Lightoj 1112 - Curious Robin Hood

http://lightoj.com/volume_showproblem.php?problem=1112

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define mx 100001
4. int arr[mx];
5. int tree[mx * 3];
6. void init(int node, int b, int e)
7. {
8.     if (b == e) {
9.         tree[node] = arr[b];
10.         return;
11.     }
12.     int Left = node * 2;
13.     int Right = node * 2 + 1;
14.     int mid = (b + e) / 2;
15.     init(Left, b, mid);
16.     init(Right, mid + 1, e);
17.     tree[node] = (tree[Left]+ tree[Right]);
18. }
19. int query(int node, int b, int e, int i, int j)
20. {
21.     if (i > e || j < b)
22.         return 0; //বাইরে চলে গিয়েছে
23.     if (b >= i && e <= j)
24.         return tree[node]; //রিলেভেন্ট সেগমেন্ট
25.     int Left = node * 2; //আরো ভাঙতে হবে
26.     int Right = node * 2 + 1;
27.     int mid = (b + e) / 2;
28.     int p1 = query(Left, b, mid, i, j);
29.     int p2 = query(Right, mid + 1, e, i, j);
30.     return (p1+p2); //বাম এবং ডান পাশের যোগফল
31. }
32.  
33. void update(int node, int b, int e, int i, int newvalue)
34. {
35.     if (i > e || i < b)
36.         return; //বাইরে চলে গিয়েছে
37.     if (b >= i && e <= i) { //রিলেভেন্ট সেগমেন্ট
38.         tree[node] = newvalue; //নতুন মান বসিয়ে দিলাম
39.         return;
40.     }
41.     int Left = node * 2; //আরো ভাঙতে হবে
42.     int Right = node * 2 + 1;
43.     int mid = (b + e) / 2;
44.     update(Left, b, mid, i, newvalue);
45.     update(Right, mid + 1, e, i, newvalue);
46.     tree[node] = tree[Left] + tree[Right];
47. }
48.  
49. int main()
50. {
51.     int ts;
52.     scanf("%d", &ts);
53.     for(int p = 1; p <=ts; p++){
54.     printf("Case %d:\n", p);
55.     int n, q;
56.     scanf("%d%d", &n, &q);
57.     for(int i = 1; i <= n; i++) scanf("%d", &arr[i]);  
58.         init(1, 1, n);
59.         for(int i = 0; i<q ; i++){
60.         int a;
61.         scanf("%d", &a);
62.         if(a == 1){
63.             int p;
64.             scanf("%d", &p);
65.             printf("%d\n",query(1, 1, n, p+1, p+1));
66.             update(1, 1, n, p+1, 0);
67.         }
68.         else if(a == 2){
69.             int p, v;
70.             scanf("%d%d", &p, &v);
71.             update(1, 1, n, p+1, query(1, 1, n, p+1, p+1)+v);
72.         }
73.         else if(a == 3){
74.             int c, b;
75.             scanf("%d%d", &c, &b);
76.             printf("%d\n",query(1, 1, n, c+1, b+1));   
77.         }
78.         //for(int i = 1; i <=n; i++) cout<<arr[i]<<" ";
79.         //cout<<endl;
80.     }
81.     }
82.     return 0;
83. }