مثال Segment Tree مسئله UVA 12086

مقدمه
قبل از این داده ساختار Segment Tree را به صورت تئوری مورد بحث قرار دادیم ، امروز مسئله UVA 12086 - Potentiometers یا مقاومت متغییر که با استفاده از این ساختمان داده قابل حل میباشد را پیاده سازی میکنیم.

متن مسئله
PDF مسئله از اینجا قابل دریافت است ، خلاصه متن این است که N مقاومت متغییر روی یک خط قرار گرفتند ، و مقدار اولیه هریک را داریم ، باید به تعداد M دستور پاسخ بدهیم دو نوع دستور داریم
نوع اول : مقدار مقاومت x را به r تغییر بده
نوع دوم : مقاومت معادل r تا l را چاپ کن ، که معادل با جمع تک تک مقاومت های این بازه میباشد.

راه حل
ابتدا راه حل ساده یعنی پیاده سازی همین کار با دو حلقه تو در تو به نظر درست می آید اما مرتبه این الگوریتم O(NM) میباشد که با توجه اینکه N میتواند تا 200000 باشد ، و M نیز میتواند تا 200000 باشد بطور تقریبی میتوان حدس زد که این الگوریتم نیاز به زمان اجرای 400 ثانیه ای تنها برای یک تست دارد و نتیجه این ارسال بدون شک Time Limit Executed میباشد ، برنامه میبایست زیر 3 ثانیه تمامی دستورات تمام تست ها را پاسخ گو باشد.

همانطور که در ابتدا گفته شد با استفاده از Segment Tree میتوان راه حل ای از مرتبه O(MlogN + NlogN) نوشت که بسیار سریع و در محدوده زمانی مسئله پاسخ گو میباشد.
در هریک از سلول های Segment Tree مقدار مجموع مربوط به آن محدوده از بازه را نگهداری میکنیم ، در ابتدا باید هزینه Nlog(N) را برای ساخت بپردازیم و در ادامه برای بروز رسانی یک مقاومت نیاز به بروز رسانی log(N) سلول از Segment Tree هست و همچنین بدست آوردن مقدار یک بازه نیز با log(N) عملیات انجام میشود.

کد راه حل مسئله مقاومت های متغییر به زبان C++ با روش مطرح شده ، همانطور که مشخص است تابع build وظیفه ساخت ، تابع update وظیفه بروزرسانی ، و تابع getVal وظیفه بدست آوردن مقدار یک بازه در Segment Tree را بر عهده دارد.

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
#define Author "DemoVersion"

const int MaxN = 200000+10;
const int MaxST = 4 * MaxN;

void build(int arL,int arR,int SI,int st[],int ar[]){
    if(arL==arR){
    	st[SI]=ar[arL];
    	return;
    }
    int m=(arL+arR)/2;
    build(arL,m,SI*2,st,ar);
    build(m+1,arR,SI*2+1,st,ar);
    st[SI]=st[SI*2]+st[SI*2+1];
}
void update(int arL,int arR,int i,int oldval,int newval,int SI,int st[]){
    if(i<arL||arR<i)return;
    st[SI]=st[SI]-oldval+newval;
    if(arL==arR)return;
    int m=(arL+arR)/2;
    update(arL,m,i,oldval,newval,SI*2,st);
    update(m+1,arR,i,oldval,newval,SI*2+1,st);

}
int getVal(int arL,int arR,int L,int R,int SI,int st[]){
    if(arR<L||arL>R)return 0;
    if(L<=arL&&arR<=R){
        return st[SI];
    }
    int m=(arL+arR)/2;
    if(arL==arR)return 0;
    return getVal(arL,m,L,R,SI*2,st)+getVal(m+1,arR,L,R,SI*2+1,st);
}

int main(){
    string s;
    int Ar[MaxN],st[MaxST],n,i,u,v,t=0;
    while(cin>>n&&n){
    	if(t++)cout<<endl;
    	cout<<"Case "<<t<<":"<<endl;
    	for(i=0;i<n;i++)
    		cin>>Ar[i];
    	build(0,n-1,1,st,Ar);
    	while(cin>>s&&s!="END"){
    		if(s=="S"){
    			cin>>u>>v;
    			update(0,n-1,u-1,Ar[u-1],v,1,st);
    			Ar[u-1]=v;
    		}else{
    			cin>>u>>v;
    			cout<<getVal(0,n-1,u-1,v-1,1,st)<<endl;
    		}
    	}
    }
    return 0;
}