fork(2) 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.      while(1)
  36.      {
  37.          scanf("%d",&n);
  38.          if(n==0)
  39.             break;
  40.             cout<<"Case "<<++cs<<":"<<endl;
  41.      memset(c,0,sizeof(c));
  42.      memset(tree,0,sizeof(tree));
  43.      char s[90];
  44.      //string s;
  45.      for(i=1;i<=n;i++)
  46.      {
  47.          scanf("%lld",&a[i]);
  48.          c[i]=c[i-1]+a[i];
  49.          k=(i-i^(i&(i-1)));
  50.          tree[i]=c[i]-c[k];//BIT
  51.          //cout<<tree[i]<<" ";
  52.      }
  53.      //cin>>s;
  54.     /*for(i=1;i<=n;i++)
  55.      {
  56.          k=(i-i^(i&(i-1)));
  57.          //cout<<i<<" "<<k<<" ";
  58.          cout<<tree[i]<<" ";
  59.      }*/
  60.      char ch;
  61.  
  62.      getchar();
  63.  
  64.      while(1)
  65.      {
  66.          gets(s);
  67.          //cin>>s;
  68.          if(s[0]=='E')
  69.             break;
  70.  
  71.         sscanf(s,"%c %d %d",&ch,&a1,&b1);
  72.         if(ch=='S')
  73.         {
  74.  
  75.             update(a1,b1-a[a1]);
  76.             a[a1]=b1;
  77.         }
  78.         else
  79.         {
  80.             if(a1>b1)
  81.                 swap(a1,b1);
  82.             printf("%lld\n",read(a1-1,b1));
  83.         }
  84.      }
  85.      }
  86.      return 0;
  87.  }
  88.  
Success #stdin #stdout 0s 13832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eDDL2i
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!