数据结构与算法 / 系统课时
前缀和与区间查询
前缀和与区间查询
前缀和把重复的区间累加提前到一次预处理中。完成本课后,你将能用统一的下标公式查询任意闭区间之和,并理解它为什么适合“查询多、修改少”的静态数据。
学习目标
- 理解长度为
n + 1的前缀数组含义 - 使用统一公式完成闭区间求和
- 分析预处理、查询与更新成本
前缀和的定义
设原数组为 nums,前缀数组 prefix 比它多一个元素,并令 prefix[0] = 0。对每个下标 i,使用下面的递推关系:
text
prefix[i + 1] = prefix[i] + nums[i]因此,prefix[t] 表示原数组前 t 个元素之和。额外的首元素使从下标 0 开始的查询也不需要特殊分支。

区间查询公式
闭区间 [left, right] 的和等于右端之后的前缀减去左端之前的前缀:
text
range_sum(left, right) = prefix[right + 1] - prefix[left]例如查询 [2, 5],prefix[6] 包含下标 0 到 5,减去 prefix[2] 所包含的下标 0 到 1,剩余部分正好是下标 2 到 5。
同样的思想还能用于区间计数。先把满足条件的元素映射为 1,其余映射为 0,再构建前缀和,就能快速统计任意区间内满足条件的元素数量。
主示例
下面的类在构造时完成预处理,并在查询前统一检查边界。
python
from typing import Sequence
class RangeSumQuery:
def __init__(self, nums: Sequence[int]) -> None:
self._size = len(nums)
self._prefix = [0]
for value in nums:
# 新前缀等于已有累计值加当前元素
self._prefix.append(self._prefix[-1] + value)
def query(self, left: int, right: int) -> int:
if left < 0 or right >= self._size or left > right:
raise IndexError("区间边界非法")
return self._prefix[right + 1] - self._prefix[left]
def main() -> None:
values = [3, 1, 4, 1, 5, 9]
query = RangeSumQuery(values)
print(query.query(0, 2))
print(query.query(2, 5))
if __name__ == "__main__":
main()预期输出:
text
8
19第一行是 3 + 1 + 4,第二行是 4 + 1 + 5 + 9。
成本与适用边界
构建前缀数组需要 O(n) 时间和 O(n) 额外空间,之后每次查询只需两次数组读取和一次减法,因此是 O(1)。若有 q 次查询,总成本为 O(n + q)。
原数组一旦修改,受影响位置之后的前缀值都需要更新,直接重建通常是 O(n)。所以前缀和适合查询多、修改少的数据;频繁单点更新与区间查询应考虑树状数组或线段树。固定宽度整数语言还要注意累计和溢出。
按自己的节奏,确认真正理解。