朝阳区规划网站,wordpress打开3秒,企业公司网,i深圳谁开发的Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏#xff1a; 算法Journey 本文开始,博主开始讲解有关前缀和的算法#xff0c;本篇博客我们先来了解一下有关前缀和的两个模板。 #x1f3e0; 一维前缀和模板
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,同时有个相关联的数组dpdp[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;vectorll v(n1,0);vectorll dp(n1,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。由于AB和AC在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可以由整体减去ABC三部分由于B和C不好求所以我们利用A间接求。于是有D(ABCD) - (AC) - (AB) A。对于A就是dp[x1][y1],AB就是dp[x1-1][y2],AC就是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;vectorvectorlong long vv(n 1);vectorvectorlong 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.我们可以根据场景推导出公式获得前缀和数组。
