数据结构与算法 / 系统课时

用前缀和处理区间统计

用前缀和处理区间统计

当题目反复询问同一个静态数组的区间和或区间计数时,每次重新遍历区间会重复做大量加法。前缀和先累计“从起点到当前位置”的结果,再用两个前缀值相减,把一次区间查询降到常数时间。

学习目标

  • 建立 prefix[i] 表示前 i 个元素累计值的统一定义
  • 用前缀差在 O(1)O(1) 时间回答静态区间统计
  • 识别前缀和的边界、适用条件和常见下标错误

用一个额外起点统一边界

设数组为 nums,定义 prefix[0] = 0,并令 prefix[i + 1] = prefix[i] + nums[i]。这样 prefix[k] 始终表示原数组前 k 个元素之和。

如果要求闭区间 [l, r] 的元素和,答案就是:

prefix[r+1]−prefix[l]prefix[r + 1] - prefix[l]

原因是 prefix[r + 1] 包含从下标 0 到 r 的所有元素,而 prefix[l] 正好减掉下标 0 到 l - 1 的部分。额外的 prefix[0] 让 l = 0 时也无需单独判断。

先预处理,再常数时间查询

下面构造一次前缀和,并回答多个区间查询。数组不发生修改时,预处理成本只支付一次。

python
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))

预期输出:

text
[0, 2, 1, 4, 9, 13]
7
13

区间 [1, 3] 对应 -1 + 3 + 5 = 7,通过前缀差计算为 prefix[4] - prefix[1] = 9 - 2。构造前缀数组需要 O(n)O(n) 时间和 O(n)O(n) 空间,此后每次查询只做一次减法,因此是 O(1)O(1)。

把计数问题也转成前缀差

前缀和并不只处理数值求和。只要某种统计可以逐项累加,就可以先把每个位置转换成贡献值。例如要查询区间内偶数个数,可以把偶数记为 1、奇数记为 0,再对这个 0/1 数组建立前缀和。

这种建模的关键不是“原数组必须能直接相加”,而是先定义每个元素对目标统计贡献多少。字符频次、满足阈值的元素数量、某类事件出现次数,都可以用同样方式处理静态区间查询。

最容易错的是下标定义

常见错误不是公式本身,而是同时混用两套定义:一会儿让 prefix[i] 表示“到下标 i 为止”,一会儿又把它当作“前 i 个元素”。更稳定的做法是固定使用长度为 n + 1 的前缀数组,并始终使用 prefix[r + 1] - prefix[l]。

还要注意数值范围:在固定宽度整数语言中,大数组累计和可能溢出,应根据题目上界选择 long 等更宽类型。只要先统一前缀定义,再把区间 [l, r] 翻译成两个前缀边界,区间统计题通常就能从重复扫描变成一次预处理加常数时间查询。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用前缀和处理区间统计

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通