daily pastebin goal
20%
SHARE
TWEET

Segment Tree normal (2.0)

sak1b Dec 20th, 2017 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define mx 100005
  3. using namespace std;
  4.  
  5. int a[mx];
  6. int tree[mx*4];
  7.  
  8. void build_tree(int node,int b,int e)
  9. {
  10.     tree[node]=0;
  11.     if(b==e)
  12.     {
  13.         tree[node]=a[b];
  14.         return;
  15.     }
  16.     int left=node*2;
  17.     int right=node*2+1;
  18.     int mid=(b+e)/2;
  19.     build_tree(left, b ,mid);
  20.     build_tree(right, mid+1, e);
  21.  
  22.     tree[node]=tree[left]+tree[right];           ///only changes will be made here
  23.  
  24. }
  25.  
  26. int query(int node, int b, int e, int i, int j)
  27. {
  28.     if(i>e || j<b) /// gone in the right or left
  29.     {
  30.         return 0;
  31.     }
  32.     if(b>=i && e<=j) return tree[node];
  33.  
  34.     int left=node*2;
  35.     int right=node*2+1;
  36.     int mid=(b+e)/2;
  37.     int ret1=query(left, b ,mid,i,j);
  38.     int ret2=query(right, mid+1, e,i,j);
  39.    return ret1+ret2;                       ///only changes will be made here
  40. }
  41.  
  42. void update(int node, int b, int e, int i, int new_val)
  43. {
  44.     // i is the position that is being updated
  45.  
  46.     if(i>e || i<b) /// gone in the right or left
  47.     {
  48.         return;
  49.     }
  50.     if(b>=i && e<=i)
  51.     {
  52.         if(new_val==-1)
  53.         {
  54.              printf("%d\n",tree[node]);
  55.              tree[node]=0;
  56.         }
  57.  
  58.        else
  59.             tree[node]+=new_val;  //changes could be here as well
  60.         return;
  61.     }
  62.     int left=node*2;
  63.     int right=node*2+1;
  64.     int mid=(b+e)/2;
  65.  
  66.     if(i<=mid)
  67.     update(left, b ,mid,i,new_val);
  68.     else
  69.     update(right, mid+1, e,i,new_val);
  70.  
  71.     tree[node]= tree[left] + tree[right];           ///only changes will be made here
  72. }
  73.  
  74. int main()
  75. {
  76.   // freopen("input.txt","r",stdin);  //input query indexing 0 theke hole query te
  77.                                                                 //x+1 , y+1 korte hobe
  78.  
  79.     int n,t,cs=1,q;
  80.     int x,y;
  81.     int input;
  82.  
  83.     cin>>t;
  84.     while(t--)
  85.     {
  86.  
  87.     cin>>n>>q;
  88.     for(int i=1;i<=n;i++)
  89.     {
  90.         scanf("%d",&a[i]);
  91.     }
  92.  
  93.  
  94.     build_tree(1,1,n);
  95.  
  96.     printf("Case %d:\n",cs++);
  97.     while(q--)
  98.     {
  99.         scanf("%d",&input);
  100.         if(input==1)
  101.         {
  102.             scanf("%d",&x);
  103.  
  104.             update(1,1,n,x+1,-1);
  105.         }
  106.         else  if(input==2)
  107.         {
  108.             scanf("%d%d",&x,&y);
  109.  
  110.             update(1,1,n,x+1,y);
  111.         } else  if(input==3)
  112.         {
  113.              scanf("%d%d",&x,&y);
  114.             int z=query(1,1,n,x+1,y+1);
  115.             printf("%d\n",z);
  116.         }
  117.  
  118.     }
  119.  
  120.     }
  121.  
  122.  
  123.  
  124.     return 0;
  125. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top