前缀和 and 差分

二维前缀和

int[][] prefix = new int[m + 1][n + 1];

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + matrix[i][j];
    }
}

int query(int x1, int y1, int x2, int y2) {
    return prefix[x2 + 1][y2 + 1] - prefix[x1][y2 + 1] - prefix[x2 + 1][y1] + prefix[x1][y1];
}

预处理公式：

prefix[i+1][j+1] = prefix[i][j+1] + prefix[i+1][j] - prefix[i][j] + matrix[i][j]

查询公式：

sum = prefix[x2+1][y2+1] - prefix[x1][y2+1] - prefix[x2+1][y1] + prefix[x1][y1]

差分数组

// 原数组 -> 差分数组（长度为 n + 1）
int n = nums.length;
int[] diff = new int[n + 1];

diff[0] = nums[0];
for (int i = 1; i < n; i++) {
    diff[i] = nums[i] - nums[i - 1];
}

// 对区间 [l, r] 批量增加 val（0 <= l <= r < n）
void increment(int l, int r, int val) {
    diff[l] += val;
    diff[r + 1] -= val;
}

// 差分数组 -> 还原原数组
int[] restore() {
    int[] result = new int[n];
    result[0] = diff[0];
    for (int i = 1; i < n; i++) {
        result[i] = result[i - 1] + diff[i];
    }
    return result;
}

构建公式：

diff[i] = nums[i] - nums[i-1]

区间修改公式：

diff[l] += val
diff[r+1] -= val

恢复公式：

result[i] = result[i-1] + diff[i]

举例：

原数组: [1, 3, 5, 5, 6]（长度 n=5）
差分数组: [1, 2, 2, 0, 1, 0]（长度 n+1=6，最后一位为 0）

区间 [1,3] 加 2:
diff[1] += 2  → diff = [1, 4, 2, 0, 1, 0]
diff[4] -= 2  → diff = [1, 4, 2, 0, -1, 0]

恢复: [1, 5, 7, 7, 6, 6]

适用场景： 多次区间修改 + 最终结果查询（优化为 O(1) 修改）

题链：https://www.luogu.com.cn/problem/CF816B