【算法——一维前缀和与二维前缀和】
一维前缀和
一维前缀和具体题目如下：
解析:
本道题就是要我们求指定的一段数组的所有元素的和。
举例:
给一个数组，如上图：
如果要求求出下标[5,8]的和时，
按照暴力解法，从5下标开始加到8即可。
所以总的时间复杂度为O(n*q)，这种复杂度一定会超时。
此时就衍生出了，前缀和的算法
创建一个辅助数组dp。
该dp数组的含义是：
下标为i的数组的值为前i个arr数组元素的和。
所以：dp数组的算法核心就是：
dp[i] = dp[i-1] + arr[i];
那就可能会出现越界的情况，当i = 0时，就出现了dp[0] = dp[-1] + arr[0];
所以dp数组一般都从1开始填充，dp[0] = 0,这样不会影响到后面的结果。
所以dp应该开n+1个空间。
当我们想要求出区间[5,8]的和时，
如果想要求出区间为[l,r]的和时，只需要
sum = dp[r] - dp[l-1];
二维前缀和
算法原理如下：
原文地址：https://blog.csdn.net/w2915w/article/details/142527567
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！