前缀和算法：高效的区间求和核心方法

前缀和算法是算法领域中经典的空间换时间策略，以一维前缀和为例：假如你有n个整数，有m次查询，每次求这n个数中某一子段的和，暴力模拟的话时间复杂度为O(nm)。
此时可以考虑对数组做预处理，先得到从第一个数到每个数的和，然后通过类似数学割补法的思想求子段和，则预处理时间复杂度O(n)，查询为O(m)。

一、一维前缀和

一维前缀和是前缀和算法的基础形式，针对一维数组的区间求和需求设计，通过构建一个前缀和数组存储累加和，实现后续查询的快速计算。

1. 前缀和数组的定义

给定原一维数组$arr$（为简化边界处理，通常将数组下标从1开始），构建长度为$n+1$的前缀和数组$sum$，其中：

• $sum[0] = 0$，作为边界默认值，避免处理第一个元素时出现数组越界问题；
• 对于$1≤i≤n$，$sum[i]$表示原数组前$i$个元素的累加和，即$sum[i] = arr[1] + arr[2] + ... + arr[i]$。

2. 递推公式

前缀和数组的构建仅需一次遍历原数组，利用前一项的结果推导当前项，时间复杂度为$O(n)$，下标从1开始的递推公式为：
$$sum[i] = sum[i-1] + arr[i]$$
下标从0开始的适配递推公式为：
$$sum[i] = sum[i-1] + arr[i-1]$$
（其实就是取原数组值的时候往前偏移一位，还是建议原数组下标base1，避免此问题。）

3. 区间和的快速计算

构建完前缀和数组后，原数组任意区间的和可通过一次减法运算直接得出，实现$O(1)$时间复杂度的查询。

• 下标从1开始：原数组区间$[l, r]$（$1≤l≤r≤n$）的和为 $sum(l, r) = sum[r] - sum[l-1]$；
• 下标从0开始：原数组区间$[x, y]$（$0≤x≤y<n$）的和为 $sum(x, y) = sum[y+1] - sum[x]$。

公式核心逻辑为：大区间的累加和减去小区间的累加和，差值即为目标区间的元素和，无需再遍历区间内元素。

二、二维前缀和

二维前缀和是一维前缀和的延伸，针对二维矩阵的子矩阵求和需求设计，核心思想与一维一致，通过构建二维前缀和数组完成预处理，将任意子矩阵的求和查询优化至$O(1)$。

1. 二维前缀和数组的定义

给定$n$行$m$列的原矩阵$arr$（下标从1开始），构建$(n+1)×(m+1)$的二维前缀和数组$sum$，其中：

• 数组第一行$sum[0][j] = 0$（$0≤j≤m$）、第一列$sum[i][0] = 0$（$0≤i≤n$），所有边界位置均为0；
• 对于$1≤i≤n$、$1≤j≤m$，$sum[i][j]$表示原矩阵中以$(1,1)$为左上角、$(i,j)$为右下角的矩形区域内所有元素的累加和。

该定义同样是为了统一边界处理逻辑，避免对矩阵第一行、第一列单独编写判断代码。

2. 递推公式

二维前缀和的递推需解决区域重叠重复计算问题：以$(i,j)$为右下角的矩形区域，可拆分为「上侧矩形」「左侧矩形」和「当前元素」，其中上侧和左侧矩形的重叠部分被计算了两次，需要减去一次。

递推公式为：
$$sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j]$$

• $sum[i-1][j]$：原矩阵中$(1,1)$至$(i-1,j)$的上侧矩形和；
• $sum[i][j-1]$：原矩阵中$(1,1)$至$(i,j-1)$的左侧矩形和；
• $sum[i-1][j-1]$：上侧与左侧矩形的重叠区域和，需扣除重复计算部分；
• $arr[i][j]$：原矩阵中当前位置的元素值。

通过两层循环遍历原矩阵即可完成前缀和数组构建，时间复杂度为$O(n×m)$，与矩阵元素总数成正比。

3. 子矩阵和的快速计算

对于原矩阵中任意以$(x1,y1)$为左上角、$(x2,y2)$为右下角的子矩阵（$1≤x1≤x2≤n$，$1≤y1≤y2≤m$），其内部所有元素的和可通过前缀和数组快速推导，公式为：
$$sum(x1,y1,x2,y2) = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]$$

公式推导逻辑：用大矩形$(1,1)$至$(x2,y2)$的和，依次减去左侧多余区域、上侧多余区域的和，最后补回被两次减去的重叠区域和，最终得到目标子矩阵的和。

三、前缀和算法的思想延伸

前缀和的核心思想并非仅局限于“求和”，而是通过预处理记录前序数据的累积结果，为后续查询提供快速支撑，这一思想可延伸至多个相关场景，形成各类衍生用法：

1. 前缀最大：用preMax[i]存储数组前i个数中的最大值，以O(n)时间复杂度预处理，后续查询只需要O(1)；
2. 前缀积：将累加替换为累积，适用于“除自身以外数组的乘积”等问题，结合前缀积和后缀积，可在不使用除法的情况下实现高效计算；
3. 与哈希表结合：将前缀和与哈希表配合，用于解决“和为k的子数组”等问题，通过哈希表记录前缀和的出现次数，快速查找满足条件的子数组，将时间复杂度优化至$O(n)$；
4. 与差分算法配合：前缀和擅长处理区间查询，差分算法擅长处理区间更新，二者结合形成经典组合，可高效解决数组的区间更新与区间查询复合问题；
5. 高维扩展：可从二维进一步扩展至三维及以上高维数组，适用于三维空间中的区域求和问题，递推与查询逻辑均遵循“累积-去重-补回”的核心思路。

四、算法总结

前缀和算法是处理数组、矩阵区间求和问题的基础且高效的预处理方法，其核心逻辑可概括为「一次预处理，多次快速查询」：

1. 一维场景通过构建一维前缀和数组，将区间和查询从$O(n)$优化至$O(1)$；
2. 二维场景通过构建二维前缀和数组，将子矩阵和查询从$O(n×m)$优化至$O(1)$；
3. 核心优势在于解决频繁查询的效率问题，且代码实现简洁，边界处理统一。

作为算法学习的基础内容，前缀和算法不仅是解决求和问题的标配方法，更是理解“空间换时间”策略的典型案例，同时为后续学习差分、动态规划、哈希表结合等高阶算法奠定了思想基础。掌握前缀和的递推公式与查询逻辑，能够快速解决各类数组、矩阵的求和问题，大幅提升算法解题的效率。

五、图示