前缀和算法模板

一维前缀和

算法用途：快速求出数组中某一连续区间的和

一维前缀和算法模板

1、预处理出一个 dp 数组

要求原数组存储在 n + 1 的空间大小中，其中后 n 个空间存数据。

dp数组，数组开 n + 1个空间，dp[i] 表示 [ 1, i ] 区间内所有元素的和。

处理方法：? dp[ i ] = dp[ i - 1 ] + arr[ i ]?

2、使用前缀和数组

区间 l 到 r 的和：? sum = dp[ r ] - dp[ l - 1 ]?

复杂度分析

处理前缀和数组，需要 O(N) 的空间复杂度和空间复杂度，求一次区间 l 到 r 的和，需要 O(1) 的时间复杂度，如果需要求 q 次和，则时间复杂度就是 O(q) + O(N)

二维前缀和

算法用途：快速求出某个子矩阵的和

二维前缀和算法模板

1、预处理出一个 前缀和矩阵（二维数组 dp）

假设原矩阵有 m 行，n列，那么这个前缀和矩阵的二维数组 dp 要开 m+1 行， n+1 列的空间，第一行，第一列的数据都为 0，?dp[ i ][ j ] 表示 [ 1, i ]?行，[ 1, j ] 列包含的这个矩阵的数据和

处理方法：dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i ][ j - 1 ] - dp[ i - 1 ][ j - 1 ] + arr[ i ][ j ]

2、使用前缀和矩阵

[ x1, y1 ] ~ [ x2, y2 ] = dp[ x2, y2] - dp[ x1- 1 ][ y2 ] - dp[ x2 ][ y2?- 1 ] + dp[ x1 ][ y1 ]

二维数组前缀和的建立和使用图解

注：vector开具体大小空间的定义方式

一维 vector ：vector< int > dp ( m + 1 ) 开 m + 1 个连续的空间

二维 vector ：vector< vector< int > > dp(n + 1, vector<int> (m + 1))?（n+1行，m + 1列的二维数组定义方式）