پرش به محتویات

تریپ (Treap) (درخت دکارتی)

تریپ (Treap) یه ساختمان داده‌ست که «درخت دودویی» (binary tree) و «هرم دودویی» (binary heap) رو با هم قاطی می‌کنه (اسمش هم از همین ترکیب باحال اومده: tree + heap $\Rightarrow$ Treap).

اگه بخوایم دقیق‌تر بگیم، تریپ یه ساختمان داده‌ست که جفت‌های $(X, Y)$ رو توی یه درخت دودویی ذخیره می‌کنه. جوری که نسبت به $X$ یه «درخت جستجوی دودویی» (binary search tree) باشه و نسبت به $Y$ یه «هرم دودویی» (binary heap). یعنی اگه یه گره توی درخت مقادیر $(X_0, Y_0)$ رو داشته باشه، تمام گره‌های توی زیردرخت چپش $X \leq X_0$ هستن و تمام گره‌های زیردرخت راستش $X_0 \leq X$ هستن. از طرفی، همه‌ی گره‌های توی هر دو زیردرخت چپ و راست، $Y \leq Y_0$ دارن.

به تریپ «درخت دکارتی» (cartesian tree) هم میگن، چون خیلی راحت میشه اون رو روی یه صفحه دکارتی کشید و تصورش کرد:

تریپ‌ها رو Raimund Siedel و Cecilia Aragon سال ۱۹۸۹ معرفی کردن.

این مدل سازماندهی داده به چه دردی می‌خوره؟

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

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

عملیات‌ها

یه تریپ این عملیات‌ها رو در اختیارت میذاره:

  • 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))$. اشتراک دو تا درخت رو پیدا می‌کنه (یعنی عناصری که تو هر دوتاشون هستن). ما اینجا پیاده‌سازی این عملیات رو بررسی نمی‌کنیم.

علاوه بر اینا، چون تریپ یه جور درخت جستجوی دودوییه، می‌تونه عملیات‌های دیگه‌ای مثل پیدا کردن $K$-امین عنصر بزرگتر یا پیدا کردن اندیس یه عنصر رو هم پیاده‌سازی کنه.

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

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

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

Split

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

  1. اگه مقدار گره ریشه (R) کوچیک‌تر یا مساوی $X$ باشه، پس L حداقل شامل خود R و کل زیردرخت چپش (R->L) میشه. بعدش، میریم سراغ زیردرخت راستش (R->R) و split رو روی اون صدا می‌زنیم. نتیجه‌ی این تقسیم رو می‌گیریم و اسمشو میذاریم L' و R'. در نهایت، L ما شامل L' هم میشه، و R همون R' خواهد بود.
  2. اگه مقدار گره ریشه (R) بزرگ‌تر از $X$ باشه، پس R حداقل شامل خود R و کل زیردرخت راستش (R->R) میشه. بعدش، split رو روی زیردرخت چپش (R->L) صدا می‌زنیم و نتیجه‌ی تقسیم رو می‌گیریم و اسمشو میذاریم L' و R'. در نهایت، L ما همون L' خواهد بود و R شامل R' هم میشه.

پس الگوریتم split اینجوریه:

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

Merge

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

Insert

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

یه راه دیگه‌ هم اینه که تریپ اصلی رو با کلید $X$ به دو قسمت تقسیم (split) کنی و بعد با دو تا عمل ادغام (merge)، گره جدید رو بینشون قرار بدی (به عکس نگاه کن).

Erase

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

یه راه جایگزین دیگه اینه که با دو تا عملیات split، زیردرخت حاوی $X$ رو جدا کنیم و تریپ‌های باقی‌مونده رو با هم ادغام کنیم (به عکس نگاه کن).

Build

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

Union

Union ($T_1$, $T_2$) پیچیدگی نظری $O (M \log (N / M))$ داره، ولی در عمل خیلی خوب کار می‌کنه و احتمالاً ثابت پنهان خیلی کوچیکی داره. بدون اینکه کلیت مسئله رو از دست بدیم، فرض می‌کنیم $T_1 \rightarrow Y > T_2 \rightarrow Y$ باشه، یعنی ریشه‌ی $T_1$، ریشه‌ی درخت نهایی هم خواهد بود. برای اینکه به نتیجه برسیم، باید درخت‌های $T_1 \rightarrow L$، $T_1 \rightarrow R$ و $T_2$ رو طوری توی دو تا درخت ادغام کنیم که بتونن بچه‌های ریشه‌ی $T_1$ بشن. برای این کار، $Split (T_2, T_1\rightarrow X)$ رو صدا می‌زنیم و $T_2$ رو به دو بخش L و R می‌شکافیم. بعد این‌ها رو به صورت بازگشتی با بچه‌های $T_1$ ترکیب می‌کنیم: Union ($T_1 \rightarrow L$, $L$) و Union ($T_1 \rightarrow 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;

این تعریف item ماست. دقت کن که دو تا اشاره‌گر به بچه‌ها، یه کلید صحیح (برای BST) و یه اولویت صحیح (برای هرم) داریم. اولویت با استفاده از یه مولد عدد تصادفی (rand()) اختصاص داده میشه.

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 همون مقدار کلیدیه که تقسیم بر اساس اون انجام میشه. حواست باشه که ما مقادیر نتیجه رو جایی return نمی‌کنیم، بلکه اینجوری ازشون استفاده می‌کنیم:

pitem l = nullptr, r = nullptr;
split(t, 5, l, r);
if (l) cout << "Left subtree size: " << (l->size) << endl;
if (r) cout << "Right subtree size: " << (r->size) << endl;

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

  1. وقتی مقدار گره ریشه $\le$ کلید باشه، ما 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 دقیقاً با چیزی که قبلاً توی بخش «توضیحات پیاده‌سازی» گفتیم، جور درمیاد.

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

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 رو برای یه گره آپدیت می‌کنه، با این فرض که برای بچه‌های L و R اون، مقادیر 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)$ درج کنی، میشه بهتر عمل کرد. چون کلیدها مرتب هستن، میشه یه درخت جستجوی دودویی متوازن رو خیلی راحت در زمان خطی ساخت. مقادیر هرم $Y$ به صورت تصادفی مقداردهی میشن و بعد میشه اونا رو مستقل از کلیدهای $X$ در زمان $O(N)$ به حالت هرم درآورد (heapify) (اطلاعات بیشتر در مورد ساختن هرم).

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 - Cartesian Tree

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

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

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

این مسئله با یه تغییر کوچیک توی الگوریتم پشته مینیمم در زمان خطی قابل حله:

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];
}

تریپ‌های ضمنی (Implicit Treaps)

تریپ ضمنی (Implicit treap) یه تغییر ساده روی همون تریپ معمولیه که یهو تبدیلش می‌کنه به یه ساختمان داده‌ی فوق‌العاده قدرتمند. جدی میگم، تریپ ضمنی رو می‌تونی مثل یه آرایه در نظر بگیری که این کارها رو میشه روش انجام داد (همه‌شون با پیچیدگی $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, new_item)). در نهایت، درخت $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$ ذخیره شده. بعد از جواب دادن به کوئری، باید درخت رو با ادغام مجدد سه بخش، به حالت اول برگردونیم: اول $T_1$ و $T_2$ رو ادغام می‌کنیم و بعد نتیجه رو با $T_3$ ادغام می‌کنیم.
  • افزودن / رنگ‌آمیزی در یک بازه. اینجا هم مثل پاراگراف قبلی عمل می‌کنیم، ولی به جای فیلد F، یه فیلد add ذخیره می‌کنیم که حاوی مقدار اضافه‌شده برای زیردرخته (یا مقداری که زیردرخت باهاش رنگ‌آمیزی شده). قبل از انجام هر عملیاتی باید این مقدار رو به درستی "push" کنیم. یعنی $T \rightarrow L \rightarrow add$ و $T \rightarrow R \rightarrow add$ رو تغییر بدیم و add رو توی گره والد پاک کنیم. اینجوری بعد از هر تغییری توی درخت، اطلاعات از بین نمیره.
  • معکوس کردن در یک بازه. این عملیات هم شبیه قبلیه: باید یه پرچم بولین rev اضافه کنیم و وقتی زیردرخت گره فعلی باید معکوس بشه، اون رو true کنیم. "Push" کردن این مقدار یه کم پیچیده‌تره؛ ما بچه‌های این گره رو با هم جابجا می‌کنیم و این پرچم رو برای اونا true می‌کنیم.

اینم یه نمونه پیاده‌سازی از تریپ ضمنی با قابلیت معکوس کردن روی بازه. برای هر گره، یه فیلد به نام 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);
}

منابع برای مطالعه بیشتر

مسائل تمرینی