不可变数组多次区间求和，为什么要预处理前缀和？

简化版

如果数组不变但要多次查询区间和，应该先预处理前缀和。

定义 prefix[i] 表示前 i 个元素的和，那么区间 [left, right] 的和是：

prefix[right + 1] - prefix[left]

预处理 O(n)，每次查询 O(1)。

详细版

不可变数组的关键是“更新没有，查询很多”。

如果每次查询都从 left 加到 right，单次是 O(n)，查询次数多时会很慢。前缀和把重复计算提前做掉。

构造时：

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

查询时：

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

多加一个 prefix[0] = 0 可以避免 left = 0 的特判。

完整版教学

一、为什么多次查询要预处理

单次区间求和直接循环没有问题，但如果查询次数是 10^5，每次最多扫 10^5 个元素，最坏会到 10^10 级别操作。前缀和的想法是把每个位置之前的累计结果提前算好，之后任意区间都通过两个累计值相减得到。它用一次 O(n) 预处理，换来每次 O(1) 查询。

记忆钩子：数组不变、区间多问，先把“从头到这里的和”存下来。

二、prefix[i] 为什么表示前 i 个元素

推荐定义 prefix 长度为 n + 1，其中 prefix[0] = 0，prefix[i] 表示 nums[0] 到 nums[i-1] 的和。这样区间 [left, right] 的左边界刚好对应 prefix[left]，右边界对应 prefix[right + 1]。

数组	`nums[0]`	`nums[1]`	`nums[2]`
前缀下标	`prefix[1]`	`prefix[2]`	`prefix[3]`
含义	前 1 个和	前 2 个和	前 3 个和

多出来的 prefix[0] 是为了让空前缀也有统一表示。

三、公式为什么成立

prefix[right + 1] 包含从 0 到 right 的全部元素。prefix[left] 包含从 0 到 left - 1 的元素。两者相减，前面公共部分被抵消，剩下的正好是 [left, right]。

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

这就是前缀和所有区间查询公式的来源。

四、代码模板

可以封装成类：

class NumArray {
  constructor(nums) {
    this.prefix = new Array(nums.length + 1).fill(0)
    for (let i = 0; i < nums.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + nums[i]
    }
  }

  sumRange(left, right) {
    return this.prefix[right + 1] - this.prefix[left]
  }
}

这个写法把查询的边界都统一掉，尤其是 left = 0 时不用额外分支。

五、复杂度收益怎么算

假设数组长度 n = 100000，查询次数 q = 100000。

方法	预处理	单次查询	总成本
每次循环求和	`O(1)`	`O(n)`	`O(nq)`
前缀和	`O(n)`	`O(1)`	`O(n+q)`

当查询很多时，前缀和收益非常明显。

六、常见误区与追问

误区：prefix[i] 定义混乱。 一会儿表示到 i，一会儿表示前 i 个，会导致 +1/-1 全乱。
误区：忘记 prefix[0] = 0。 没有空前缀时，查询从 0 开始的区间容易特判。
误区：数组会更新也直接用普通前缀和。 更新会让后续前缀都失效，应考虑树状数组或线段树。
追问：为什么空间是 O(n)？ 需要保存每个位置的累计和，长度是 n + 1。
追问：如果元素有负数还能用吗？ 可以，前缀和不依赖正负，只是累计加法。

这些问题考的是前缀和定义是否稳定。

七、加强记忆

不可变区间求和记成“前缀多一格，查询两数减”。prefix[0] = 0，prefix[i] 表示前 i 个元素的和；查询 [l,r] 就是 prefix[r+1]-prefix[l]。只要数组不更新，多次查询就非常适合这种预处理模型。

简化版

详细版