一维树状数组
· 单点修改 + 单点查询：
直接使用即可
· 区间修改 + 单点查询：
另外维护一个维护前缀和的树状数组，查询时查询与原值相加即可。
· 区间修改 + 区间查询：
若要查询区间$[1, R]$的区间和，可推公式，其中$D[i]$表示差分数组：
$\sum\limits_{i=1}^R \sum\limits_{j=1}^i D[j]$
$= \sum\limits_{i=1}^R (R - i + 1) * D[i]$
$= (x + 1) \sum\limits_{i=1}^R D[i] - \sum\limits_{i=1}^R (i * D[i])$
此时维护$\sum D[i]$及$\sum (i * D[i])$就好了。
二维树状数组
· 单点修改 + 单点查询：
二维树状数组就是在一维的基础上维护一个矩阵，直接维护即可。
· 区间修改 + 单点查询：
由$Sum[i][j] = Sum[i - 1][j] + Sum[i][j - 1] - Sum[i - 1][j - 1] + a[i][j]$得到启发，可以维护形似$a[i][j] -> a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1]$的差分数组，加如下代码即可：
void Add_Main (int x1, int y1, int x2, int y2, int delta) { Add (x1, y1, delta); Add (x2 + 1, y1, - delta); Add (x1, y2 + 1, - delta); Add (x2 + 1, y2 + 1, delta); }
· 区间修改 + 区间查询：
推公式，可以由每个二元组$(x, y)$的出现次数得：
$\sum\limits_{x=1}^n\sum\limits_{y=1}^m\sum\limits_{i=1}^x\sum\limits_{j=1}^yD[i][j]$
$= \sum\limits_{x=1}^n\sum\limits_{y=1}^m D[x][y] (n - x + 1) (m - y + 1)$
$= \sum\limits_{x=1}^n\sum\limits_{y=1}^m (D[x][y] (n + 1) (m + 1) - D[x][y] (n + 1) * y - D[x][y] (m + 1) * x + D[x][y] * x * y)$
同一维树状数组的区间修改 + 区间查询，维护四个二维树状数组即可。
· 完整代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 typedef long long LL; 8 9 const int MAXN = 2048 + 10; 10 11 int N, M; 12 13 char opt[5]; 14 15 int lowbit (int x) { 16 return x & (- x); 17 } 18 19 int Tree1[MAXN][MAXN]= {0}; 20 int Tree2[MAXN][MAXN]= {0}; 21 int Tree3[MAXN][MAXN]= {0}; 22 int Tree4[MAXN][MAXN]= {0}; 23 24 void Add (int x, int y, int delta) { 25 int tx = x, ty = y; 26 while (x <= N) { 27 y = ty; 28 while (y <= M) { 29 Tree1[x][y] += delta; 30 Tree2[x][y] += ty * delta; 31 Tree3[x][y] += tx * delta; 32 Tree4[x][y] += tx * ty * delta; 33 y += lowbit (y); 34 } 35 x += lowbit (x); 36 } 37 } 38 39 void Add_Main (int x1, int y1, int x2, int y2, int delta) { 40 Add (x1, y1, delta); 41 Add (x2 + 1, y1, - delta); 42 Add (x1, y2 + 1, - delta); 43 Add (x2 + 1, y2 + 1, delta); 44 } 45 46 int Query (int x, int y) { 47 int tx = x, ty = y; 48 int cnt = 0; 49 while (x >= 1) { 50 y = ty; 51 while (y >= 1) { 52 cnt += (tx + 1) * (ty + 1) * Tree1[x][y]; 53 cnt -= (tx + 1) * Tree2[x][y]; 54 cnt -= (ty + 1) * Tree3[x][y]; 55 cnt += Tree4[x][y]; 56 y -= lowbit (y); 57 } 58 x -= lowbit (x); 59 } 60 61 return cnt; 62 } 63 64 int Query_Main (int x1, int y1, int x2, int y2) { 65 return Query (x2, y2) - Query (x2, y1 - 1) - Query (x1 - 1, y2) + Query (x1 - 1, y1 - 1); 66 } 67 68 int getnum () { 69 int num = 0; 70 char ch = getchar (); 71 int flag = 0; 72 73 while (! isdigit (ch)) { 74 if (ch == '-') 75 flag = 1; 76 ch = getchar (); 77 } 78 while (isdigit (ch)) 79 num = (num << 3) + (num << 1) + ch - '0', ch = getchar (); 80 81 return flag ? - num : num; 82 } 83 84 int main () { 85 scanf ("%s", opt + 1); 86 N = getnum (), M = getnum (); 87 88 while (~ scanf ("%s", opt + 1)) { 89 if (opt[1] == 'L') { 90 int x1, y1, x2, y2; 91 int delta; 92 x1 = getnum (), y1 = getnum (), x2 = getnum (), y2 = getnum (); 93 delta = getnum (); 94 95 Add_Main (x1, y1, x2, y2, delta); 96 } 97 else { 98 int x1, y1, x2, y2; 99 x1 = getnum (), y1 = getnum (), x2 = getnum (), y2 = getnum (); 100 101 int ans = Query_Main (x1, y1, x2, y2); 102 printf ("%d\n", ans); 103 } 104 } 105 106 return 0; 107 } 108 109 /* 110 X 4 4 111 L 1 1 3 3 2 112 L 2 2 4 4 1 113 k 2 2 3 3 114 */