Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- long long int arr[1000006],tree[1000006];
- void treebuild(ll node,ll start,ll e)
- {
- if(start==e)
- {
- tree[node]=arr[e];
- return;
- }
- ll left=node*2;
- ll right=left+1;
- ll mid=(start+e)/2;
- treebuild(left,start,mid);
- treebuild(right,mid+1,e);
- tree[node]=tree[left]+tree[right];
- }
- void update(ll node,ll start,ll e,ll index,ll value)
- {
- if(index>e || index<start)
- return;
- if(start==e)
- {
- tree[node]=value;
- return;
- }
- ll left=node*2;
- ll right=left+1;
- ll mid=(start+e)/2;
- update(left,start,mid,index,value);
- update(right,mid+1,e,index,value);
- tree[node]=tree[left]+tree[right];
- }
- ll query(ll node,ll start,ll e,ll ranges,ll rangef)
- {
- if(ranges>e || rangef<start)
- return 0;
- if(start>=ranges &&rangef>=e)
- return tree[node];
- ll left=node*2;
- ll right=left+1;
- ll mid=(start+e)/2;
- ll ans1=query(left,start,mid,ranges,rangef);
- ll ans2=query(right,mid+1,e,ranges,rangef);
- return ans1+ans2;
- }
- int main()
- {
- ll n,i,j,test=0,q,ans,index,value,ranges,rangef;
- string s;
- while(cin>>n && n)
- {
- for(i=1;i<=n;i++)
- cin>>arr[i];
- treebuild(1,1,n);
- if(test)cout<<endl;
- cout<<"Case "<<++test<<":"<<endl;
- while(cin>>s)
- {
- if(s=="END")
- break;
- else if(s[0]=='S')
- {
- cin>>index>>value;
- arr[index]=value;
- update(1,1,n,index,value);
- }
- else
- {
- cin>>ranges>>rangef;
- ans=query(1,1,n,ranges,rangef);
- cout<<ans<<endl;
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement