代码与动画 PREFIX SUM
前缀和.
预先累计数组，再通过两个前缀之差求区间和。
预处理 O(n)查询 O(1)空间 O(n)
原理与执行逻辑
保存数组从开头到各位置之前的累计和。区间右端之前的总和减去左端之前的总和，恰好留下目标区间。
执行步骤
- 建立长度 n + 1 的 prefix，令 prefix[0] = 0。
- 按顺序计算 prefix[i + 1] = prefix[i] + a[i]。
- 查询闭区间 [left, right] 时读取 prefix[right + 1] 与 prefix[left]。
- 两者相减得到区间和。
关键理解
prefix[i] 对应前 i 个元素，区间不包含下标 i。额外的首项 0 让从下标 0 开始的查询也使用同一公式。
简短示例
[3, -2, 5, 1] 的前缀数组为 [0, 3, 1, 6, 7]；查询 [1, 2] 得到 prefix[3] - prefix[1] = 6 - 3 = 3。
代码与执行动画
STEP 0 / 7function rangeSum(arr, left, right) { const prefix = Array(arr.length + 1).fill(0); for (let i = 0; i < arr.length; i++) { prefix[i + 1] = prefix[i] + arr[i]; } return prefix[right + 1] - prefix[left];}当前数据正在操作已访问 / 命中标记 / 指针
0
创建前缀数组
prefix[0] = 0。
配置演示数据
应用后重新生成执行过程，可单步观察结果。
前缀和的操作规则
使用长度 n + 1 的前缀数组，prefix[0] = 0。查询闭区间 [left, right] 的和为 prefix[right + 1] - prefix[left]。
对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
使用 n + 1 个前缀和，回答多次闭区间求和。