日野弥生：勉強しよう

prefix sum

发表于2024年12月10日

介绍

前缀和可以简单理解为「数列的前 n 项的和」，能降低查询的时间复杂度。C++ 标准库中也实现了：std::partial_sum。具体应用在单维和多维数组、树等结构。

快速求数组前 i 项之和

快速求数组的 [i,j] 范围内的和

快速求二维矩阵中某个子矩阵之和

递推

$B[0] = A[0]$，对于 i \geq 1 则 $B[i] = B[i-1] + A[i]$。

变化

但是，在计算 [i,j] 区间和时，若 i 为 0 得单独讨论，否则 i-1 小于 0 会越界。为了让两种区间使用同一种计算公式，使用前缀和算法时，通常会令前缀和数组的长度为原数组的长度加一，使preSum[0] = 0。从而前缀和定义为：

$preSum[i] = nums[0] + nums[1] + … + nums[i-1]$

则对于前缀和数组的任一项有：$preSum[i] = preSum[i-1] + nums[i-1]$，此时只需谨记前缀和数组的下标与原数组下标不是直接对应，而是加一对应。即 preSum[i] 表示 nums 前 i-1 项的，不包含当前元素 nums[i]。

那么，对于任意 $i<=j<len(nums)$ ，数组 [i,j] 区间和公式：

$sum(i, j) = preSum[j + 1] - preSum[i]$