Lightoj 1164 - Horrible Queries

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

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