【Y总/算法基础课/学习笔记】前缀和 及 差分 思想
时间：2023-10-02 20:07:01
目录
-
- 前缀和 及 差分的思想
-
- 1. 一维前缀和
- 2. 二维前缀和
- 3. 一维差分
- 4. 二维差分
- 应用：模板题
前缀和 及 差分的思想
1. 一维前缀和
- 一维前缀和定义:从下标从『1』开始长度为『 n n n』的一维数组 『 a 1 , a 2 , a 3 , . . . , a n a_1,a_2,a_3,...,a_n a1,a2,a3,...,an』，前缀和计算公式为『 S i = a 1 a 2 . . . a i S_i=a_1 a_2 ... a_i Si=a1+a2+...+ai』。
- 如何求解『 S i S_i Si』：
S[0] = 0; for (int i = 1; i <= n; ++i) { S[i] = S[i - 1] + a[i]; } - 作用：快速的求解原数组中任意一段
[l,r]的和『 S = S r − S l − 1 S=S_r-S_{l-1} S=Sr−Sl−1』，计算的时间复杂度为 O ( 1 ) O(1) O(1)。 - 为什么原数组下标必须从1开始：定义『 S 0 = 0 S_0=0 S0=0』可以更好地处理边界问题，统一公式为『 S = S r − S l − 1 S=S_r-S_{l-1} S=Sr−Sl−1』。例如计算『 S 10 S_{10} S10』也可以写成『 S 10 = S 10 − S 0 S_{10}=S_{10}-S_0 S10=S10−S0』。
- 如何求解『 S i S_i Si』：
2. 二维前缀和
- 二维前缀和的定义：对于一个从下标从『1』开始的大小为『 n × m n \times m n×m』的二维数组 『 a i j a_{ij} aij』，前缀和的计算公式为『 S i j = a 11 + a 12 + . . . + a 1 j + a 21 + a 22 + . . . + a 2 j + . . . + a i 1 + a i 2 + . . . + a i j S_{ij}=a_{11}+a_{12}+...+a_{1j}+a_{21}+a_{22}+...+a_{2j}+...+a_{i1}+a_{i2}+...+a_{ij} Sij=a11+a12+...+a1j+a21+a22+...+a2j+...+ai1+ai2+...+aij』，即为其左上角所有元素的和。
- 如何求解『 S i j S_{ij} Sij』：
S[0][0] = 0; S[0][1] = 0; S[1][0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + a[i][j]; } - 作用：快速的求解原二维数组中任意一块矩形 [ l 1 [l_1 [l1 ~ l 2 , r 1 l_2,r_1 l2,r1 ~ r 2 ] r_2] r2] （ l 2 > l 1 , r 2 > r 1 l_2>l_1,r_2>r_1 l2>l1,r2>r1）的和『 S = S l 2 r 2 − S ( l 1 − 1 ) r 2 − S l 2 ( r 1 − 1 ) + S ( l 1 − 1 ) ( r 1 − 1 ) S=S_{l_2r_2}-S_{(l_1-1)r_2}-S_{l_2(r_1-1)}+S_{(l_1-1)(r_1-1)} S=Sl2r2−S(l1−1)r2−Sl2(r1−1)+S(l1−1)(r1−1)』，计算的时间复杂度为 O ( 1 ) O(1) O(1)。
- 如何求解『 S i j S_{ij} Sij』：
3. 一维差分
- 一维差分的定义：对于一个从下标从『1』开始的长度为『 n n n』的一维数组 『 a 1 , a 2 , a 3 , . . . , a n a_1,a_2,a_3,...,a_n a1,a2,a3,...,an』，构造一个新数组『 b 1 , b 2 , b 3 , . . . , b n b_1,b_2,b_3,...,b_n b1,b2,b3,...,bn』，使得『 a i a_i ai』是『 b b b』数组的前缀和，即『 a i = b 1 + b 2 + . . . + b i a_i=b_1+b_2+...+b_i ai=b1+b2+...+b元器件数据手册、IC替代型号，打造电子元器件IC百科大全！
