fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define mx 100009
  4. typedef long long ll;
  5. ll BIT[mx];
  6. void initBIT(ll arr[],ll n){
  7.     memset(BIT,0,sizeof(BIT));
  8.     ll i,idx;
  9.     for(i=1;i<=n;i++){
  10.         ll value=arr[i-1];
  11.         idx=i;
  12.         while(idx<=n){
  13.            BIT[idx]+=value;
  14.            idx+=(idx&(-idx));
  15.         }
  16.     }
  17. }
  18. void update(ll idx,ll value,ll n){
  19.     idx=idx+1;
  20.     while(idx<=n){
  21.         BIT[idx]+=value;
  22.         idx+=(idx&(-idx));
  23.     }
  24. }
  25. ll query(ll r,ll n){
  26.     int idx=r+1;
  27.     int ans=0;
  28.     while(idx>0){
  29.         ans+=BIT[idx];
  30.         idx-=(idx&(-idx));
  31.     }
  32.     return ans;
  33. }
  34. int main()
  35. {
  36.     ll arr[mx],n,index,value,q,com,x,y,tc,cs=0;
  37.     scanf("%lld",&tc);
  38.     while(tc--){
  39.     scanf("%lld%lld",&n,&q);
  40.     for(int i=0;i<n;i++) scanf("%lld",&arr[i]);
  41.     initBIT(arr,n);
  42.     printf("Case %lld:\n",++cs);
  43.     while(q--){
  44.     scanf("%lld",&com);
  45.     if(com==1){
  46.         scanf("%lld",&index);
  47.         ll tmp=index-1;
  48.         ll ans=query(index,n)-query(tmp,n);
  49.         printf("%lld\n",ans);
  50.         update(index,-ans,n);
  51.     }
  52.     else if(com==2){
  53.         scanf("%lld%lld",&index,&value);
  54.         update(index,value,n);
  55.     }
  56.     else if(com==3){
  57.         scanf("%lld%lld",&x,&y);
  58.         printf("%lld\n",query(y,n)-query(--x,n));
  59.     }
  60.     }
  61.     }
  62.     return 0;
  63. }
  64.  
  65.  
Success #stdin #stdout 0s 16680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sIcaHD
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!