1 动态矩形和
给定
- 单点加:将
增加 。 - 矩形求和:查询左上角
、右下角 围成的闭矩形内所有数的和。
本文统一用
静态二维前缀和能快速查询矩形和,但修改一点后,许多前缀矩形都要改变。二维树状数组沿用 树状数组基础 的分块方式,在两个方向分别跳转。
2 管辖矩形
一维中,
行方向长度为
例如
3 单点修改
修改
行方向的覆盖块由 i += lowbit(i) 枚举,列方向由 j += lowbit(j) 枚举,两层循环取所有组合:
void add(int x, int y, long long v) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
c[i][j] += v;
}
}
}
覆盖
列循环每次都从原来的
4 前缀查询
设
分别将行前缀、列前缀按一维规则拆块,再组合:
long long sum(int x, int y) {
long long 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;
}
例如
每个行块、列块都互不重叠且覆盖对应前缀,所以它们的组合也互不重叠,恰好覆盖整个前缀矩形。将这些块相加即可得到
5 矩形容斥
目标是闭矩形
左上坐标包含在查询内,因此减去的是 前
当 sum(0,y)、sum(x,0) 自然返回
6 代码实现
下面采用通用演示格式,初始矩阵全为零:
- 第一行
:行数、列数、操作数。 1 x y v:将位置的数增加 。 2 x1 y1 x2 y2:查询闭矩形和。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 5;
const int maxm = 1000 + 5;
int n, m, q;
long long c[maxn][maxm];
int lowbit(int x) { return x & -x; }
void add(int x, int y, long long v) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
c[i][j] += v;
}
}
}
long long sum(int x, int y) {
long long 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;
}
long long rect_sum(int x1, int y1, int x2, int y2) {
return sum(x2, y2) - sum(x1 - 1, y2)
- sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> q;
while (q--) {
int op;
cin >> op;
if (op == 1) {
int x, y;
long long v;
cin >> x >> y >> v;
add(x, y, v);
} else {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << rect_sum(x1, y1, x2, y2) << '\n';
}
}
return 0;
}
若题目给出非零初始矩阵,可对每个初值调用一次 add,初始化为
单次修改或前缀查询在两个方向各进行
有效存储为 long long c[maxn][maxm] 约占
6.1 示例
输入:
3 4 6
1 1 1 5
1 2 3 7
2 1 1 2 3
1 2 3 -4
2 2 2 3 4
2 1 1 1 1
输出:
12
3
5
注意矩阵不是正方形。负增量后
7 边界
- 修改坐标必须满足
、 ,否则下标为零会使更新停滞。 - 查询左上、右下坐标均包含在内,容斥公式必须带两个减一。
- 本篇支持单点加;任意赋值需要先求旧值或额外保存原矩阵,再加入差值。
- 矩形加不是一次
add(x,y,v),需另行引入二维差分。 - 多组数据应清空有效矩形范围;所有块和及中间结果须在
long long范围内。
8 练习
CSES 1739:Forest Queries II 要求翻转一个格子的树木状态,并查询矩形内树木数量。
将有树记为
- 读入初始地图时,将每个有树位置加入
。 - 另外保存当前格子状态。由空变有时加入
,由有变空时加入 。 - 矩形查询直接使用
rect_sum。
该题先输入正方形地图和操作数,代码读入部分需要相应调整;它的翻转操作没有额外的增量参数。题面按“行、列”给坐标,使用时保持这一顺序。
进阶可做 luogu P4514: P4514 上帝造题的七分钟。它要求矩形加与矩形求和,需要将差分的边界修改推广到二维的四个角,并进一步推导矩形和的加权公式。可结合 区间加与区间求和 中的贡献次数理解这一扩展。
9 相关题解
暂无相关题解