Prefix Sum & Adjacent Difference - tenji/ks GitHub Wiki
前缀和 & 差分数组
一、前缀和（Prefix Sum）
1.1 定义
前缀和可以简单理解为「数列的前 n 项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度，时间复杂度从 $O(n)$ 变成 $O(1)$。
1.2 适用场景
前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。
1.3 Java 实现
class NumArray {
// 前缀和数组
private int[] preSum;
/* 输入一个数组，构造前缀和 */
public NumArray(int[] nums) {
// preSum[0] = 0，便于计算累加和
preSum = new int[nums.length + 1];
// 计算 nums 的累加和
for (int i = 1; i < preSum.length; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}
}
/* 查询闭区间 [left, right] 的累加和 */
public int sumRange(int left, int right) {
return preSum[right + 1] - preSum[left];
}
}
1.4 二维/多维前缀和（2-Dimensional and Multi-Dimensional Prefix Sum）
class NumMatrix {
// 定义：preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和
private int[][] preSum;
public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
if (m == 0 || n == 0) return;
// 构造前缀和矩阵
preSum = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 计算每个矩阵 [0, 0, i, j] 的元素和
preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i - 1][j - 1] - preSum[i-1][j-1];
}
}
}
// 计算子矩阵 [x1, y1, x2, y2] 的元素和
public int sumRegion(int x1, int y1, int x2, int y2) {
// 目标矩阵之和由四个相邻矩阵运算获得
return preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1];
}
}
1.5 基于 DP 计算高维前缀和（High-Dimensional Sum over Subsets Dynamic Programming）
...
1.6 树上前缀和（Prefix Sum on Tree）
...
1.7 Leetcode 题目
- 一维前缀和
- 二维/多维前缀和
- 基于 DP 计算高维前缀和
- 树上前缀和
二、差分数组（Adjacent Difference）
2.1 定义
差分是一种和前缀和相对的策略，可以当做是求和的逆运算。
2.2 适用场景
差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。
2.3 Java 实现
// 差分数组工具类
class Difference {
// 差分数组
private int[] diff;
/* 输入一个初始数组，区间操作将在这个数组上进行 */
public Difference(int[] nums) {
assert nums.length > 0;
diff = new int[nums.length];
// 根据初始数组构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
/* 给闭区间 [i, j] 增加 val（可以是负数）*/
public void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < diff.length) {
diff[j + 1] -= val;
}
}
/* 返回结果数组 */
public int[] result() {
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res;
}
}