前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）。前缀和分为一维前缀和，以及二维前缀和。前缀和是一种重要的预处理，能够降低算法的时间复杂度，可以在 O ( 1 ) O(1) O(1)的时间复杂度内求出区间和。
一维数组前缀和
基本思想
一维数组前缀和的公式为： s u m [ i ] = s u m [ i − 1 ] + a r r [ i ] sum[i]=sum[i-1]+arr[i] sum[i]=sum[i−1]+arr[i]，其中 s u m sum sum为前缀和数组， a r r arr arr为内容数组。区间 [ i , j ] [i,j] [i,j]的区间和为： i n t e r v a l [ i , j ] = s u m [ j ] − s u m [ i − 1 ] interval[i, j]=sum[j]-sum[i-1] interval[i,j]=sum[j]−sum[i−1]。
二维数组前缀和
基本思想
二维数组前缀和的公式为： s u m [ i , j ] = s u m [ i − 1 , j ] + s u m [ i , j − 1 ] − s u m [ i − 1 , j − 1 ] + a r r [ i , j ] sum[i,j]=sum[i-1,j]+sum[i,j-1]-sum[i-1,j-1]+arr[i,j] sum[i,j]=sum[i−1,j]+sum[i,j−1]−sum[i−1,j−1]+arr[i,j]。区间 [ a i , b i , a j , b j ] [ai,bi,aj,bj] [ai,bi,aj,bj]的区间和为： i n t e r v a l [ a i , a j , b i , b j ] = s u m [ b i , b j ] − interval[ai,aj,bi,bj]=sum[bi,bj]- interval[ai,aj,bi,bj]=sum[bi,bj]− s u m [ a i − 1 , b j ] − s u m [ b i , a j − 1 ] + s u m [ a i − 1 , a j − 1 ] sum[ai-1,bj]-sum[bi,aj-1]+sum[ai-1,aj-1] sum[ai−1,bj]−sum[bi,aj−1]+sum[ai−1,aj−1]。
为了便于理解画了一个简易的图：
题目链接
-
304. 二维区域和检索 - 矩阵不可变
-
1480. 一维数组的动态和
参考文献：
- 什么是前缀和?
