数据结构与算法 / 系统课时
用前缀和处理区间统计
用前缀和处理区间统计
当题目反复询问同一个静态数组的区间和或区间计数时,每次重新遍历区间会重复做大量加法。前缀和先累计“从起点到当前位置”的结果,再用两个前缀值相减,把一次区间查询降到常数时间。
学习目标
- 建立
prefix[i]表示前i个元素累计值的统一定义 - 用前缀差在 时间回答静态区间统计
- 识别前缀和的边界、适用条件和常见下标错误
用一个额外起点统一边界
设数组为 nums,定义 prefix[0] = 0,并令 prefix[i + 1] = prefix[i] + nums[i]。这样 prefix[k] 始终表示原数组前 k 个元素之和。
如果要求闭区间 [l, r] 的元素和,答案就是:
原因是 prefix[r + 1] 包含从下标 0 到 r 的所有元素,而 prefix[l] 正好减掉下标 0 到 l - 1 的部分。额外的 prefix[0] 让 l = 0 时也无需单独判断。
先预处理,再常数时间查询
下面构造一次前缀和,并回答多个区间查询。数组不发生修改时,预处理成本只支付一次。
def build_prefix(nums):
prefix = [0]
for x in nums:
# prefix[-1] 是已经处理部分的累计和
prefix.append(prefix[-1] + x)
return prefix
def range_sum(prefix, left, right):
return prefix[right + 1] - prefix[left]
nums = [2, -1, 3, 5, 4]
prefix = build_prefix(nums)
print(prefix)
print(range_sum(prefix, 1, 3))
print(range_sum(prefix, 0, 4))预期输出:
[0, 2, 1, 4, 9, 13]
7
13区间 [1, 3] 对应 -1 + 3 + 5 = 7,通过前缀差计算为 prefix[4] - prefix[1] = 9 - 2。构造前缀数组需要 时间和 空间,此后每次查询只做一次减法,因此是 。
把计数问题也转成前缀差
前缀和并不只处理数值求和。只要某种统计可以逐项累加,就可以先把每个位置转换成贡献值。例如要查询区间内偶数个数,可以把偶数记为 1、奇数记为 0,再对这个 0/1 数组建立前缀和。
这种建模的关键不是“原数组必须能直接相加”,而是先定义每个元素对目标统计贡献多少。字符频次、满足阈值的元素数量、某类事件出现次数,都可以用同样方式处理静态区间查询。
最容易错的是下标定义
常见错误不是公式本身,而是同时混用两套定义:一会儿让 prefix[i] 表示“到下标 i 为止”,一会儿又把它当作“前 i 个元素”。更稳定的做法是固定使用长度为 n + 1 的前缀数组,并始终使用 prefix[r + 1] - prefix[l]。
还要注意数值范围:在固定宽度整数语言中,大数组累计和可能溢出,应根据题目上界选择 long 等更宽类型。只要先统一前缀定义,再把区间 [l, r] 翻译成两个前缀边界,区间统计题通常就能从重复扫描变成一次预处理加常数时间查询。