fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxn=100005;
  5.  
  6. int arr[maxn];
  7. int tree[4*maxn];
  8.  
  9. void build(int node,int left,int right){
  10. 	if(left==right){
  11. 		tree[node] = arr[left];
  12. 	}
  13. 	else {
  14. 	   int mid = (left+right)/2;
  15. 	   build(2*node,left,mid);
  16. 	   build(2*node+1,mid+1,right);
  17. 	   tree[node] = tree[2*node] + tree[2*node+1];
  18. 	}
  19. }
  20.  
  21. void update(int node,int left,int right,int idx,int val){
  22. 	if(left==right){
  23.         arr[idx]+=val;
  24. 		tree[node] = val;
  25. 	}
  26. 	else {
  27. 	   int mid = (left+right)/2;
  28. 	   if(idx>=left && idx<=mid)
  29. 	      update(2*node,left,mid,idx,val);
  30. 	   else
  31. 	      update(2*node+1,mid+1,right,idx,val);
  32. 	tree[node] = tree[2*node] + tree[2*node+1];
  33. 	}
  34. }
  35.  
  36. int query(int node,int left,int right,int x,int y){
  37. 	if(left > y || right < x)
  38. 		return 0;
  39. 	if(left >= x && right<= y)
  40. 		return tree[node];
  41. 	int mid = (left+right)/2;
  42. 	return (query(2*node,left,mid,x,y) + query(2*node+1,mid+1,right,x,y));
  43. }
  44.  
  45. int main(){
  46.    char t;
  47.    int n,q,a,b;
  48.    cin>>n>>q;
  49.    for(int i=0;i<n;i++)
  50.    	 cin>>arr[i];
  51.    build(1,0,n-1);
  52.    while(q--){
  53.    	 cin>>t>>a>>b;
  54.    	 if(t=='q')
  55.    	    cout << query(1,0,n-1,a-1,b-1) << endl;
  56.      else
  57.         update(1,0,n-1,a-1,b);
  58.    }
  59. return 0;
  60. }
Success #stdin #stdout 0s 17192KB
comments (?)
stdin
copy 
6 5
10 11 12 13 14 15
q 1 6
q 2 4
q 3 5
u 4 9
q 1 6
stdout
copy 
75
36
39
71
https://ideone.com/O2ejBL
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!