【算法图解】前缀和：区间查询神器

你有没有遇到过这种问题：

给你一个数组
问很多次“从 i 到 j 的和是多少？”

如果每次都循环相加，复杂度就会爆。

前缀和的思想是：

把重复计算提前做掉，让每次查询只做 O(1)。

它是很多面试题的底层骨架。

1. 一维前缀和：定义与公式

定义：

pre[i] 表示前 i 个元素的和（也可以定义成到 i 为止，关键是统一）

常用定义：

pre[0] = 0
pre[i+1] = pre[i] + a[i]

这样区间 l, r 的和就是：

$$sum(l,r) = prer+1 - prel$$

2. 可运行代码

function buildPrefixSum(a) {
  const pre = new Array(a.length + 1).fill(0)
  for (let i = 0; i < a.length; i++) pre[i + 1] = pre[i] + a[i]
  return pre
}

function rangeSum(pre, l, r) {
  return pre[r + 1] - pre[l]
}

const a = [2, -1, 3, 5]
const pre = buildPrefixSum(a)
console.log(rangeSum(pre, 1, 3)) // -1 + 3 + 5 = 7

3. 典型题：子数组和为 K（前缀和 + 哈希表）

题意：统计有多少个子数组的和等于 K。

核心等式：

若 pre[j] - pre[i] = K
则 pre[i] = pre[j] - K

遍历前缀和 pre[j] 时，用 Map 统计过去出现过多少个 pre[i]。

function subarraySumEqualsK(a, k) {
  const count = new Map()
  count.set(0, 1)

  let pre = 0
  let ans = 0

  for (const x of a) {
    pre += x
    ans += count.get(pre - k) ?? 0
    count.set(pre, (count.get(pre) ?? 0) + 1)
  }

  return ans
}

console.log(subarraySumEqualsK([1, 2, 3, -2, 2], 3))