树状数组

 1 int lowbit(int x) {
 2     return x & -x;
 3 }
 4 
 5 void change1(int x,int d)     //单点修改
 6 {
 7     for (int i = x; i <= n; i += lowbit(i)) {
 8         c[i] += d;
 9     }
10 }
11 
12 int sum1(int x)     ///区间查询
13 {
14     if (!x) {
15         return 0;
16     }
17     int res = 0;
18     for (int i = x; i; i -= lowbit(i)) {
19         res += c[i];
20     }
21     return res;
22 }
23 
24 void change2(int x,int d)        //区间修改
25 {
26     for (int i=x;i;i-=lowbit(i)){
27         c[i]+=d;
28     }
29 }
30 
31 void sum2(int x)   //单点查询
32 {
33     if (!x) {
34         return 0;
35     }
36     int res;
37     for (int i = x; i <= n; i += lowbit(i)) {
38         res += c[i];
39     }
40     return res;
41 }
42 
43 
44 
45 
46 
47 
48 int main() {
49     for (int i=1;i<=n;i++) {
50         scanf("%d", &a[i]);
51         change3(c, i, a[i] - a[i - 1]);
52         change3(d, i, (a[i] - a[i - 1]) * (i - 1));
53     }
54     for (int i=1;i<=m;i++) {
55         scanf("%d", &x);
56         if (x == 1) {
57             scanf("%d%d%d", &a, &b, &c);
58             change3(c, a, c);
59             change3(c, b + 1, -c);
60             change3(d, a, (a - 1) * c);
61             change3(d, b + 1, -b * c);
62         } else {
63             scanf("%d%d", &a, &b);
64             t1 = sum3(c, a - 1) * (a - 1) - sum3(d, a - 1);
65             t2 = sum3(c, b) * b - sum3(d, b);
66             printf("%d
", t2 - t1);
67         }
68     }
69     scanf("%d", &n);
70     for (int i = 1; i <= n; i++) {
71         scanf("%d", &a);
72         change1(i, a);
73     }
74     for (int i = 1; i <= m; i++) {
75         scanf("%d%d%d", &a, &b, &c);
76         if (a == 1) {
77             change1(b, c);   //单点修改
78         } else {
79             printf("%d
", sum1(c) - sum1(b - 1));//区间查询
80         }
81     }
82 }