前缀和

查找与遍历

说明

预处理从开头到各位置的累积和；区间和可在 O(1) 求出。

分析

p[i] 保存前 i 个元素的和，因此 [l,r) 的区间和等于 p[r]−p[l]。一次 O(n) 预处理后，任意区间查询都是常数时间。

对[2,3,5]构造p=[0,2,5,10]，查询[1,3)为10-2=8。p下标代表前多少项，起始零使空区间和从0开始的区间使用同一公式；不要把p[3]误当成原数组下标3的值。

查看图表代码

适用前提与边界

它适合静态数据；频繁修改元素时应使用树状数组或线段树。 查询使用半开区间0≤l≤r≤n；l=r时结果为0，预处理与相减都需避免int溢出。

示例输入与调用

prefix := PrefixSums([]int{2, 3, 5})
	fmt.Println(RangeSum(prefix, 1, 3))

运行输出

8

完整 Go 示例

package main

import "fmt"

func PrefixSums(a []int) []int {
	p := make([]int, len(a)+1)
	for i, x := range a {
		p[i+1] = p[i] + x
	}
	return p
}
func RangeSum(p []int, l, r int) int {
	return p[r] - p[l]
}

func main() {
	prefix := PrefixSums([]int{2, 3, 5})
	fmt.Println(RangeSum(prefix, 1, 3))
}