code前端网数据结构学习笔记：二维树块
简介
二维树块，其实就是原来一维树块的每个点变成一个树块，一层层低位运算和维护做了一个矩形。简单来说，我们现在正在处理类似于树数组的二维矩阵上执行操作（即使您不习惯使用二维树数组，它也节省空间）。
const int N = 2e3 + 10;
int bit[N][N], n, m;
操作
我们考虑如何维护一维树块的维护间隔。
void add(int x, int d) {
for (int i = x; i <= n; i += i & -i) {
bit[i] += d;
}
}
其实，在进行单点操作时，我们考虑的是改变位置后影响了多少个位置。显然，我们可以使用 i += i & -i 来反转树数组处理的区间内的原始位置。对于二维树数组，我们实际上执行完全相同的操作。但这一次不同。如果一维树数组维护一维数组，则二维树数组维护二维数组。
我们现在考虑的是，改变位置后，影响到几个矩阵的值。当然，如上所述，二维树数组实际上是树数组中的树数组，也就是说每个节点都是一个树数组。因此，当我们对树形数组的第一维进行修改操作时，必须考虑到该位置的树形数组的修改会影响到树形数组中的多少个位置。当我们进入第二个维度时，我们考虑改变这个位置会影响多少个位置。可以看到，经过这样的操作，小矩形被一一修改，单次修改的总时间复杂度为�(log�log�)。
void add(int x, int y, int d) {
for (int i = x; i <= n; i += i & -i) {
for (int j = y; j <= m; j += j & -j) {
bit[i][j] += d;
}
}
}
查询操作呢？也是如此。对于一维树形数组，我们要查询范围[1,�]内的区间，即前缀之和。
int query(int x) {
int ret = 0;
for (int i = x; i > 0; i -= i & -i) {
ret += bit[x];
}
return ret;
}
我们已经提到过，单点修改操作本质上和一维树形数组是一样的，所以查询操作也是一样的，仍然要考虑需要添加多少个小矩形。当然，这次我们查询二维前缀之和，时间复杂度为�(log�log�)。
int query(int x, int y) {
int ret = 0;
for (int i = x; i > 0; i -= i & -i) {
for (int j = y; j > 0; j -= j & -j) {
ret += bit[i][j];
}
}
return ret;
}
一点加法，区间查询
LOJ #133. 1. 二维树数组：一点修改，区间查询
给定一个 �×� 零矩阵 �� ，必须执行以下操作：
- 1���：表示元素 ,�� � 增加了；
- 2����：表示查询所有子矩阵，位于左上角（�,�）和右下角（�,�）。数字的总和。
单点操作上面已经讲过了。二维树数组的一点操作和一维树数组是一样的，所以我们只能直接相加。
在区间查询中，我们可以仔细考虑一下使用二维树数组我们实际维护的是什么。事实上，我们使用一个二维树形数组来维护二维差分数组。查询时，我们寻找这个两位数差数组的前缀之和。所以，如果我们需要查询左上角为(�1,�1)，右下角为(�2,�2)的子矩阵中所有数字的总和，我们可以使用包含-排除原理为前缀数组的总和来计算这个小矩形的总和。
���=��2,�2−��1−1,�2−��2,�1−1+��1−1,�1−1
查询 操作为以下应该是：查询（x2，y2）-查询（x1-1，y2）-查询（x2，y1-1）+查询（x1-1，y1-1）。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<vector<ll>> bit(n + 1, vector<ll>(m + 1));
auto add = [&](int x, int y, ll d) {
for (int i = x; i <= n; i += i & -i) {
for (int j = y; j <= m; j += j & -j) {
bit[i][j] += d;
}
}
};
auto query = [&](int x, int y) {
ll ret = 0;
for (int i = x; i; i -= i & -i) {
for (int j = y; j; j -= j & -j) {
ret += bit[i][j];
}
}
return ret;
};
int opt;
while (cin >> opt) {
if (opt == 1) {
int x, y, d;
cin >> x >> y >> d;
add(x, y, d);
} else {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1) << '\n';
}
}
}
区间加法，一点查询
LOJ #134. 2. 二维树形数组：区间修改、一点查询
如果给定一个 �×� 零矩阵 � ，则必须执行以下操作：
- 1������：表示所有带有子矩阵左上角(�,�)和右下角(�,�)增加�;
- 2�� ：表示查询元素�、�的值。
现在我们的需求又发生了变化。需要改变的是区间，但这只是单点查询功能。
我们考虑单点查询问题。你还记得上一个问题吗？树块中可以查询的是某个位置的前缀和。因此，我们这里的一点查询仍然是查询一个前缀的总和。所需的答案是什么前缀和？当然，这是一个二维差分数组。 （接下来的�是原数组，�是差值数组）
��,�=�=1��=1���,�
因此，我们的目标是保留两个维差数组 ，使用二维树形数组来维护二维差数组。
但是区间修改操作呢？例如，这里是区间增量操作。由于我们当前的二维树数组保留了原数组的二维差分数组，因此我们在单点修改二维树数组，与修改差分数组类似，仍然应用包含排除原则。
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
std::cin >> n >> m;
std::vector bit(n + 1, std::vector<ll>(m + 1));
auto add = [&](int x, int y, ll d) {
for (int i = x; i <= n; i += i & -i) {
for (int j = y; j <= m; j += j & -j) {
bit[i][j] += d;
}
}
};
auto query = [&](int x, int y) {
ll ret = 0;
for (int i = x; i; i -= i & -i) {
for (int j = y; j; j -= j & -j) {
ret += bit[i][j];
}
}
return ret;
};
int opt;
while (std::cin >> opt) {
if (opt == 1) {
int x1, y1, x2, y2, d;
std::cin >> x1 >> y1 >> x2 >> y2 >> d;
add(x1, y1, d);
add(x1, y2 + 1, -d);
add(x2 + 1, y1, -d);
add(x2 + 1, y2 + 1, d);
} else {
int x, y;
std::cin >> x >> y;
std::cout << query(x, y) << '\n';
}
}
}
区间加法、区间查询
LOJ #135。 3. 二维树数组：区间修改、区间查询
如果我们在输入文件末尾得到一个大小为 �×� 的零矩阵，我们就必须继续。多重运算，有两种运算：
- 1 a b c d x，表示对左上角(�,�)和右下角(�,�)的所有子矩阵添加�；
- 2 a b c d，意思是要求左上角为(�,�)，右下角为(�,�)，即该顶点的子矩阵的所有数字之和。
现在我们的目标已经上升到了一个更高的层次。我们不仅要进行区间加法，还想查询原数组的区间和，而不是差数组的前缀和。不过我们的树数组还是维护了一个差分数组，不如线段树直观（当然这道题如果想用二维线段树还是可以MLE）。
我们用�作为原数组的前缀和，�作为原数组，�作为差数组。
现在我们必须开始思考 ��,� 对 ��,� 前缀之和的贡献有多大。我们可以知道 ��,�=Σ�=1�Σ�=1���,� ，即在单个位置 ��,� 对原始数组只有一个贡献。
现在我们添加总和：��,�=Σ�=1�Σ�=1���,�=Σ�=1�Σ1�=1�Σ�=1�Σ� �,� 。对于单个��,�，它对前缀和的贡献仍然是1，但如果��,�，我们仍然可以使用包含排除原则来考虑贡献。可以参考下图进行计算。
可以看出，在位置��,�处，对第一行�−1没有贡献，也对第一列�−1没有贡献，而从左上角(� ,�)开始右下角矩形 (�,�) 贡献 (�−�+1)(�−�+1)��,� 。也就是说，现在前缀和公式和差公式可以直接连接起来了。
��,�=Σ�=1�Σ�=1�(�−�+1)(�−�+1)��,�
但是，我们必须提前完成。事实上，我们刚才考虑的是查询前缀��,�的总和，即位置前缀(�,�)的总和（注意，这不是标题中的��,�，而是查询��,�） ，所以这两个参数不是我们在维护时可以更换的，因为这两个参数的变化是无规律的。但如果我们稍微简化一下，我们会发现整个公式中的“,”实际上是可以建议的，具体如下公式所示。
��,�=Σ�=1�Σ�=1��,�=Σ�=1�Σ�=1�Σ�=1, =1�Σ�=1�(�−� +1)(�−�+1)��,�=Σ�=1�Σ�=1�[��−�(�−1)−�( �−1)+(�−1)(� −1)]��,��=��Σ��=1�����=1���,��−����=1�����(=1�) ��−1)��,�−�Σ �=1�Σ�=1�(�−1)��,�+Σ�=1�Σ�=1�(�−1)(�−1) ��,�
现在可以看到，实际上只需 ��,�,(�−1)��,�,(�−1)��,�,(�−1)(� −1)��,� 就足够了。当我们要查询(�,�)的位置时，只需输入适当的系数即可。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2050;
int n, m;
ll a[N][N], b[N][N], c[N][N], d[N][N];
void add(int x, int y, ll v) {
for (int i = x; i <= n; i += i & -i) {
for (int j = y; j <= m; j += j & -j) {
a[i][j] += v;
b[i][j] += (x - 1) * v;
c[i][j] += (y - 1) * v;
d[i][j] += (x - 1) * (y - 1) * v;
}
}
}
ll query(int x, int y) {
ll ret = 0;
for (int i = x; i > 0; i -= i & -i) {
for (int j = y; j > 0; j -= j & -j) {
ret += x * y * a[i][j]
- y * b[i][j]
- x * c[i][j]
+ d[i][j];
}
}
return ret;
}
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m;
int opt;
while (cin >> opt) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (opt == 1) {
ll v;
cin >> v;
add(x1, y1, v);
add(x1, y2 + 1, -v);
add(x2 + 1, y1, -v);
add(x2 + 1, y2 + 1, v);
} else {
cout <<
query(x2, y2)
- query(x1 - 1, y2)
- query(x2, y1 - 1)
+ query(x1 - 1, y1 - 1)
<< '\n';
}
}
}版权声明
本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。
