المپدیا

روش انتشار آبشاری

این روش برای سرعت بخشیدن به حل بعضی از مسائل سگمنت تری استفاده می شود. در حالاتی که هر راس از درخت سگمنت تری لیستی از اعداد را در خود دارد و ما به دنبال این هستیم که به ازای هر راس بتوانیم بفهمیم چند تا از اعداد در بازه $[l,r]$ وجود دارد استفاده می شود.

الگوریتم بدیهی

در این حالت می خواهیم بدانیم در بازه $[X,Y]$ از راس ها چند عدد در بازه ی $[L,R]$ وجود دارد. برای این کار ابتدا با توجه به درخت سگمنت به logn راس تجزیه می کنیم و به ازای هر کدام از آن ها یک بار بر روی لیست آن راس باینری سرچ می زنیم و تعداد اعداد بازه $[L,R]$ را برای آن راس به دست می آوریم. چون به ازای هر کدام از $logn$ بازه یک بار الگوریتم باینری سرچ را انجام می دهیم در مجموع هزینه از $O(log^2n)$ است.

الگوریتم انتشار آبشاری

در این روش در هنگام ساخت درخت سگمنت تری به ازای هر عدد در راسی از درخت سگمنت تری با استفاده از یک بار باینری سرچ می توان فهمید که بزرگ ترین عددی که کوچک تر مساوی این عدد است و در فرزند سمت چپ این راس قرار دارد را پیدا می کنیم. همین کار را برای فرزند سمت راست آن راس نیز انجام می دهیم. حال وقتی بخواهیم بدانیم چند عدد در بازه ی $[L,R]$ وجود دارد یک بار بر روی راس ریشه سگمنت تری باینری سرچ را انجام می دهیم و هنگامی که می خواهیم به یکی از فرزندان این راس برویم با توجه به اطلاعاتی که در هنگام ساخت درخت سگمنت تری داریم بدون استفاده از باینری سرچ بازه ای از لیست اعداد آن راس که بین $[L,R]$ است را پیدا کنیم. در نتیجه هزینه به ازای هر راس $O(1)$ خواهد شد و در کل برای $logn$ راس از $O(logn)$ خواهد بود.

void build_segment_tree(int l,int r,int num){
    if(r - l <= 1){
        vec[num].push_back(a[l]);
        return;
    }
    int mid = (l + r)/2;
    build_segment_tree(l,mid,num*2+0);
    build_segment_tree(mid,r,num*2+1);
    vec[num] = merge(vec[num*2], vec[num*2+1]); // merge two vectors of childs
    for(int i=0; i < vec[num].size() ; i++){
        l[num][i] = binary_search(vec[num][i], vec[num*2+0]); // find left bound with binary search
        r[num][i] = binary_search(vec[num][i], vec[num*2+1]); // find right bound with binary search
    }
}