树状数组
如题= =自用模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package 树状数组模板;  
  
import java.io.*;  
import java.util.*;  
  
public class Main {  
    static long[] sum;  //单点更新只需要一个数组 l-r的和为sum[l]-sum[r-1];
    static long[] c1;   //区间更新需要三个数组
    static long[] c2;  
  
    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);  
        PrintWriter pw = new PrintWriter(System.out);  
        while (sc.hasNext()) {  
            int n = sc.nextInt();  
            int m = sc.nextInt();  
            c1 = new long[n + 1];  
            c2 = new long[n + 1];  
            sum = new long[n + 1];  
            for (int i = 1; i <= n; i++) {  
                int t = sc.nextInt();  
                sum[i] = t;  
                sum[i] += sum[i - 1];  
            }  
            for (int o = 1; o <= m; o++) {  
                int t = sc.nextInt();  
  
                if (t == 1) {  
                    int x = sc.nextInt();  
                    int y = sc.nextInt();  
                    long add = sc.nextLong();  
                    add(x, add, n, c1);  
                    add(y + 1, -add, n, c1);  
                    add(x, x * add, n, c2);  
                    add(y + 1, -(y + 1) * add, n, c2);  
                } else {  
                    int start = sc.nextInt();  
                    int end = sc.nextInt();  
                    pw.println(regsum(start, end, sum, c1, c2));  
                }  
            }  
            pw.flush();  
        }  
    }  
  
    static void add(int k, long sum, int n, long[] tree) {  
        while (k <= n) {  
            tree[k] += sum;  
            k += k & -k;  
        }  
    }  
	//1-k的和查询
    static long sum(int k, long[] tree) {  
        long sum = 0;  
        while (k > 0) {  
            sum += tree[k];  
            k -= k & -k;  
        }  
        return sum;  
    }  
	//start-end区间和的查询
    static long regsum(int start, int end, long[] sum, long[] c1, long[] c2) {  
        return sum[end] - sum[start - 1] + sum(end, c1) * (end + 1) - sum(start - 1, c1) * start - sum(end, c2)  
                + sum(start - 1, c2);  
    }  
  
}