题目描述
给定一个 的零矩阵，支持两种操作：
- 单点修改：将 位置上的值增加 。
- 子矩阵求和：查询左上角 ，右下角 的子矩阵内所有数的和。
，操作总数 。
解法分析
这是一道二维树状数组（Fenwick Tree）的模板题。树状数组可以高效地维护前缀和，二维树状数组则用于维护二维前缀和。
二维树状数组原理
设 表示以 为右下角，宽度为 ，高度为 的子矩阵的和。其中 。
那么，对于单点修改 增加 ，我们需要更新所有满足 且 的 ，即：
for (int i = x; i <= n; i += i & -i)
for (int j = y; j <= m; j += j & -j)
C[i][j] += k;
时间复杂度 。
对于查询前缀和 ，我们可以累加所有 ，其中 从 向下取 递减， 同理：
int sum(int x, int y) {
int res = 0;
for (int i = x; i > 0; i -= i & -i)
for (int j = y; j > 0; j -= j & -j)
res += C[i][j];
return res;
}
子矩阵求和的容斥
对于查询 ，子矩阵和为：
\text{ans} = S(c, d) - S(a-1, d) - S(c, b-1) + S(a-1, b-1)
其中 是前缀和函数。
输入处理
题目没有明确给出操作数量，而是直到文件结束。因此我们需要使用 while (cin >> opt) 或 while (scanf(...) != EOF) 的方式循环读入。
复杂度
· 单次修改： · 单次查询： · 总时间复杂度：，其中 为操作次数。 · 空间复杂度：，但 时空间约 ，可以接受。
注意事项
· 树状数组下标从 1 开始，输入坐标保证在范围内。 · 使用 long long 存储结果，因为累加和可能超过 int 范围（，操作次数 ，最大和约 ）。 · 注意输入输出效率，建议使用 scanf / printf。
参考代码（C++）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 4100; // 2^12 = 4096，稍大一点
ll C[MAXN][MAXN];
int n, m;
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))
C[i][j] += k;
}
ll sum(int x, int y) {
ll res = 0;
for (int i = x; i > 0; i -= lowbit(i))
for (int j = y; j > 0; j -= lowbit(j))
res += C[i][j];
return res;
}
ll query(int a, int b, int c, int d) {
return sum(c, d) - sum(a-1, d) - sum(c, b-1) + sum(a-1, b-1);
}
int main() {
scanf("%d%d", &n, &m);
int opt, x, y, k, a, b, c, d;
while (scanf("%d", &opt) != EOF) {
if (opt == 1) {
scanf("%d%d%d", &x, &y, &k);
add(x, y, k);
} else {
scanf("%d%d%d%d", &a, &b, &c, &d);
printf("%lld\n", query(a, b, c, d));
}
}
return 0;
}
总结
二维树状数组是处理二维单点修改、子矩阵和查询的常用工具，代码简单，常数小。对于本题的数据范围，完全可以胜任。如果 更大（例如 ），则需要考虑离散化或使用二维线段树等更复杂的数据结构，但本题只需掌握二维树状数组即可。
暂无评论