Advertisement
Saleh127

UVA 12086 / Live Archive 2191 - Segment Tree

Oct 25th, 2021
994
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5. ll a[200005];
  6. ll tree[800005];
  7.  
  8. void treeconstruct(ll node,ll b,ll e)
  9. {
  10.  
  11.     if(b==e)
  12.     {
  13.         tree[node]=a[b];
  14.         return;
  15.     }
  16.  
  17.     ll left = node*2;
  18.     ll right = node*2 + 1ll;
  19.  
  20.     ll mid=(b+e)/2;
  21.  
  22.     treeconstruct(left,b,mid);
  23.     treeconstruct(right,mid+1,e);
  24.  
  25.     tree[node]=tree[left]+tree[right];
  26.  
  27. }
  28.  
  29. void update(ll node,ll b,ll e,ll i,ll newv)
  30. {
  31.     if(i>e || i<b) return;
  32.  
  33.     if(b==e)
  34.     {
  35.         tree[node]=newv;
  36.         return;
  37.     }
  38.  
  39.     ll left = node*2;
  40.     ll right = node*2 + 1ll;
  41.  
  42.     ll mid=(b+e)/2;
  43.  
  44.     update(left,b,mid,i,newv);
  45.  
  46.     update(right,mid+1,e,i,newv);
  47.  
  48.     tree[node]=tree[left]+tree[right];
  49.  
  50. }
  51.  
  52. ll queries(ll node,ll b,ll e,ll i,ll j)
  53. {
  54.     if(i>e || j<b) return 0;
  55.  
  56.     if(b>=i && e<=j) return tree[node];
  57.  
  58.  
  59.     ll left = node*2;
  60.     ll right = node*2 + 1ll;
  61.  
  62.     ll mid=(b+e)/2;
  63.  
  64.     ll x=queries(left,b,mid,i,j);
  65.  
  66.     ll y=queries(right,mid+1,e,i,j);
  67.  
  68.     return x+y;
  69.  
  70. }
  71.  
  72. int main()
  73. {
  74.     ios_base::sync_with_stdio(0);
  75.     cin.tie(0);
  76.     cout.tie(0);
  77.  
  78.  
  79.     ll n,q,ff=0;
  80.  
  81.     while(cin>>n)
  82.     {
  83.         ll m,i,j,k,l;
  84.  
  85.         if(n==0) break;
  86.  
  87.  
  88.         if(ff) cout<<endl;
  89.         ff++;
  90.  
  91.         //memset(tree,0,sizeof tree);
  92.  
  93.         for(i=1; i<=n; i++)
  94.         {
  95.            cin>>a[i];
  96.         }
  97.  
  98.         treeconstruct(1ll,1ll,n);
  99.  
  100.         cout<<"Case "<<ff<<":"<<endl;
  101.  
  102.         string c;
  103.         while(cin>>c)
  104.         {
  105.             if(c=="END") break;
  106.  
  107.             else if(c[0]=='S')
  108.             {
  109.                 cin>>j>>k;
  110.  
  111.                 update(1ll,1ll,n,j,k);
  112.             }
  113.             else if(c[0]=='M')
  114.             {
  115.                  cin>>j>>k;
  116.                  m=queries(1ll,1ll,n,j,k);
  117.                  cout<<m<<endl;
  118.             }
  119.         }
  120.  
  121.     }
  122.  
  123.     return 0;
  124. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement