前缀和概念与区间和

有勇气的牛排 27 算法 2025-08-10 22:19:17

程序员兼职接单交流

编程交流

进群口令：博客

前缀和思路

1 前缀和的定义

定一前缀和数组 prefix：

prefix[i]=nums[0]+nums[1]+...+nums[i-1]

也就是说：

prefix[0] = 0			（空数组的和）
prefix[1] = nums[0]
prefix[2] = nums[0] + nums[1]
...
prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

2 区间和的目标

要求：

sumRange(left, right)=nums[left]+nums[left+1]+...+nums[right]

3 用前缀和表示

观察 prefix[right+1]和prefix[left]

prefix[right+1] = nums[0]+nums[1]+...+nums[right]
prefix[left] = nums[0]+nums[1]+...+nums[left-1]

两者相减

prefix[right+1]-prefix[left]
= (nums[0]+nums[1]+...+nums[right])-(nums[0]+nums[1]+...+nums[left-1])
= nums[left]+nums[left+1]+...+nums[right]  # left-1之前的全部抵消

即：prefix[right+1]-prefix[left]

sumRange(left,right)=nums[left]+nums[left+1]+⋯+nums[right]
					= prefix[right+1]-prefix[left]

$\begin{aligned} sumRange(left,right)&=nums[left]+nums[left+1]+⋯+nums[right] \\ &= prefix[right+1]-prefix[left] \end{aligned}$

4 举个例子

数组：nums = [-2, 0, 3, -5, 2, -1]
前缀和：prefix_sum = [0, -2, -2, 1, -4, -2, -3]

题目案例

题目：
  sumRange(2, 5)
= 3-5+2-1
= prefix_sum[6] - prefix_sum[2]
= (-3)-(-2)
= -1

时间复杂度：

初始化：O(n)
每次查询：O(1)

空间复杂度：O(n)

总结

公式成立的原理就是 前缀和的抵消：
前缀和保存的是 从头到某个位置的和，两个前缀和相减，刚好抵消掉前面不需要的部分，留下的就是区间和。

前缀和 概念与区间和

前缀和 思路