构建前缀和

构建「前缀和」（Prefix Sum）是一种非常常用的算法技巧，用于在 常数时间内查询子区间的和，适用于数组、二维矩阵等结构。

📌 一维前缀和

✅ 定义：

给定一个数组 nums，前缀和数组 preSum 的定义是：

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

也就是：

• preSum[0] = 0
• preSum[i] = preSum[i - 1] + nums[i - 1]

然后，对于任意区间 [l, r]（闭区间），其和为：

sum = preSum[r + 1] - preSum[l]

📘 示例（JavaScript）：

// 构建前缀和数组
function buildPrefixSum(nums) {
  const preSum = [0];
  for (let i = 0; i < nums.length; i++) {
    preSum.push(preSum[i] + nums[i]);
  }
  return preSum;
}

// 查询区间和 [l, r]
function rangeSum(preSum, l, r) {
  return preSum[r + 1] - preSum[l];
}

// 示例
const nums = [2, 4, 5, 7, 1];
const preSum = buildPrefixSum(nums);
console.log(rangeSum(preSum, 1, 3)); // 输出：4+5+7 = 16

📌 二维前缀和（矩阵）

✅ 定义：

给定一个二维数组 matrix，前缀和数组 preSum 满足：

preSum[i][j] = matrix[0][0] + matrix[0][1] + ... + matrix[i-1][j-1]

即：

preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1]

然后查询任意子矩形 (x1, y1) ~ (x2, y2) 的和为：

sum = preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1]

📘 示例（JavaScript）：

// 构建二维前缀和
function build2DPrefixSum(matrix) {
  const m = matrix.length, n = matrix[0].length;
  const preSum = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      preSum[i][j] =
        preSum[i - 1][j] +
        preSum[i][j - 1] -
        preSum[i - 1][j - 1] +
        matrix[i - 1][j - 1];
    }
  }

  return preSum;
}

// 查询矩形和：左上(x1, y1)，右下(x2, y2)
function range2DSum(preSum, x1, y1, x2, y2) {
  return (
    preSum[x2 + 1][y2 + 1] -
    preSum[x1][y2 + 1] -
    preSum[x2 + 1][y1] +
    preSum[x1][y1]
  );
}

// 示例
const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];
const preSum = build2DPrefixSum(matrix);
console.log(range2DSum(preSum, 0, 0, 1, 1)); // 输出：1+2+4+5 = 12

🔍 应用场景