چگونه با درختان بخش دوست شدم

هفته گذشته، من در مورد یک ساختار داده پیشرفته صحبت کردم که برای رسیدگی به سؤالات دامنه مکرر مفید است – Fenwick Tree. با این حال، خیلی همه کاره نیست زیرا بیشتر برای پرس و جوهای جمع استفاده می شود، و من شخصاً هرگز از آن برای هیچ نوع مشکل دیگری استفاده نکردم. با این حال، بازیکن دیگری در زمین حضور دارد که کلاه های بسیار بیشتری دارد. خانم‌ها و آقایان، Segment Tree را که یکی از مفیدترین و در عین حال اغلب نادیده گرفته می‌شود، ملاقات کنید.

چرا تصمیم گرفتم آن را یاد بگیرم

بنابراین، انگیزه من در پشت یادگیری Segment Trees چه بود؟ پاسخ بسیار ساده است، در واقع. از حل مشکلاتی که نمی‌توانستم آن‌ها را حل کنم خسته شدم. شما می توانید آن را به عنوان تلاش برای ساخت یک مبلمان بدون ابزار مناسب در نظر بگیرید. در این مثال، مبلمان تمام مشکلات Segment Tree هستند که سعی می‌کنم با استفاده از روش‌های دیگر، یعنی استفاده از ابزارهای اشتباه، آن‌ها را حل کنم.

هر بار که مسابقه‌ای را تمام می‌کنم و می‌بینم که کسی راه‌حلی ارسال می‌کند که می‌گوید این یک مشکل معمولی Segment Tree است، کمی دلسرد می‌شوم، زیرا هنوز چیزی در مورد این ساختار داده نمی‌دانستم. من همیشه یادگیری آن را به تعویق می انداختم، زیرا بسیار پیچیده به نظر می رسید. به طور جدی، من فقط «Segment Tree» را در گوگل جستجو می‌کردم و اولین پیوندی که می‌گرفتم معمولاً از الگوریتم‌های cp است. اگر با شما صادق باشم، مقاله در آن وب سایت حتی پیچیده تر از دیپلم لیسانس من است. با این حال، من مطمئن بودم که باید راه دیگری برای یادگیری این ساختار داده وجود داشته باشد که مبتدی‌تر باشد.

چگونه اصول را یاد گرفتم

اگر پست قبلی وبلاگ من را بخوانید، قبلاً با کتابچه راهنمای برنامه نویس رقابتی و وب سایتی که می توانید اکثر الگوریتم ها و ساختارهای داده شرح داده شده در این کتاب را در آن تمرین کنید، آشنا هستید. این دو منبع مورد علاقه من برای یادگیری چیزهای جدید در حوزه برنامه نویسی رقابتی هستند. البته، بسیاری از منابع مفید دیگر نیز وجود دارد، و امروز می‌خواهم روند گام‌به‌گامی را با شما در میان بگذارم تا Segment Trees را به خوبی یاد بگیرم.

اول از همه، من به بخش “درخت بخش” در کتابچه راهنما که به تازگی با شما به اشتراک گذاشتم، رفتم. توضیح بسیار واضح و مثال خوبی دارد که عملکردهای اساسی آن را نشان می دهد sum و add. به نظر من، درک ایده پشت هر عملکرد و همچنین آنچه در مثال ها می گذرد بسیار مهم است. اعتراف می کنم که ممکن است برخی از چیزهای کد در همان ابتدا مشخص نباشد، اما اشکالی ندارد.

به هر حال، پس از پایان خواندن بخش، به پیاده سازی Segment Tree خودم در Python رسیدم:

from math import ceil, log2


class SegmentTree:
    def __init__(self, A: list[int]) -> None:
        self.n = 2 ** ceil(log2(len(A)))
        self.tree = [0] * (self.n * 2)

        for k, x in enumerate(A):
            self.add(k, x)

    def add(self, k: int, x: int) -> None:
        k += self.n

        self.tree[k] += x
        k //= 2

        while k >= 1:
            self.tree[k] = self.tree[k * 2] + self.tree[k * 2 + 1]
            k //= 2

    def sum(self, a: int, b: int) -> int:
        a += self.n
        b += self.n

        s = 0

        while a <= b:
            if a % 2 == 1:
                s += self.tree[a]
                a += 1

            if b % 2 == 0:
                s += self.tree[b]
                b -= 1

            a //= 2
            b //= 2

        return s

همانطور که می بینید، تنها چیزی که باید توسط خودم می نوشتم این بود __init__ عملکرد، که به هر حال بسیار ساده بود. توجه داشته باشید که ceil(log2(len(A))) به سادگی راهی برای بدست آوردن اولین عدد است که توان 2 است که بزرگتر یا مساوی است len(A). در اینجا، ما نیز آن را فرض می کنیم len(A) != 0. هر چیز دیگری در کد من طبق توضیحات کتاب پیاده سازی شده است.

پس از پرداختن به اصول اولیه، کمی جلوتر رفتم و بخش‌های دیگر را خواندم که شامل موضوعات مربوط به سایر پرسش‌ها، یافتن شاخص حداقل مقدار و به‌روزرسانی‌های محدوده بود. من مطمئن شدم که همه آنها را پیاده سازی کردم و نمونه های کتاب را در کدم اجرا کردم.

پس از انجام چند بازی، به سرعت متوجه چیز دیگری شدم. کارکرد add در واقع می توان به set مانند:

class SegmentTree:
    # ...

    def set(self, k: int, x: int) -> None:
        k += self.n

        self.tree[k] = x  # changed from "self.tree[k] += x"
        k //= 2

        while k >= 1:
            self.tree[k] = min(self.tree[k * 2], self.tree[k * 2 + 1])
            k //= 2

این تغییر ساده زمانی مفید بود که SegmentTree را که حداقل پرس و جوها را پشتیبانی می کند، اجرا کردم:

from math import inf, ceil, log2


class SegmentTree:
    def __init__(self, A: list[int]) -> None:
        self.n = 2 ** ceil(log2(len(A)))
        self.tree = [inf] * (self.n * 2)

        for k, x in enumerate(A):
            self.set(k, x)

    def set(self, k: int, x: int) -> None:
        k += self.n

        self.tree[k] = x
        k //= 2

        while k >= 1:
            self.tree[k] = min(self.tree[k * 2], self.tree[k * 2 + 1])
            k //= 2

    def min(self, a: int, b: int) -> int:
        a += self.n
        b += self.n

        res = inf

        while a <= b:
            if a % 2 == 1:
                res = min(res, self.tree[a])
                a += 1

            if b % 2 == 0:
                res = min(res, self.tree[b])
                b -= 1

            a //= 2
            b //= 2

        return res

به طور منطقی، وقتی با پرس و جوهای حداقل/حداکثر سروکار داریم، نمی خواهیم عناصر خاصی را کم یا زیاد کنیم، بلکه آنها را به طور کلی تغییر دهیم، به همین دلیل است که set عملکرد در این پیاده سازی معقول تر به نظر می رسد.

به هر حال، نکته همه چیزهایی که تا به حال به شما گفته ام این است که وقتی شروع به درک اصول اولیه کردید، خودتان شروع به مشاهده الگوهای جالب دیگر می کنید. وب سایت هایی مانند الگوریتم های cp، بسیار جامع بودن و همه چیز، از همان ابتدا شما را با تمام این الگوها و مشاهدات اضافی سرازیر می کند، که نه تنها شما را تحت تأثیر قرار می دهد، بلکه این فرصت را از شما می گیرد که خودتان متوجه چیزی شوید! البته ممکن است آن سایت‌ها هنوز هم بسیار مفید باشند، به خصوص اگر از آنها به عنوان یک مرجع استفاده کنید، زمانی که الگوریتم‌های توضیح داده شده در آنجا را می‌شناسید.

چگونه آموخته ام را تمرین کردم

زمانی که با تئوری برخورد کردم و به پیاده سازی های خودم رسیدم که اتفاقاً در این مخزن بارگذاری کردم، تصمیم گرفتم مشکلات خوبی برای تمرین پیدا کنم. جای تعجب نیست که اولین انتخاب من CSES بود. دارای مجموعه بزرگی از مشکلات است که به طور خاص به “پرسش های محدوده” اختصاص داده شده است. اگر شما نیز در مسیر تسلط بر Segment Trees هستید، پیشنهاد می‌کنم 5 مشکل اول آن لیست را حل کنید:

همه آنها ساده هستند و مطمئناً پس از پاک کردن آنها احساس افزایش اعتماد به نفس خواهید کرد. برای تمرین تکنیک های جالب تر، پیشنهاد می کنم به مشکلات زیر مراجعه کنید:

• پرسش‌های به‌روزرسانی محدوده (نام همه چیز را نشان می‌دهد: به‌روزرسانی‌های محدوده سریع را تمرین خواهید کرد)

• سوالات هتل (مطمئناً سخت ترین مشکل در این لیست است، اما اگر آن را حل کنید رضایت زیادی به شما خواهد داد)

شما می توانید راه حل های من را در این مخزن بیابید. اتفاقاً قصد دارم برای بسیاری از مشکلات دیگر هم در آنجا راه حل اضافه کنم.

با توجه به اینکه CSES یک سایت فوق العاده مفید است، گاهی اوقات کافی نیست. علاوه بر این، جامعه‌ای در آنجا تقریباً وجود ندارد، که اگر نمی‌دانید چگونه یک مشکل خاص را حل کنید، «گیر افتادن» برای شما دشوارتر می‌شود. به همین دلیل، من تقریبا همیشه سعی می کنم مشکلات مشابهی را برای تمرین در LeetCode نیز پیدا کنم. خوشبختانه، در یکی از مسابقات اخیر نیز مشکل بسیار خوبی در Segment Trees وجود داشت: Peaks in Array. من می توانم بگویم که حتی سخت تر از “پرسش های هتل” از لیست بالا است. با این حال، قطعا درک بهتری از نحوه تشخیص الگوی Segment Tree در یک مشکل برنامه‌نویسی رقابتی به شما می‌دهد. به هر حال راه حل من اینجاست. همانطور که می بینید، من همان پیاده سازی را که پس از خواندن کتاب راهنما به آن دست یافتم، دنبال کردم، فقط یک روش اضافی اضافه کردم و توابع دیگر را کمی تغییر دادم. حدس می‌زنم وقتی شروع به حل مشکلاتی مثل این کنید، این فرآیند خلاق‌تر می‌شود و من واقعاً آن را دوست دارم.

در مورد موضوعات پیشرفته تر چطور؟

در این مرحله، برخی از شما ممکن است فکر کنید، “اما باید چیز دیگری برای Segment Trees وجود داشته باشد. آنها نمی توانند به این سادگی باشند! به هر حال، چرا اینطور می شود. الگوریتم های cp وب سایت چنین بحث طولانی در مورد آنها دارد؟” و شما کاملاً درست می گویید! البته، تکنیک های پیشرفته ای مانند “تبلیغ تنبل” و دیگران وجود دارد که من حتی ریسک نمی کنم نام آنها را ذکر کنم. عجله در تلاش برای تسلط بر همه چیز به طور همزمان، این تکنیک های پیشرفته احتمالاً همان چیزی است که طبق اصل پارتو از 80 درصد تلاش ها به دست می آید.

بنابراین، به‌جای نگرانی از اینکه هنوز چیزهای زیادی نمی‌دانید، معتقدم که بهتر است روی چیزهایی که قبلاً می‌دانید تمرکز کنید و الگوها را برای انواع مختلف پرس‌وجوها تمرین کنید، درست مانند آنچه در مشکلات «پرس و جوهای هتل» و “قله ها در آرایه.” و هنگامی که در انجام آن راحت باشید، قطعاً از یادگیری تکنیک های پیشرفته سود بیشتری خواهید برد.

شاید من هم روزی به آن موضوعات پیشرفته بپردازم و تجربیاتم را با شما به اشتراک بگذارم. با این حال، دنیای برنامه نویسی بسیار بزرگ است و DSA تنها بخش کوچکی از آن را تشکیل می دهد. می دانم که در بسیاری از زمینه های دیگر نیز یاد خواهم گرفت و پیشرفت خواهم کرد. اما اگر انگیزه ای برای یادگیری آن مفاهیم واقعا پیشرفته پیدا کنم، قطعا آنها را امتحان خواهم کرد. و حتی اگر نتوانم همه آنها را درک کنم، یک چیز ثابت می ماند: خود گذشته من همچنان به من افتخار می کند.