前缀和与差分
一句话说明
前缀和把多次区间查询变成两次减法；差分把多次区间修改变成两个端点标记。
前缀和
定义 prefix[i] 为前 i 个元素之和，特意让 prefix[0] = 0：
nums: 3 1 4 2
index: 0 1 2 3
prefix: 0 3 4 8 10区间 [left, right] 的和为：
prefix[right + 1] - prefix[left]flowchart LR A[0 到 right 的总和] --> C["减去 0 到 left-1 的总和"] C --> D[left 到 right 的区间和]
func buildPrefix(nums []int) []int {
prefix := make([]int, len(nums)+1)
for i, value := range nums {
prefix[i+1] = prefix[i] + value
}
return prefix
}
func rangeSum(prefix []int, left, right int) int {
return prefix[right+1] - prefix[left]
}预处理 O(n)，每次查询 O(1)，额外空间 O(n)。
二维前缀和
prefix[r][c] 表示左上角到 (r-1, c-1) 的矩形和。查询矩形时使用容斥：
目标矩形 = 大矩形 - 上方 - 左方 + 被重复减去的左上角func rectangleSum(prefix [][]int, r1, c1, r2, c2 int) int {
return prefix[r2+1][c2+1] -
prefix[r1][c2+1] -
prefix[r2+1][c1] +
prefix[r1][c1]
}差分数组
差分数组记录相邻元素的变化量：
nums: 2 2 5 5
diff: 2 0 3 0给闭区间 [left, right] 全部增加 value，只需要：
diff[left] += value
diff[right + 1] -= value # right + 1 存在时最后对 diff 求一次前缀和即可还原修改后的数组。
type Update struct {
Left int
Right int
Delta int
}
func applyUpdates(nums []int, updates []Update) []int {
if len(nums) == 0 {
return nil
}
diff := make([]int, len(nums)+1)
diff[0] = nums[0]
for i := 1; i < len(nums); i++ {
diff[i] = nums[i] - nums[i-1]
}
for _, update := range updates {
diff[update.Left] += update.Delta
diff[update.Right+1] -= update.Delta
}
result := make([]int, len(nums))
running := 0
for i := 0; i < len(nums); i++ {
running += diff[i]
result[i] = running
}
return result
}使用长度 n + 1 的差分数组后，right + 1 不需要额外判断。
选择指南
| 问题 | 结构 | 单次操作 |
|---|---|---|
| 静态数组，多次区间求和 | 前缀和 | 查询 O(1) |
| 多次区间加值，最后统一输出 | 差分 | 修改 O(1) |
| 动态单点修改 + 区间查询 | [[../数据结构/树状数组 | 树状数组]] |
| 动态区间修改 + 区间查询 | [[../数据结构/线段树 | 线段树]] |
易错点
- 统一闭区间或半开区间，不要混用。
- 前缀数组多出的首位
0能显著减少边界分支。- 差分适合离线批量修改；如果每次修改后立刻查询，通常要换数据结构。