sak1b

Segment Tree normal (2.0)

Dec 20th, 2017
158
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×