• API
• FAQ
• Tools
• Archive
daily pastebin goal
56%
SHARE
TWEET

# Segment Tree normal (2.0)

sak1b Dec 20th, 2017 77 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.

Top