sko.kr

算法 - 4. 前缀和

algorithmsarraysoptimizationprefix-sumsrange-queries
By sko•9/29/2025•7 min read

何时使用前缀和

当你需要对数组中的范围重复查询累积属性时使用前缀和。虽然最常用于范围和，但它可以适应于：

  • 范围和查询（经典用例）
  • 子数组和问题（查找具有目标和的子数组）
  • 累积频率（计算范围内的元素）
  • 范围积（使用对数或单独数组进行修改）
  • 2D矩阵区域和（扩展到2D前缀和）
  • 差分数组（高效应用范围更新）
  • 需要对区间的累积属性进行多次查询的任何问题

示例问题

每日收入分析：给定每日销售数据 [3, 5, 2, 8, 4, 6, 1]，你需要回答关于不同日期范围收入的多个查询。

  • 查询："第2天到第5天的总收入是多少？"
  • 查询："第0天到第3天的总收入是多少？"
  • 查询："第4天到第6天的总收入是多少？"

答案：构建一次前缀和数组，然后在O(1)时间内回答每个查询。第2天到第5天：总和是20（2 + 8 + 4 + 6）。

最重要的洞察

任何范围和都等于两个前缀和的差 - 通过预先计算从开始的累积和，我们可以使用减法立即计算任何子数组和：sum(i, j) = prefix[j] - prefix[i-1]。

注意：该算法的力量在于转换问题。不是重复求和元素（每次查询O(n)），我们只预计算一次所有部分和。在查询时，我们只需要一次减法："到右边界的总和"减去"左边界之前的总和"。这将重复的O(n)操作转换为O(1)查找。

为什么叫"前缀和（Prefix Sum）"？：这个名字来源于存储数组每个前缀（开头部分）的和。对于数组 [3, 5, 2, 8]，前缀是 [3]、[3, 5]、[3, 5, 2] 和 [3, 5, 2, 8]。我们存储它们的和：[0, 3, 8, 10, 18]。这种技术被称为"Prefix Sum"，特别是因为经典用例是加法——尽管相同的模式适用于其他操作（前缀积等），但它们不太常见。

单位元很重要：初始值取决于操作：加法为0（因为 x + 0 = x），乘法为1（因为 x × 1 = x）。对于前缀积，你会使用 prefix[0] = 1 并使用逆运算（除法）来提取范围：product(left, right) = prefix[right+1] / prefix[left]。这与减法是加法的逆运算类似。

决策框架

前缀和技术涉及两个阶段：

构建阶段：在遍历数组一次时使用操作（加法、乘法等）累积值

查询阶段：对于任何范围 [left, right]，对两个预计算值使用逆运算来提取范围结果

  • 加法 → 减法：sum(left, right) = prefix[right+1] - prefix[left]
  • 乘法 → 除法：product(left, right) = prefix[right+1] / prefix[left]
  • 最大值 → 最大值（幂等）：max(left, right) = max(prefix[right+1], -prefix[left])（需要不同的方法，如线段树）

代码

// 构建阶段：预计算所有前缀和
function buildPrefixSum(nums) {
  // 从0开始表示空前缀
  const prefix = new Array(nums.length + 1).fill(0);

  for (let i = 0; i < nums.length; i++) {
    const currentNum = nums[i];
    const sumSoFar = prefix[i];

    // 决策框架：累积运行总和
    prefix[i + 1] = sumSoFar + currentNum;
  }

  return prefix;
}

// 查询阶段：使用逆运算提取范围
function rangeSum(prefix, left, right) {
  const totalUpToRight = prefix[right + 1];
  const totalBeforeLeft = prefix[left];

  // 决策框架：通过减法提取范围
  return totalUpToRight - totalBeforeLeft;
}

// 使用每日收入数据的示例
const dailySales = [3, 5, 2, 8, 4, 6, 1];
const prefixSums = buildPrefixSum(dailySales);

console.log(rangeSum(prefixSums, 2, 5)); // 20（第2-5天：2+8+4+6）
console.log(rangeSum(prefixSums, 0, 3)); // 18（第0-3天：3+5+2+8）
console.log(rangeSum(prefixSums, 4, 6)); // 11（第4-6天：4+6+1）

疑问解答

常见疑问："为什么在前缀和数组的开头添加一个额外的元素？我们不能使用与原始数组相同的索引吗？"

为什么你可能想避免额外的元素

一对一的对应关系似乎更直观：

  • 原始数组：[3, 5, 2, 8, 4, 6, 1]
  • 前缀和数组：[3, 8, 10, 18, 22, 28, 29]（相同长度）

这样，prefix[i] 将是从0到i的元素之和，这感觉很自然。

为什么额外的元素至关重要

关键认识：如果没有额外的元素，你需要对从索引0开始的范围进行特殊情况处理！

让我们看看没有额外元素会发生什么：

原始数组：[3, 5, 2, 8, 4, 6, 1]
前缀和：  [3, 8, 10, 18, 22, 28, 29]

查询 sum(2, 5)：
  = prefix[5] - prefix[1]
  = 28 - 8
  = 20 ✓（正确：2+8+4+6）

查询 sum(0, 3)：
  = prefix[3] - prefix[-1]  // 糟糕！索引-1不存在
  = prefix[3] - ???
  = 需要特殊情况：if (left == 0) return prefix[right]

优雅的解决方案：prefix[0] = 0

通过在开头添加一个零：

原始数组：[3, 5, 2, 8, 4, 6, 1]
前缀和：  [0, 3, 8, 10, 18, 22, 28, 29]
         ↑
         这表示"零个元素的和"

查询 sum(0, 3)：
  = prefix[4] - prefix[0]
  = 18 - 0
  = 18 ✓（正确：3+5+2+8）

为什么这个模式保证正确性

公式 sum(left, right) = prefix[right+1] - prefix[left] 普遍有效的原因：

  1. prefix[i] = 前i个元素的和（不包括索引i处的元素）
  2. prefix[right+1] = 直到并包括索引right的所有元素的和
  3. prefix[left] = 索引left之前的所有元素的和
  4. 差值正好给出范围 [left, right] 中的元素

这消除了所有特殊情况，使代码更清洁、更易维护、更不容易出错。额外的内存成本（一个元素）与获得的清晰度相比可以忽略不计。

← Back to Blog