差分进阶
1.二维差分
差分的前缀和数组是原数组。
由一维差分的应用（将区间加改为单点加操作）我们可以扩展到二维差分的应用，就是把将矩阵的 \((a,b)\) 到 \((c,d)\) 的区块加改为四个点的加操作。
即：\(D[a,b]+=delta; D[c+1,b]-=delta; D[a,d+1]-=delta; D[c+1, d+1] += delta\)。
看图理解：（若原数组一个方块 \(+delta\)，其前缀和数组中右下的每一个方块都会 \(+delta\)。）
讲完修改操作，但问题是先得有一个矩阵啊！怎么构造呢？我们这里使用的方法是插入法。
假设原矩阵为 \(\{0\}\)，那么差分矩阵也为 \(\{0\}\)。然后按顺序（不影响的顺序，就是从左到右从上到下）对每一个点 \((i,j)\) 都进行插入操作：\(\operatorname{insert}(i, j),(i, j)\)。
要输出原数组的时候，只需要进行一次二位前缀和即可。
例题：https://www.luogu.com.cn/problem/P4514
（这个题目，光用这个还过不去（\(query\) 操作的时间是 \(O(qnm)\)），需要使用二维树状数组优化前缀和的计算时间复杂度。）
\(O(qnm)\) 代码：
#include
using namespace std;
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair pii;
int n, m;
int D[2050][2050], A[2050][2050], s[2050][2050];
/*
L a b c d delta —— 代表将 (a,b),(c,d)(a,b),(c,d) 为顶点的矩形区域内的所有数字加上 deltadelta。
k a b c d —— 代表求 (a,b),(c,d)(a,b),(c,d) 为顶点的矩形区域内所有数字的和。
*/
void insert(int a, int b, int c, int d, int delta) {
D[a][b] += delta; D[c + 1][b] -= delta;
D[a][d + 1] -= delta; D[c + 1][d + 1] += delta;
}
void query(int a, int b, int c, int d) {
//求出原数组
f(i, 1, n)
f(j, 1, m)
A[i][j] = A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1] + D[i][j];
f(i, 1, n)
f(j, 1, m)
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + A[i][j];
cout << s[c][d] - s[a - 1][d] - s[c][b - 1] + s[a - 1][b - 1] << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
char op; cin >> op;
cin >> n >> m;
/*若有初始值
f(i, 1, n)
f(j, 1, m)
insert(i, j, i, j, a[i][j]);*/
while(cin >> op && op != EOF) {
if(op == 'L') {
int a, b, c, d, delta; cin >> a >> b >> c >> d >> delta;
insert(a, b, c, d, delta);
}
else {
int a, b, c, d; cin >> a >> b >> c >> d;
query(a, b, c, d);
}
}
return 0;
}
树状数组统计差分数组形式下原数组的前缀和
假设有一个数组 \(A\)，我们只维护它的差分数组 \(D\)，有 \(q\) 次 \(D\) 的单点修改操作（也就是 \(A\) 的区间加操作）。要求前缀和数组 \(S\)。暴力解法是对于每一个 \(q\) 做一次前缀和，时间复杂度 \(O(qn)\)。
我们考虑分解：
\(A[1] = D[1];\)
\(A[2] = D[1] + D[2];\)
\(A[3] = D[1] + D[2] + D[3];\)
\(A[4] = D[1] + D[2] + D[3] + D[4];\)
考虑统计 \(D[x]\) 出现的次数，那么 \(S[4]=\sum\limits_{i = 1}^{4} A_i\)
\(~~~~~~=4D[1] + 3D[2] + 2D[3] + D[4]\)
\(~~~~~~=5(D[1] + D[2] + D[3] + D[4]) - (D[1] + 2D[2] + 3D[3] + 4D[4])\)。
化为第三步的时候，应该可以看出来了：这个东西可以通过维护 \(D[x]\) 和 \(xD[x]\) 的前缀和求出。（第二步的形式，系数是不随统计的末位置 \(i\) 固定的，我们需要把系数变形成固定的）
暴力维护前缀和，时间复杂度没有优化，为 \(O(qn)\)。但使用树状数组维护前缀和，可以将时间复杂度优化至 \(O(q \log n)\)。
例题：https://www.luogu.com.cn/problem/P3372
AC 代码：
#include
using namespace std;
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair pii;
int n, m;
ll d[100010], id[100010], a[100010];
ll di[100010], idi[100010];
int lowbit(int x) {
return x & -x;
}
void add(int x, int k, int tnum) {
if(tnum == 1) {
//add di
while(x <= n) {
di[x] += k;
x += lowbit(x);
}
}
else {
//add idi
while(x <= n) {
idi[x] += k;
x += lowbit(x);
}
}
}
ll query(int x, int tnum) {
ll ans = 0;
if(tnum == 1) {
//add di
while(x > 0) {
ans += di[x];
x -= lowbit(x);
}
}
else {
//add idi
while(x > 0) {
ans += idi[x];
x -= lowbit(x);
}
}
return ans;
}
ll s(ll x) {
return (x + 1) * query(x, 1) - query(x, 2);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
f(i, 1, n) {
cin >> a[i]; d[i] = a[i] - a[i - 1]; id[i] = d[i] * i;
add(i, d[i], 1); add(i, id[i], 2);
}
//1 x y k：将区间 [x, y][x,y] 内每个数加上 kk。
//2 x y：输出区间 [x, y][x,y] 内每个数的和。
f(i, 1, m) {
int op; cin >> op;
if(op == 1) {
int x, y, k; cin >> x >> y >> k;
add(x, k, 1); add(y + 1, -k, 1);
add(x, x * k, 2); add(y + 1, -(y + 1) * k, 2);
}
else {
int x, y; cin >> x >> y;
cout << s(y) - s(x - 1) << endl;
}
}
return 0;
}
推广到二维情况怎么做？
依然借鉴前面的方法，将 \(S[a][b]\) 表示出来：
\(\sum\limits_{i = 1}^{a} \sum\limits_{j = 1}^{b}\sum\limits_{x = 1}^{i}\sum\limits_{y = 1}^{j} D[x][y]\)
依然举例子，统计 \(d[x][y]\) 的出现次数：
\(S[2][3] = A[1][1] + A[1][2] + A[1][3] + A[2][1] + A[2][2] + A[2][3]\)
\(A[1][1] = D[1][1]\)
\(A[1][2] = D[1][1] + D[1][2]\)
\(A[1][3] = D[1][1] + D[1][2] + D[1][3]\)
\(A[2][1] = D[1][1] + D[2][1]\)
\(A[2][2] = D[1][1] + D[1][2] + D[2][1] + D[2][2]\)
\(A[2][3] = D[1][1] + D[1][2] + D[1][3] + D[2][1] + D[2][2] + D[2][3]\)
可以发现，\(D[x][y]\) 会统计 \((a-x+1) \times (b-y+1)\) 次。
那么 \(S[a][b] = \sum\limits_{i = 1}^{a} \sum\limits_{j = 1}^{b} (a-i+1)(b-j+1)D[i][j]\)
\(~~~~~~~~~~~~~~~~~~=\sum\limits_{i = 1}^{a} \sum\limits_{j = 1}^{b} ij D[i][j] + (-b-1)iD[i][j] + (-a-1)jD[i][j] + (ab+a+b+1)D[i][j]\)
可以使用树状数组维护。
维护过程中，四个树状数组最好合在一起维护，因为分开会错。这是 AC 代码：
#include
using namespace std;
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair pii;
int n, m;
int td[2050][2050], tdi[2050][2050], tdj[2050][2050], tdij[2050][2050];
/*
L a b c d delta —— 代表将 (a,b),(c,d)(a,b),(c,d) 为顶点的矩形区域内的所有数字加上 deltadelta。
k a b c d —— 代表求 (a,b),(c,d)(a,b),(c,d) 为顶点的矩形区域内所有数字的和。
*/
int lowbit(int x) {
return x & (-x);
}
void add(int x, int y, int k) {
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j))
{
td[i][j]+=k;
tdi[i][j]+=k*x;
tdj[i][j]+=k*y;
tdij[i][j]+=k*x*y;
}
}
void insert(int a, int b, int c, int d, int delta) {
add(a, b, delta);
add(a, d + 1, -delta);
add(c + 1, b, -delta);
add(c + 1, d + 1, delta);
}
int query(int x, int y) {
int ans = 0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
ans+=((x+1)*(y+1)* td[i][j]-(y+1)*tdi[i][j]-(x+1)*tdj[i][j]+tdij[i][j]);
return ans;
}
void q(int a, int b, int c, int d) {
cout << query(c, d) - query(a - 1, d) - query(c, b - 1) + query(a - 1, b - 1) << endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
char op;
cin >> op;
cin >> n >> m;
while(cin >> op && op != EOF) {
if(op == 'L') {
int a, b, c, d, delta; cin >> a >> b >> c >> d >> delta;
insert(a, b, c, d, delta);
}
else {
int a, b, c, d; cin >> a >> b >> c >> d;
q(a, b, c, d);
}
}
return 0;
}