【前缀和算法】--- 一维和二维前缀和模板

 Welcome to 9ilk's Code World

       

(๑•́ ₃ •̀๑) 个人主页:       9ilk

(๑•́ ₃ •̀๑) 文章专栏：    算法Journey  

---

本文开始,博主开始讲解有关前缀和的算法，本篇博客我们先来了解一下有关前缀和的两个模板。

---

🏠 一维前缀和模板

📌 题目内容

一维前缀和

📌题目解析

• 数组的下标是从1开始的。
• 数组中每个值的范围是−10^9 ≤ a[i] ≤ 10^9，因此我们需要考虑如果多个值相加用int可能溢出，可以考虑用long long.

📌算法原理

✏️ 思路一：暴力解法

 暴力解法很简单就是进行模拟，每次查询从L下标开始遍历直到到R下标。最坏情况是L是1下标，而R是n下标，n为数组长度。因此时间复杂度为O(q*n).

有没有什么优化的解法？

✏️ 思路二：前缀和

前缀和算tg法分为两步：1.预处理出来一个前缀和数组。2.使用前缀和数组。它可以用来快速求出数组中某一个连续区间的和。

• 预处理出前缀和数组

假设有一个数组arr,同时有个相关联的数组dp，dp[i]表示的是arr数组[1,i]区间内所有值和。

我们发现，比如dp[3]是【1,3】区间值的和，那么就相当于是【1,2】区间的和+arr[3].

因此我们可以得出公式dp[i] = dp[i-1] + arr[i].

通过公式我们在遍历一遍数组的同时，就可以求出前缀和数组。

• 使用前缀和数组

题目要我们求出[l,r]区间内值的和，由于我们提前求出了前缀和数组，我们发现所求区间 = 总和 - 前一段区间，因此【l,r】= dp[r] - dp[l-1]，这个过程是很快的达到了O(1)。

参考代码:

typedef long long ll;
int main() 
{int n = 0;int q = 0; //查询次数cin >> n >> q;vector<ll> v(n+1,0);vector<ll> dp(n+1,0);ll prev = 0;//获得前缀和数组//dp[i]表示的是从1到i区间值的总和for(int i = 1 ; i <= n ; i++){cin >> v[i];dp[i] = dp[i-1] + v[i];} //使用前缀和数组while(q--){int l = 0;int r = 0;cin >> l >> r;cout << dp[r] - dp[l-1] << endl; }return 0;
}

• 细节问题

我们前缀和数组下标是从1开始的，如果下标从0开始，当求[0,2]区间的值之和时就转化成dp[2] - dp[-1]这个dp[-1]是个边界情况需要我们特殊处理且原本数组没有-1开始的；如果下标从1开始，当求[1,2]区间的值之和时转化成dp[2] - dp[0]，对于dp[0]我们就容易将它处理为0即可。

总结：前缀和数组下标从1开始，是为了处理边界情况。

🏠 二维前缀和数组

📌 题目内容

二维前缀和

📌 题目解析

• 本题数据范围仍然过大，用int会有溢出的风险。
• 题目要我们求的是以(x1,y1)为左上角,(x2,y2)为右下角的子矩阵的和。

📌 算法原理

✏️ 思路一：暴力解法

暴力解法也就是模拟从第一个点开始直接按照划分区域进行遍历，最坏情况是整个矩阵，时间复杂度是O(n*m*q).

✏️ 思路二：二维前缀和

• 预处理出二维前缀和数组

假设有一个二维数组arr,dp数组是一个与它关联的数组。dp[i][j]表示以(1,1)为左上角，(i,j)为右上角形成的子矩阵中值之和。任取一块区域，假设D为(i,j)点，若我们要求dp[i][j]也就是求(1,1)到(i,j)区域的和，我们可以将这四部分相加，由于B和C不好求，我们可以利用A(dp[i-1][j-1])来间接求这两部分，但是不要忘记减去多进来的A。由于A+B和A+C在dp数组中分别对应的是dp[i-1][j]和dp[i][j-1],因此我们可以得到公式:

dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i ][ j-1 ] + arr[ i ][ j ] - dp[ i-1][ j-1 ].

通过公式，我们在遍历二维数组时就可以求出对应的dp二维数组。

• 使用二维前缀和数组

题目要我们求以(x1,y1)为左上角，(x2,y2)为右上角区域的值之和，也就是求区域D。因此D可以由整体减去A，B，C三部分，由于B和C不好求，所以我们利用A间接求。于是有D=(A+B+C+D) - (A+C) - (A+B) +A。对于A就是dp[x1][y1],A+B就是dp[x1-1][y2],A+C就是dp[x2][y1-1],于是得到公式：D = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]。此时 我们由于提前得到的二维前缀和数组，我们能很快得出D的值，时间复杂度是O(1).

时间复杂度优化为了O(m*n) + O(q).

参考代码：

int main() 
{int n = 0; //行 int m = 0; //列int q = 0; //查询次数cin >> n >> m >> q;vector<vector<long long>> vv(n + 1);vector<vector<long long>> dp(n + 1);for (int i = 0; i <= n; i++){vv[i].resize(m + 1, 0);dp[i].resize(m + 1, 0);if (i >= 1){for (int j = 1; j <= m; j++){cin >> vv[i][j];}}}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + vv[i][j] - dp[i-1][j-1];}}while (q--){int x1, x2, y1, y2 = 0;cin >> x1 >> y1 >> x2 >> y2;cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;}return 0;
}

---

总结：

1. 一维和二维前缀和数组下标都是从1开始。

2.当我们需要快速求出一段连续区间或区域时，可以考虑用前缀和数组，用前缀和数组间接求我们需要的。

3.我们可以根据场景推导出公式获得前缀和数组。