Segment Tree

یکی از پرکاربرد ترین داده ساختار های مورد استفاده در المپیاد کامپیوتر بی شک Segment Tree است. نوع درخت دودویی آن Full Binary Tree است.

با استفاده از این داده ساختار می توان جمع یک بازه از آرایه و بیشترین یا کمترین مقدار یک آرایه را بدست آورد.

ساختار

هر راس این درخت بیانگر یک بازه از آرایه مورد پرسش است. بچه های هر راس (اگر موجود باشد طبیعتاً دو تا است) بازه پدر خود را نصف می کنند یا به عبارت دیگر اگر بازه راسی \([Begin, End)\) باشد بازه دو پسر چپ و راست آن به ترتیب \([Begin, Middle)\) و \([Middle, End)\) است. راس های بدون بچه هم حاوی تک عضوی از آرایه است.

برای بهتر فهمیدن رابطه ی بین راس ها و بازه ها به شکل زیر نگاه کنید.

Segment Tree

در هر کدام از این راس ها یک اطلاعات مشخصی از بازه متناظر آن راس در آرایه در دسترس است که بسته به استفاده ما از این داده ساختار می تواند متفاوت باشد. برای نمونه اگر دنبال جمع یک بازه از آرایه هستیم هر کدام از راس ها در خود مجموع بازه متناظرشان را ذخیره می کنند.

برای درک بیشتر از این قسمت به شکل زیر نگاه کنید که چطور هر راس مقداری را ذخیره کرده.

Segment Tree

ارتفاع این درخت \(lg n\) و تعداد راسی که مورد استفاده قرار می دهد حداکثر \(2n\) است بنابراین شما با حافظه \(2n\) می توانید این داده ساختار را ذخیره کنید. لازم به ذکر است که بعضی افراد حافظه \(4n\) را در نظر می گیرند که بخاطر نوع پیاده سازی برای هر برگ درخت(راس های تک عضوی) دو بچه بدون هیچ مشخصه ای قرار می دهند که باعث می شود حافظه دو برابر شود.

برای شماره گذاری راس ها هم می توان به ریشه عدد یک داد و به بچه های راست و چپ هر راس به ترتیب \(2k\) و \(2k + 1\) داد.

الگوریتم

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

در ابتدا به ما یک آرایه داده شده و در هر مرحله از ما می خواهند که یا مقدار یک عضو آرایه را تغییر دهیم و یا جمع یک بازه را گزارش دهیم.

ساخت

برای حل ابتدا Segment Tree را از روی آرایه می سازیم. برای اینکار اول ساختار اصلی Segment Tree را می سازیم و بعد مقدار هر راس را برابر جمع مقدار بچه هایش می گذاریم و مقدار راس های تک عضوی را مقدار عضو متناظر می گذاریم.

void build(int u = 1, int ul = 0, int ur = n){
    if(ur - ul < 2){
        seg[u] = a[ul];
        return;
    }
    int mid = (ul + ur) / 2;
    build(u * 2, ul, mid);
    build(u * 2 + 1, mid, ur);
    seg[u] = seg[u * 2] + seg[u * 2 + 1];
}

تغییر دادن مقدار یک عضو

مقدار تمام راس هایی که بازه آن ها شامل این عضو می شود را تغییر می دهیم. توجه کنید که تعداد این بازه ها حداکثر برابر ارتفاع درخت است چرا که هر طبقه از درخت، آرایه را افراز می کند بنابراین در هر طبقه باید مقدار حداکثر یک راس تغییر کند بنابراین اردر این عملیات \(O(lg n)\) است.

void update(int i, int x, int u = 1, int ul = 0, int ur = n){
    seg[u] += x - a[i];
    if(ur - ul < 2){
        a[i] = x;
        return;
    }
    int mid = (ul + ur)/2;
    if(i < mid)
        update(i, x, u * 2, ul, mid);
    else
        update(i, x, u * 2 + 1, mid, ur);
}

گزارش دادن جمع یک بازه از آرایه

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

برای فهم بهتر فرض کنید \(F(u,ul,ur,l,r)\) تابع بازگشتی بالا باشد که با گرفتن راسی که روی آن هستیم و بازه این راس و بازه خواسته شده، جواب را به ما بدهد(با فرض اینکه بازه خواسته شده درون بازه راس u باشد) و \(sum[u]\) به معنای مقدار ذخیره شده در راس u باشد. خلاصه سه حالت بالا به صورت زیر می شود.

\[Middle = (ul + ur) / 2\]
\[(ul = l, ur = r) => F(u,ul,ur,l,r) = sum[u]\]
\[(r < Middle) => F(u,ul,ur,l,r) = F(2*u,ul,Middle,l,r)\]
\[(l > Middle) => F(u,ul,ur,l,r) = F(2*u,Middle,ur,l,r)\]
\[(l < Middle, Middle < r) => F(u,ul,ur,l,r) = F(2*u,ul,Middle,l,Middle) + F(2*u+1,Middle,ur,Middle,r)\]

اردر این عملیات \(O(lg n)\) است به این دلیل که در هر طبقه حداکثر ۴ راس در تابع بازگشتی مورد استفاده قرار می گیرند. برای اثبات کافیست توجه کنید که فقط راست ترین و چپ ترین راس های یک طبقه می توانند بچه های خود را صدا کنند و این یعنی در هر طبقه حداکثر ۴ راس صدا زده می شوند.

int sum(int l, int r, int u = 1, int ul = 0, int ur = n){
    if(x >= ur || ul >= y)return 0;
    if(x <= ul && ur <= y)return seg[u];
    int mid = (ul + ur) / 2;
    return sum(l, r, u * 2, ul, mid) + sum(l, r, u * 2 + 1, mid, ur);
}

انتشار با تاخیر (Lazy propagation)

فرض کنید در عملیات اول بجای تغییر یک مقدار، تغییر یک بازه مطرح باشد. به طور مثال به ما بگوید به بازه \(L\) تا \(R\) دو واحد اضافه کنیم. اگر بخواهیم تمامی عنصر های این بازه را عوض کنیم کار سخت است و تعداد عملیات هایمان بالا می رود. حال با استفاده از تکنیک انتشار با تاخیر می توانیم تعداد عملیات ها را پایین بیاوریم. به این صورت که به ازای هر راس یک مقدار دیگر هم در نظر می گیریم که بر فرض در آرایه Lazy ذخیره می شود. بازه داده شده برای تغییر را مانند روشی که در عملیات دوم برای بازه خواسته شده انجام دادیم افراز می کنیم به بازه های کوچک تر (روی درخت) و مقدار آرایه Lazy تمامی این راس ها (راس هایی که بازه روی آن ها افراز شده) را عوض می کنیم. و هر هنگام که در کل این الگوریتم بر روی راسی از درخت بودیم Lazy آن را به مقدار خود راس اضافه می کنیم و Lazy آن را به Lazy بچه هایش اضافه می کنیم و بعد آن را صفر می کنیم.

void upd(int u, int ul, int ur, int x){
    lazy[u] += x;
    seg[u] += (ur - ul) * x;
}
void shift(int u, int ul, int ur){
    int mid = (ul + ur) / 2;
    upd(u * 2, ul, mid, lazy[u]);
    upd(u * 2 + 1, mid, ur, lazy[u]);
    lazy[u] = 0;
}
void increase(int l, int r, int x, int u = 1, int ul = 0, int ur = n){
    if(l >= ur || ul >= r)return;
    if(l <= ul && ur <= r){
        upd(u, ul, ur, x);
        return;
    }
    shift(u, ul, ur);
    int mid = (ul + ur) / 2;
    increase(l, r, x, u * 2, ul, mid);
    increase(l, r, x, u * 2 + 1, mid, ur);
    seg[u] = seg[u * 2] + seg[u * 2 + 1];
}
int sum(int l, int r, int u = 1, int ul = 0, int ur = n){
    if(l >= ur || ul >= r)return 0;
    if(l <= ul && ur <= r)return seg[u];
    shift(u, ul, ur);
    int mid = (ul + ur) / 2;
    return sum(l, r, u * 2, ul, mid) + sum(l, r, u * 2 + 1, mid, ur);
}