前缀和

• 前缀和
  • 什么是前缀和
  • 一维前缀和
  • 二维前缀和
  • 使用场景

什么是前缀和

前缀和算法（Prefix Sum）是一种用于快速计算数组元素之和的技术。它通过预先计算数组中每个位置前所有元素的累加和，将这些部分和存储在一个新的数组中，从而在需要计算某个区间的和时，可以通过简单的减法操作得到结果，而不必重新遍历整个区间。

一维前缀和

指对于给定的一维数组，我们可以预先计算出一个新的数组，其中每个元素是原数组中从第一个元素到当前位置的元素之和

• 代码实现

  function prefixSum(nums) {
    let presum = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
        presum[i + 1] = presum[i] + nums[i];
    }
    return presum;
  }

二维前缀和

用于处理二维数组（或矩阵）。对于给定的二维数组，我们可以预先计算出一个新的二维数组，其中每个元素是原数组中从左上角到当前位置的元素之和。

• 代码实现

  function prefixSum2D(matrix) {
    let rows = matrix.length, cols = matrix[0].length;
    let presum = new Array(rows + 1).fill(0).map(() => new Array(cols + 1).fill(0));
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            presum[i + 1][j + 1] = presum[i + 1][j] + presum[i][j + 1] - presum[i][j] + matrix[i][j];
        }
    }
    return presum;
  }

使用场景

• 查询区间和
  给定一个数组和一系列查询，每个查询包含两个索引 i 和 j，我们需要快速计算出数组中从 i 到 j 的元素之和
• 处理二维数组（矩阵）中的区域和问题
  给定一个二维数组（矩阵）和一系列查询，每个查询包含两个坐标 (x1, y1) 和 (x2, y2)，我们需要快速计算出矩阵中从 (x1, y1) 到 (x2, y2) 形成的子矩阵的元素之和
• 动态规划中优化状态转移 我们需要计算某个状态的所有前驱状态的值之和