اُپدیا

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

این روش برای سرعت بخشیدن به حل بعضی از مسائل سگمنت تری استفاده می‌شود. در حالاتی که هر راس از درخت سگمنت تری لیستی از اعداد را در خود دارد و ما به دنبال این هستیم که به ازای هر راس بتوانیم بفهمیم چند تا از اعداد در بازه $[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
    }
}