fork(1) download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<string.h>
  4. using namespace std;
  5. #define ll long long int
  6. int n;
  7. ll tree[1000009],a[200009],c[200009];
  8. void update(int idx,int val)
  9. {
  10.     while(idx<=n)
  11.     {
  12.         tree[idx]+=val;
  13.         idx+=(idx & -idx);
  14.     }
  15. }
  16. long long int read(int i,int j)
  17. {
  18.     long long s1=0,s2=0;
  19.     while(i>0)
  20.     {
  21.         s1+=tree[i];
  22.         i-=(i & -i);
  23.     }
  24.     while(j>0)
  25.     {
  26.         s2+=tree[j];
  27.         j-=(j & -j);
  28.     }
  29.     return s2-s1;
  30. }
  31. int main()
  32.  {
  33.      int i,a1,b1,k;
  34.      int cs=0;
  35.      //char chare;
  36.      while(1)
  37.      {
  38.          scanf("%d",&n);
  39.          if(n==0)
  40.             break;
  41.             //getchar();
  42.             //cin>>chare;
  43.  
  44.      memset(c,0,sizeof(c));
  45.      memset(tree,0,sizeof(tree));
  46.      char s[90];
  47.      cout<<"Case "<<++cs<<":"<<endl;
  48.  
  49.      //string s;
  50.      for(i=1;i<=n;i++)
  51.      {
  52.          scanf("%lld",&a[i]);
  53.          //cin>>chare;
  54.          //getchar();
  55.          c[i]=c[i-1]+a[i];
  56.          k=(i-i^(i&(i-1)));
  57.          //cout<<i<<" "<<k<<" ";
  58.          tree[i]=c[i]-c[k];//BIT
  59.          //cout<<tree[i]<<endl;
  60.  
  61.      }
  62.  
  63.      char ch;
  64.  
  65.      getchar();
  66.  
  67.      while(1)
  68.      {
  69.          gets(s);
  70.          //getchar();
  71.          if(s[0]=='E')
  72.             break;
  73.         //cin>>chare;
  74.         sscanf(s,"%c %d %d",&ch,&a1,&b1);
  75.         if(ch=='S')
  76.         {
  77.             update(a1,b1-a[a1]);
  78.             a[a1]=b1;
  79.         }
  80.         else
  81.         {
  82.             if(a1>b1)
  83.                 swap(a1,b1);
  84.             printf("%lld\n",read(a1-1,b1));
  85.  
  86.         }
  87.      }
  88.      cout<<endl;
  89.      }
  90.      return 0;
  91.  }
  92.  
Success #stdin #stdout 0s 13792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dQxm7e
language:
C++ (gcc 8.3)
created:
11 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!