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

前缀和与区间查询

前缀和与区间查询

前缀和把重复的区间累加提前到一次预处理中。完成本课后,你将能用统一的下标公式查询任意闭区间之和,并理解它为什么适合“查询多、修改少”的静态数据。

学习目标

  • 理解长度为 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)。所以前缀和适合查询多、修改少的数据;频繁单点更新与区间查询应考虑树状数组或线段树。固定宽度整数语言还要注意累计和溢出。

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

目录与阅读设置

阅读设置

17

记录一个想法

前缀和与区间查询

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

登录哪都通