预处理¶
1 前缀和¶
前缀和是一种常用的预处理技术，用于快速计算数组中某个区间内所有元素的和。
基本思想¶
通过预处理构建一个前缀和数组，实现区间和的快速查询。
一维前缀和¶
- 定义： \(sum[i] = a[1] + a[2] + ... + a[i]\)
- 时间复杂度：
- 预处理： \(O(n)\)
- 查询： \(O(1)\)
- 空间复杂度： \(O(n)\)
// 预处理一维前缀和
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + a[i];
}
// 查询区间 [l, r] 的和
int result = sum[r] - sum[l - 1];
二维前缀和¶
- 定义： \(sum[i][j]\) 表示以 \((1, 1)\) 为左上角， \((i, j)\) 为右下角的子矩阵元素和。
- 时间复杂度：
- 预处理： \(O(nm)\)
- 查询： \(O(1)\)
- 空间复杂度： \(O(nm)\)
// 预处理二维前缀和
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
}
}
// 查询子矩阵 [(x1,y1), (x2,y2)] 的和
int result = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
2 差分¶
差分是前缀和的逆运算，用于快速对数组的某个区间进行修改操作。
基本思想¶
通过构建差分数组，将区间增减操作转化为端点修改。
一维差分¶
- 定义： \(b[i] = a[i] - a[i - 1]\)
- 时间复杂度：
- 预处理： \(O(n)\)
- 修改： \(O(1)\)
- 还原： \(O(n)\)
- 空间复杂度： \(O(n)\)
// 构造差分数组
for (int i = 1; i <= n; i++) {
b[i] = a[i] - a[i - 1];
}
// 对区间 [l, r] 加上常数 c
b[l] += c;
b[r + 1] -= c;
// 通过差分数组还原原数组
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + b[i];
}
二维差分¶
- 定义： \(b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]\)
- 时间复杂度：
- 预处理： \(O(nm)\)
- 修改： \(O(1)\)
- 还原： \(O(nm)\)
- 空间复杂度： \(O(nm)\)
// 构造二维差分数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
}
}
// 对子矩阵 [(x1,y1), (x2,y2)] 加上常数 c
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
// 通过二维差分数组还原原数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];
}
}