fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long build(long long* tree,int i,int tl,int tr,int* a)
  6. {
  7.     if(tl==tr)
  8.     {
  9.         tree[i]=a[tl];
  10.         return tree[i];
  11.     }
  12.     int m=(tl+tr)/2; /// tl=0 tr=7 root m=3
  13.  
  14.     /// left: tl=0 tr=m=3
  15.     tree[2*i+1]=build(tree,2*i+1,tl,m,a);
  16.  
  17.     /// right: tl=m+1=4 tr=7
  18.     tree[2*i+2]=build(tree,2*i+2,m+1,tr,a);
  19.  
  20.     tree[i]=(tree[2*i+1]+tree[2*i+2]);
  21.  
  22.     return tree[i];
  23.  
  24. }
  25.  
  26. long long update(long long* tree,int i,int tl,int tr,int l,long long a) /// a[l]=11
  27. {
  28.     if(tl==tr && tl==l)
  29.     {
  30.         tree[i]=a;
  31.         return tree[i];
  32.     }
  33.     if(l<tl || l>tr)
  34.     {
  35.         return tree[i];
  36.     }
  37.     int m=(tl+tr)/2;
  38.     tree[2*i+1]=update(tree,2*i+1,tl,m,l,a);
  39.     tree[2*i+2]=update(tree,2*i+2,m+1,tr,l,a);
  40.     tree[i]=(tree[2*i+1]+tree[2*i+2]);
  41.     return tree[i];
  42. }
  43.  
  44. long long query(long long* tree,int i,int tl,int tr,int l,int r)
  45. {
  46.     /// full overlap
  47.     if(tl>=l && tr<=r)
  48.     {
  49.         return tree[i];
  50.     }
  51.  
  52.     /// no overlap
  53.     if(r<tl || l>tr)
  54.     {
  55.         return 0;
  56.     }
  57.  
  58.     /// partial overlap
  59.     int m=(tl+tr)/2;
  60.     int left=query(tree,2*i+1,tl,m,l,r);
  61.     int right=query(tree,2*i+2,m+1,tr,l,r);
  62.     return (left+right);
  63. }
  64.  
  65. int main()
  66. {
  67.     int n; cin >> n;
  68.      int q; cin >> q;
  69.     int a[n];
  70.     for(int i=0;i<n;i++) cin >> a[i];
  71.  
  72.     long long tree[4*n];
  73.     build(tree,0,0,n-1,a);
  74.  
  75.  
  76.  
  77.  
  78.     while(q--)
  79.     {
  80.         int ch; cin >> ch;
  81.         if(ch==2)
  82.         {
  83.             int l,r; cin >> l >> r;
  84.             l--,r--;
  85.             long long ans=query(tree,0,0,n-1,l,r);
  86.             cout << ans << endl;
  87.         }
  88.         else if(ch==1)
  89.         {
  90.             int l; cin >> l;
  91.             long long v;
  92.             cin>>v;
  93.             l--;
  94.            // a[l]=v;
  95.             update(tree,0,0,n-1,l,v);
  96.         }
  97.  
  98.     }
  99.  
  100.     return 0;
  101. }
  102.  
  103.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/CUdqBv
language:
C++ (gcc 8.3)
created:
9 hours 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!