درخت تِرَپ، الگوریتم‌هایی برای برنامه‌نویسی رقابتی

درخت ⟦treap⟧ ساختاری داده است که در آن درخت دودویی و هپ دودویی (بنابراین نام: درخت + هپ ⟦$\Rightarrow$⟧ Treap) ترکیب شده‌اند.

به طور خاص‌تر، ⟦treap⟧ ساختاری است که جفت‌های ⟦$(X, Y)$⟧ را در درخت دودویی ذخیره می‌کند به گونه‌ای که این درخت، بر اساس ⟦X⟧ یک درخت جست‌وجوی دودویی و بر اساس ⟦Y⟧ یک هپ دودویی باشد. اگر درون یک گره مقدارهای ⟦$(X_0, Y_0)$⟧ قرار داشته باشد، تمام گره‌های شاخه چپ دارای ⟦X \leq X_0⟧، و تمام گره‌های شاخه راست دارای ⟦X_0 \leq X⟧، و همچنین در هر دو شاخه چپ و راست، گره‌ها دارای ⟦Y \leq Y_0⟧ هستند.

⟦treap⟧ همچنین اغلب به عنوان «درخت کارتیزی» (Cartesian tree) شناخته می‌شود، زیرا به راحتی می‌توان آن را در صفحه کارتیزی قرار داد:

درخت‌های ⟦treap⟧ در سال ۱۹۸۹ توسط ⟦Raimund Siedel⟧ و ⟦Cecilia Aragon⟧ پیشنهاد شده‌اند.

مزایای این نوع سازمان‌دهی داده‌ها¶

در چنین پیاده‌سازی، مقادیر ⟦X⟧ کلیدها هستند (و در عین حال مقادیری که در ⟦treap⟧ ذخیره می‌شوند)، و مقادیر ⟦Y⟧ «اولویت‌ها» نامیده می‌شوند. بدون اولویت‌ها، ⟦treap⟧ یک درخت جست‌وجوی دودویی معمول بر اساس ⟦X⟧ بود، و مجموعه‌ای از مقادیر ⟦X⟧ می‌توانست به درخت‌های مختلفی منجر شود، برخی از آن‌ها دفرمه (مثلاً به صورت لیست پیوندی) و در نتیجه بسیار کند (عملیات اصلی دارای پیچیدگی ⟦O(N)⟧ بودند).

در عین حال، اولویت‌ها (وقتی یکتا باشند) امکان تعیین یکتای درخت ساخته شده را فراهم می‌کنند (البته، این موضوع به ترتیب افزودن مقادیر وابسته نیست)، که می‌توان آن را با استفاده از قضیه مربوطه اثبات کرد. واضح است که اگر انتخاب اولویت‌ها را به صورت تصادفی انجام دهید، درخت‌های غیر دفرمه به طور میانگین حاصل می‌شود، که این امر پیچیدگی ⟦O(\log N)⟧ را برای عملیات‌های اصلی تضمین می‌کند. بنابراین، این ساختار داده‌ها همچنین به نام «درخت جست‌وجوی دودویی تصادفی» (randomized binary search tree) شناخته می‌شود.

عملیات‌ها¶

⟦treap⟧ عملیات‌های زیر را فراهم می‌کند:

• Insert (X,Y) در ⟦O(\log N)⟧. افزودن یک گره جدید به درخت. یکی از حالت‌های ممکن این است که تنها ⟦X⟧ را وارد کنید و ⟦Y⟧ را به صورت تصادفی درون عملیات تولید کنید.
• Search (X) در ⟦O(\log N)⟧. جست‌وجو برای یافتن گره‌ای با مقدار کلید مشخص ⟦X⟧. پیاده‌سازی آن همانند درخت جست‌وجوی دودویی عادی است.
• Erase (X) در ⟦O(\log N)⟧. جست‌وجو برای یافتن گره‌ای با مقدار کلید مشخص ⟦X⟧ و حذف آن از درخت.
• Build ($X_1$, ..., $X_N$) در ⟦O(N)⟧. ساخت درخت از یک لیست مقادیر. این کار در زمان خطی امکان‌پذیر است (با فرض اینکه ⟦$X_1, ..., X_N$⟧ مرتب شده باشند).
• Union ($T_1$, $T_2$) در ⟦O(M \log (N/M))⟧. ادغام دو درخت، با فرض اینکه تمام عناصر متفاوت باشند. اگر قرار باشد عناصر تکراری حذف شوند، همان پیچیدگی قابل دستیابی است.
• Intersect ($T_1$, $T_2$) در ⟦O(M \log (N/M))⟧. یافتن تقاطع دو درخت (یعنی عناصر مشترک آن‌ها). در اینجا پیاده‌سازی این عملیات را بررسی نمی‌کنیم.

علاوه بر این، به دلیل اینکه ⟦treap⟧ یک درخت جست‌وجوی دودویی است، می‌تواند عملیات‌های دیگری مانند یافتن عنصر ⟦K⟧-ام بزرگ یا یافتن شاخص یک عنصر را نیز پیاده‌سازی کند.

توضیحات پیاده‌سازی¶

از نظر پیاده‌سازی، هر گره شامل ⟦X⟧، ⟦Y⟧ و اشاره‌گر به فرزندان چپ (⟦L⟧) و راست (⟦R⟧) است.

تمام عملیات‌های مورد نیاز را با استفاده از دو عملیات کمکی: تقسیم (Split) و ادغام (Merge) پیاده‌سازی خواهیم کرد.

تقسیم¶

Split ($T$, $X$) درخت ⟦T⟧ را به دو زیر درخت ⟦L⟧ و ⟦R⟧ تقسیم می‌کند (که مقادیر بازگشتی عملیات split هستند) به طوری که ⟦L⟧ شامل تمام عناصر با کلید ⟦$X_L \le X$⟧ و ⟦R⟧ شامل تمام عناصر با کلید ⟦$X_R > X$⟧ باشد. این عملیات دارای پیچیدگی ⟦O (\log N)⟧ است و با استفاده از بازگشت تمیز پیاده‌سازی می‌شود:

1. اگر مقدار ریشه (⟦R⟧) ⟦\leq X⟧، آنگاه L حداقل شامل R->L و R است. سپس عملیات split روی R->R را فراخوانی می‌کنیم و نتیجه split آن را به عنوان L' و R' ثبت می‌کنیم. در نهایت، L همچنین شامل L' است، در حالی که R = R'.
2. اگر مقدار ریشه (⟦R⟧) > X باشد، آنگاه R حداقل شامل R و R->R است. سپس عملیات split روی R->L را فراخوانی می‌کنیم و نتیجه split آن را به عنوان L' و R' ثبت می‌کنیم. در نهایت، L=L'، در حالی که R نیز شامل R' است.

بنابراین، الگوریتم split به شکل زیر است:

1. تعیین اینکه ریشه درخت به کدام زیر درخت تعلق دارد (چپ یا راست)
2. بازگشتی فراخوانی split روی یکی از فرزندان آن
3. ساخت نتیجه نهایی با استفاده مجدد از فراخوانی split بازگشتی.

ادغام¶

Merge ($T_1$, $T_2$) دو زیر درخت ⟦T_1⟧ و ⟦T_2⟧ را ترکیب می‌کند و درخت جدیدی برمی‌گرداند. این عملیات نیز دارای پیچیدگی ⟦O (\log N)⟧ است. فرض بر این است که ⟦T_1⟧ و ⟦T_2⟧ مرتب هستند (تمام کلیدهای ⟦X⟧ در ⟦T_1⟧ کوچکتر از کلیدهای ⟦X⟧ در ⟦T_2⟧). بنابراین، باید این درخت‌ها را بدون نقض ترتیب اولویت‌های ⟦Y⟧ ترکیب کرد. برای این کار، درختی که اولویت ⟦Y⟧ در ریشه بالاتر دارد، به عنوان ریشه انتخاب می‌شود و عملیات ادغام به صورت بازگشتی برای درخت دیگر و زیر درخت مربوطه در ریشه انتخاب شده انجام می‌شود.

درج¶

اکنون پیاده‌سازی عملیات Insert (X, Y) واضح است. ابتدا در درخت پایین می‌رویم (مانند درخت جست‌وجوی دودویی بر اساس ⟦X⟧) و در اولین گره‌ای که مقدار اولویت آن کمتر از ⟦Y⟧ باشد، توقف می‌کنیم. در این نقطه، محل قرارگیری عنصر جدید را یافته‌ایم. سپس، عملیات Split (T, X) را روی زیر درخت شروع شده از گره یافته فراخوانی می‌کنیم و زیر درخت‌های ⟦L⟧ و ⟦R⟧ را به عنوان فرزندان چپ و راست گره جدید استفاده می‌کنیم.

به طور جایگزین، درج می‌تواند با تقسیم ⟦treap⟧ اولیه بر اساس ⟦X⟧ و انجام دو عملیات ادغام با گره جدید انجام شود (به تصویر مراجعه کنید).

حذف¶

پیاده‌سازی عملیات Erase (X) نیز واضح است. ابتدا در درخت پایین می‌رویم (مانند درخت جست‌وجوی دودویی بر اساس ⟦X⟧) و به دنبال عنصر مورد نظر برای حذف می‌گردیم. پس از یافتن گره، عملیات Merge را روی فرزندان آن انجام می‌دهیم و نتیجه عملیات را جایگزین گره حذف شده می‌کنیم.

به طور جایگزین، می‌توان زیر درخت حاوی ⟦X⟧ را با دو عملیات split جدا کرد و درخت‌های باقی‌مانده را با هم ادغام کرد (به تصویر مراجعه کنید).

ساختن درخت¶

عملیات Build را با پیچیدگی ⟦O(N \log N)⟧ با استفاده از ⟦N⟧ فراخوانی Insert پیاده‌سازی می‌کنیم.

اتحاد¶

اتحاد (⟦T_1⟧، ⟦T_2⟧) از نظر نظریه‌ي پيچيدگي $O (M \log (N / M))$ دارد، اما در عمل بسيار خوب عمل مي‌کند، احتمالا با ثابت مخفي بسيار کوچک. فرض کنيد بدون از دست دادن عموم، ⟦T_1⟧ به ⟦Y⟧ و ⟦T_2⟧ به ⟦Y⟧ اشاره مي‌کنند، يعني ريشه‌ي ⟦T_1⟧ ريشه‌ي نتيجه خواهد بود. براي به‌دست آوردن نتيجه، بايد درختان ⟦T_1⟧‌، ⟦T_1⟧‌ و ⟦T_2⟧ را در دو درخت که مي‌توانند فرزندان ريشه‌ي ⟦T_1⟧ باشند، ادغام کنيم. براي اين کار، تابع Split (⟦T_2⟧، ⟦T_1⟧‌→⟦X⟧) را فراخواني مي‌کنيم، و در نتيجه ⟦T_2⟧ را به دو قسمت ⟦L⟧ و ⟦R⟧ تقسيم مي‌کنيم، که سپس به صورت بازگشتي با فرزندان ⟦T_1⟧‌ ادغام مي‌شوند: Union (⟦T_1⟧‌→⟦L⟧، ⟦L⟧) و Union (⟦T_1⟧‌→⟦R⟧، ⟦R⟧)، و در نتيجه شاخه‌هاي چپ و راست نتيجه به دست مي‌آيد.

پياده‌سازي¶

struct item {
    int key, prior;
    item *l, *r;
    item () { }
    item (int key) : key(key), prior(rand()), l(NULL), r(NULL) { }
    item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};
typedef item* pitem;

اين تعريف عنصر ما است. توجه داشته باشيد که دو اشاره‌گر فرزند و يک کلید صحيح (برای BST) و يک اولويت صحيح (برای heap) وجود دارد. اولويت با استفاده از يک توليدکننده عدد تصادفی تخصيص داده می‌شود.

void split (pitem t, int key, pitem & l, pitem & r) {
    if (!t)
        l = r = NULL;
    else if (t->key <= key)
        split (t->r, key, t->r, r),  l = t;
    else
        split (t->l, key, l, t->l),  r = t;
}

t درخت‌تريپ است که بايد تقسيم شود، و key مقدار BST است که بر اساس آن تقسيم انجام می‌شود. توجه داشته باشيد که ما مقادير return را در جايی نمي‌نويسيم؛ در عوض، درختان‌تريپ خروجی از طریق l و r نوشته می‌شوند، برای مثال:

pitem l = nullptr, r = nullptr;
split(t, 5, l, r);

اين تابع split ممکن است پيچيده باشد، زيرا هم اشاره‌گر دارد (pitem) و هم ارجاع به آن اشاره‌گرها (pitem &l). بگذاريد در کلمات، هدف فراخوانی تابع split(t, k, l, r) را درک کنيم: «درخت‌تريپ t را بر اساس مقدار k تقسيم کن و شاخه چپ را در l و شاخه راست را در r ذخيره کن». عالی! حالا، بیایید این تعریف را در دو فراخوانی بازگشتی، با استفاده از مواردی که در بخش قبل تحلیل کردیم، به کار ببريم: (شرط if اول، یک حالت پایه ساده برای درخت‌تريپ خالی است)

1. وقتی مقدار ريشه ≤ کلید است، تابع split (t->r, key, t->r, r) را فرا می‌خوانيم، که به معنی: «درخت‌تريپ t->r (شاخه راست t) را بر اساس مقدار key تقسيم کن و شاخه چپ را در t->r و شاخه راست را در r ذخيره کن». پس از آن، l = t را تنظيم مي‌کنيم. توجه داشته باشيد که مقدار l نتايج t->l، t و t->r (که نتیجه فراخوانی بازگشتی است) همگي در ترتيب صحيح ادغام شده‌اند! بايد توقف کنيد و اطمينان حاصل کنيد که اين نتايج l و r دقيقاً با آنچه در توضيح پياده‌سازي قبلاً بحث شد، مطابقت دارد.
2. وقتی مقدار ريشه بزرگ‌تر از کلید است، تابع split (t->l, key, l, t->l) را فرا می‌خوانيم، که به معنی: «درخت‌تريپ t->l (شاخه چپ t) را بر اساس مقدار key تقسيم کن و شاخه چپ را در l و شاخه راست را در t->l ذخيره کن». پس از آن، r = t را تنظيم مي‌کنيم. توجه داشته باشيد که مقدار r نتايج t->l (نتیجه فراخوانی بازگشتی)، t و t->r، همگي در ترتيب صحيح ادغام شده‌اند! بايد توقف کنيد و اطمينان حاصل کنيد که اين نتايج l و r دقيقاً با آنچه در توضيح پياده‌سازي قبلاً بحث شد، مطابقت دارد.

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

void insert (pitem & t, pitem it) {
    if (!t)
        t = it;
    else if (it->prior > t->prior)
        split (t, it->key, it->l, it->r),  t = it;
    else
        insert (t->key <= it->key ? t->r : t->l, it);
}

void merge (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
}

void erase (pitem & t, int key) {
    if (t->key == key) {
        pitem th = t;
        merge (t, t->l, t->r);
        delete th;
    }
    else
        erase (key < t->key ? t->l : t->r, key);
}

pitem unite (pitem l, pitem r) {
    if (!l || !r)  return l ? l : r;
    if (l->prior < r->prior)  swap (l, r);
    pitem lt, rt;
    split (r, l->key, lt, rt);
    l->l = unite (l->l, lt);
    l->r = unite (l->r, rt);
    return l;
}

حفظ اندازه‌های زیر درخت‌ها¶

برای گسترش قابلیت‌های درخت‌تريپ، اغلب لازم است تعداد گره‌های هر زیر درخت را در فیلد int cnt در ساختار item ذخیره کنیم. برای مثال، می‌تواند برای پیدا کردن عنصر K‌ام بزرگ در درخت در زمان $O (\log N)$، یا برای یافتن شاخص عنصر در لیست مرتب شده با همان پیچیدگی، استفاده شود. پیاده‌سازی این عملیات‌ها همانند درخت جستجوی دودویی معمول است.

وقتی درخت تغییر می‌کند (گره‌ها اضافه یا حذف می‌شوند و غیره)، باید cnt برخی گره‌ها به‌طور مناسب به‌روزرسانی شود. دو تابع ایجاد می‌کنیم: cnt() مقدار فعلی cnt را برمی‌گرداند یا ۰ اگر گره وجود نداشته باشد، و upd_cnt() مقدار cnt را برای این گره به‌روزرسانی می‌کند، فرض بر این است که برای فرزندان آن، cnt قبلاً به‌روزرسانی شده است. به وضوح کافی است فراخوان‌های upd_cnt() را به انتهای insert، erase، split و merge اضافه کنید تا مقادیر cnt به‌روز باقی بمانند.

int cnt (pitem t) {
    return t ? t->cnt : 0;
}

void upd_cnt (pitem t) {
    if (t)
        t->cnt = 1 + cnt(t->l) + cnt (t->r);
}

ساختن درخت‌تريپ در زمان $O (N)$ در حالت آفلاین¶

با داشتن یک لیست مرتب از کلیدها، می‌توان درخت‌تريپ را سریع‌تر از وارد کردن کلیدها یکی یکی که زمان آن $O(N \log N)$ است، ساخت. از آنجایی که کلیدها مرتب شده‌اند، می‌توان به راحتی درخت جستجوی دودویی متوازن را در زمان خطی ساخت. مقادیر heap ⟦Y⟧ به صورت تصادفی مقداردهی اولیه می‌شوند و سپس می‌توان آن‌ها را مستقل از کلیدهای ⟦X⟧ به صورت heapified درآورد تا ساختن heap در زمان $O(N)$ انجام شود.

void heapify (pitem t) {
    if (!t) return;
    pitem max = t;
    if (t->l != NULL && t->l->prior > max->prior)
        max = t->l;
    if (t->r != NULL && t->r->prior > max->prior)
        max = t->r;
    if (max != t) {
        swap (t->prior, max->prior);
        heapify (max);
    }
}

pitem build (int * a, int n) {
    // Construct a treap on values {a[0], a[1], ..., a[n - 1]}
    if (n == 0) return NULL;
    int mid = n / 2;
    pitem t = new item (a[mid], rand ());
    t->l = build (a, mid);
    t->r = build (a + mid + 1, n - mid - 1);
    heapify (t);
    upd_cnt(t);
    return t;
}

توجه: فراخوانی upd_cnt(t) تنها در صورتی لازم است که به اندازه‌های زیر درخت نیاز دارید.

روش بالا همیشه درختی کاملاً متعادل فراهم می‌کند، که در موارد عملی معمولاً خوب است، اما به هزینه‌ی نگه داشتن اولویت‌هایی که در ابتدا به هر گره اختصاص یافته است، نیست. بنابراین، این روش برای حل مشکل زیر مناسب نیست:

acmsguru - درخت کارتزین

با داشتن یک دنباله از زوج‌ها $(x_i, y_i)$، یک درخت کارتزین بر روی آن‌ها بسازید. تمام $x_i$ و تمام $y_i$ یکتا هستند.

توجه داشته باشید که در این مسئله اولویت‌ها تصادفی نیستند، بنابراین فقط وارد کردن رأس‌ها یکی یکی می‌تواند راه‌حلی درجه‌دو ارائه دهد.

یکی از راه‌حل‌های ممکن این است که برای هر عنصر، نزدیک‌ترین عناصر به چپ و راست را پیدا کنید که اولویت کمتری نسبت به این عنصر دارند. در میان این دو عنصر، آن‌که اولویت بزرگ‌تری دارد، باید پدر عنصر جاری باشد.

این مسئله با تغییر پشته کمینه در زمان خطی قابل حل است. ساختار زیر از قاعده min-heap برای اولویت‌ها استفاده می‌کند، بر خلاف قاعده max-heap که در پیاده‌سازی درخت‌تريپ معمولی بالا به کار رفته است، و فرض می‌کند که item با اشاره‌گر پدر p توسعه یافته است که به nullptr مقداردهی اولیه شده است.

void connect(auto from, auto to) {
    vector<pitem> st;
    for(auto it: ranges::subrange(from, to)) {
        while(!st.empty() && st.back()->prior > it->prior) {
            st.pop_back();
        }
        if(!st.empty()) {
            if(!it->p || it->p->prior < st.back()->prior) {
                it->p = st.back();
            }
        }
        st.push_back(it);
    }
}

pitem build(int *x, int *y, int n) {
    vector<pitem> nodes(n);
    for(int i = 0; i < n; i++) {
        nodes[i] = new item(x[i], y[i]);
    }
    connect(nodes.begin(), nodes.end());
    connect(nodes.rbegin(), nodes.rend());
    for(int i = 0; i < n; i++) {
        if(nodes[i]->p) {
            if(nodes[i]->p->key < nodes[i]->key) {
                nodes[i]->p->r = nodes[i];
            } else {
                nodes[i]->p->l = nodes[i];
            }
        }
    }
    return nodes[min_element(y, y + n) - y];
}

درخت‌تريپ‌های ضمنی¶

درخت‌تريپ ضمنی، یک تغییر ساده در درخت‌تريپ معمولی است که یک ساختار داده بسیار قدرتمند است. در واقع، درخت‌تريپ ضمنی می‌تواند به عنوان یک آرایه در نظر گرفته شود که عملیات زیر را پیاده‌سازی می‌کند (همه در زمان $O (\log N)$ در حالت آنلاین):

• درج یک عنصر در آرایه در هر مکان
• حذف یک عنصر دلخواه
• یافتن مجموع، کمینه / بیشینه در یک بازه دلخواه
• اضافه کردن، رنگ‌آمیزی در یک بازه دلخواه
• معکوس کردن عناصر در یک بازه دلخواه

ایده این است که کلیدها باید شاخص‌های صفر مبنا درجۀ عناصر در آرایه باشند. اما این مقادیر را به صورت صریح ذخیره نمی‌کنیم (در غیر این صورت، برای مثال، درج یک عنصر باعث تغییر کلید در $O (N)$ گره در درخت می‌شود).

توجه داشته باشید که کلید یک گره، تعداد گره‌هایی است که کمتر از آن هستند (این گره‌ها می‌توانند نه تنها در زیر درخت چپ آن، بلکه در زیر درخت‌های چپ اجداد آن نیز وجود داشته باشند). به طور خاص، کلید ضمنی برای یک گره T، تعداد رئوس $cnt (T \rightarrow L)$ در زیر درخت چپ این گره است، به علاوه مقادیر مشابه $cnt (P \rightarrow L) + 1$ برای هر اجداد P گره T، اگر T در زیر درخت راست P قرار داشته باشد.

حالا واضح است که چگونه می‌توان کلید ضمنی گره جاری را به سرعت محاسبه کرد. چون در تمام عملیات‌ها، به هر گره با پایین آمدن در درخت می‌رسیم، می‌توانیم این مجموع را جمع کنیم و به تابع منتقل کنیم. اگر به زیر درخت چپ برویم، این مجموع تجمع یافته تغییر نمی‌کند، اما اگر به زیر درخت راست برویم، با $cnt (T \rightarrow L) + 1$ افزایش می‌یابد.

در اینجا پیاده‌سازی‌های جدید Split و Merge آمده است:

void merge (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
    upd_cnt (t);
}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
    if (!t)
        return void( l = r = 0 );
    int cur_key = add + cnt(t->l); //implicit key
    if (key <= cur_key)
        split (t->l, l, t->l, key, add),  r = t;
    else
        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
    upd_cnt (t);
}

در پیاده‌سازی بالا، پس از فراخوانی $split(T, T_1, T_2, k)$، درخت $T_1$ شامل اولین $k$ عنصر از $T$ (یعنی عناصری که کلید ضمنی آن‌ها کمتر از $k$ است) خواهد بود و $T_2$ شامل بقیه عناصر است.

حالا بیایید پیاده‌سازی عملیات مختلف روی درخت‌های ضمنی را بررسی کنیم:

• درج عنصر. فرض کنید نیاز است عنصری را در موقعیت $pos$ وارد کنیم. درخت را به دو قسمت تقسیم می‌کنیم، که متناظر با آرایه‌های $[0..pos-1]$ و $[pos..sz]$ است؛ برای این کار، $split(T, T_1, T_2, pos)$ را فراخوانی می‌کنیم. سپس می‌توانیم درخت $T_1$ را با رأس جدید با فراخوانی $merge(T_1, T_1, \text{new item})$ ترکیب کنیم (به راحتی می‌توان دید که تمام پیش‌شرط‌ها برآورده شده است). در نهایت، درخت‌های $T_1$ و $T_2$ را با فراخوانی $merge(T, T_1, T_2)$ دوباره به هم می‌پیچیم.
• حذف عنصر. این عملیات حتی ساده‌تر است: عنصری را که باید حذف شود، $T$، پیدا کنید، سپس فرزندهای آن $L$ و $R$ را با هم ادغام کنید و عنصر $T$ را با نتیجه ادغام جایگزین کنید. در واقع، حذف عنصر در درخت ضمنی دقیقاً همانند درخت معمولی است.
• پیدا کردن مجموع / کمینه و غیره در بازه. ابتدا، یک فیلد اضافی $F$ در ساختار item ایجاد کنید تا مقدار تابع هدف برای زیر درخت این گره را نگه دارد. نگهداری این فیلد به آسانی همانند نگهداری اندازه‌های زیر درخت‌ها است: یک تابع بسازید که این مقدار را بر اساس مقادیر فرزندان آن برای یک گره محاسبه می‌کند و فراخوانی‌های این تابع را در پایان تمام توابعی که درخت را تغییر می‌دهند، اضافه کنید. دوم، باید بدانید چگونه درخواست برای یک بازه دلخواه $[A; B]$ را پردازش کنید. برای به‌دست آوردن بخشی از درخت که متناظر با بازه $[A; B]$ است، باید $split(T, T_2, T_3, B+1)$ را فراخوانی کنید، و سپس $split(T_2, T_1, T_2, A)$ را انجام دهید: پس از این، $T_2$ شامل تمام عناصر در بازه $[A; B]$ است و فقط آن‌ها. بنابراین، پاسخ به درخواست در فیلد $F$ ریشه درخت $T_2$ ذخیره می‌شود. پس از پاسخگویی، درخت باید با فراخوانی $merge(T, T_1, T_2)$ و $merge(T, T, T_3)$ بازسازی شود.
• اضافه کردن / نقاشی در بازه. مشابه پاراگراف قبلی عمل می‌کنیم، اما به جای فیلد $F$، فیلد add را نگه می‌داریم که مقدار افزوده شده برای زیر درخت (یا مقداری که زیر درخت نقاشی شده است) را در بر می‌گیرد. قبل از انجام هر عملیاتی، باید این مقدار را «فشار» دهیم — یعنی $T \rightarrow L \rightarrow add$ و $T \rightarrow R \rightarrow add$ را تغییر دهیم، و add در گره والد را پاک کنیم. این کار باعث می‌شود که پس از هر تغییر در درخت، اطلاعات از دست نرود.
• معکوس‌سازی در بازه. این عملیات مجدد مشابه عملیات قبلی است: باید پرچم بولی rev را اضافه کنیم و هرگاه زیر درخت گره جاری باید معکوس شود، آن را تغییر دهیم. «فشار دادن» این مقدار کمی پیچیده است — باید فرزندان این گره را جابجا کنیم و این پرچم را برای آن‌ها تغییر دهیم.

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

typedef struct item * pitem;
struct item {
    int prior, value, cnt;
    bool rev;
    pitem l, r;
};

int cnt (pitem it) {
    return it ? it->cnt : 0;
}

void upd_cnt (pitem it) {
    if (it)
        it->cnt = cnt(it->l) + cnt(it->r) + 1;
}

void push (pitem it) {
    if (it && it->rev) {
        it->rev = false;
        swap (it->l, it->r);
        if (it->l)  it->l->rev ^= true;
        if (it->r)  it->r->rev ^= true;
    }
}

void merge (pitem & t, pitem l, pitem r) {
    push (l);
    push (r);
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
    upd_cnt (t);
}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
    if (!t)
        return void( l = r = 0 );
    push (t);
    int cur_key = add + cnt(t->l);
    if (key <= cur_key)
        split (t->l, l, t->l, key, add),  r = t;
    else
        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
    upd_cnt (t);
}

void reverse (pitem t, int l, int r) {
    pitem t1, t2, t3;
    split (t, t1, t2, l);
    split (t2, t2, t3, r-l+1);
    t2->rev ^= true;
    merge (t, t1, t2);
    merge (t, t, t3);
}

void output (pitem t) {
    if (!t)  return;
    push (t);
    output (t->l);
    printf ("%d ", t->value);
    output (t->r);
}

ادبیات¶

• Blelloch, Reid-Miller "عملیات سریع مجموعه‌ها با استفاده از درخت‌های Treap"

مسائل تمرینی¶

• SPOJ - Ada and Aphids
• SPOJ - Ada and Harvest
• Codeforces - Radio Stations
• SPOJ - Ghost Town
• SPOJ - Arrangement Validity
• SPOJ - All in One
• Codeforces - Dog Show
• Codeforces - Yet Another Array Queries Problem
• SPOJ - Mean of Array
• SPOJ - TWIST
• SPOJ - KOILINE
• CodeChef - The Prestige
• Codeforces - T-Shirts
• Codeforces - Wizards and Roads
• Codeforces - Yaroslav and Points
• Codeforces - KiaKio and Energy Intervals