前缀和算法详解：从一维到二维实战

第一步：构建前缀和矩阵

这里就要用到一维数组里面的拓展知识。我们要在矩阵的最上面和最左边添加上一行和一列 0，这样我们就可以省去非常多的边界条件的处理。

注意 dp 表与原数组 matrix 内的元素的映射关系：

• 从 dp 表到 matrix 矩阵，横纵坐标减一；
• 从 matrix 矩阵到 dp 表，横纵坐标加一。

sum[i][j] 的含义：表示从 [0, 0] 位置到 [i, j] 位置这段区域内，所有元素的累加和。

递推方程可以参考图形面积的分割法： sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1]

这里多减去了一次重叠部分（红色区域），所以逻辑上正好抵消。

第二步：使用前缀和矩阵

题目的接口中提供的参数是原始矩阵的下标，为了避免下标映射错误，这里直接先把下标映射成 dp 表里面对应的下标：row1++, col1++, row2++, col2++。

对于左上角 (row1, col1)、右下角 (row2, col2) 围成的区域，利用容斥原理计算： sum[row2][col2] - sum[row2][col1 - 1] - sum[row1 - 1][col2] + sum[row1 - 1][col1 - 1]

这个流程下来，二维前缀和其实是不难的，核心思想简单，注意题目和 dp 表的细节就好了。

#include <iostream>
using namespace std;
const int N = 1010;
int arr[N][N];
long long dp[N][N];
int n, m, q;

int main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
        }
    }
    
    // 构建二维前缀和
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
    
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] + dp[x1 - 1][y1 - 1] - dp[x2][y1 - 1] - dp[x1 - 1][y2] << endl;
    }
    return 0;
}

经典例题实战

寻找数组的中心下标

这道题的核心在于：除中心下标的元素外，该元素左边的「前缀和」等于该元素右边的「后缀和」。

因此，我们可以先预处理出来两个数组，一个表示前缀和，另一个表示后缀和。然后枚举可能的中心下标，判断每一个位置的「前缀和」以及「后缀和」是否相等。

class Solution:
    def pivotIndex(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        
        # dp1 存储左侧前缀和
        dp1 = [0] * n
        # dp2 存储右侧后缀和
        dp2 = [0] * n
        
        for i in range(1, n):
            dp1[i] = dp1[i - 1] + nums[i - 1]
            
        for i in range(n - 2, -1, -1):
            dp2[i] = dp2[i + 1] + nums[i + 1]
            
        for i in range(n):
            if dp1[i] == dp2[i]:
                return i
        return -1

除自身以外数组的乘积

注意题目的要求，不能使用除法，并且要在 O(N) 的时间复杂度内完成。这意味着我们不能求出整个数组的乘积再除以单个元素。

根据题意，对于每一个位置的最终结果 ret[i]，它是由两部分组成的：

• nums[0] * ... * nums[i - 1]（左侧乘积）
• nums[i + 1] * ... * nums[n - 1]（右侧乘积）

于是，我们可以利用前缀和的思想，使用两个数组 left 和 right，分别处理出来两个信息：

• left 表示：i 位置之前的所有元素的前缀乘积
• right 表示：i 位置之后的所有元素的后缀乘积

然后再处理最终结果。

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        left = [1] * n
        right = [1] * n
        
        for i in range(1, n):
            left[i] = left[i - 1] * nums[i - 1]
            
        for i in range(n - 2, -1, -1):
            right[i] = right[i + 1] * nums[i + 1]
            
        for i in range(n):
            nums[i] = left[i] * right[i]
        return nums

还有一种方法就是不用开两个数组这么公式化，我们可以灵活一点，使用对撞指针来优化空间。

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        n = len(nums)
        dp1 = [1] * n
        left = 0
        right = n - 1
        l = 1
        r = 1
        
        while left < n and right >= 0:
            dp1[left] *= l
            dp1[right] *= r
            l *= nums[left]
            r *= nums[right]
            left += 1
            right -= 1
        return dp1

总结

前缀和是一种高效处理区间问题的算法思想，通过预处理数组实现 O(1) 时间复杂度的区间和查询。其核心在于构建前缀和数组，将原数组的累加信息存储，从而避免重复计算。

• 一维前缀和通过递推公式 s[i] = s[i-1] + a[i-1] 快速求解区间 [l, r] 的和。
• 二维前缀和则通过矩阵递推公式，实现子矩阵和的快速计算。
• 处理边界时可通过添加辅助行/列简化逻辑。

前缀和以空间换时间，很好地优化了时间复杂度，是算法面试和竞赛中的高频考点。