网站开发有哪些方式,网站建设企业 熊掌号,江苏省建设厅,找代加工产品哪个网前缀和是指某序列的前n项和#xff0c;可以把它理解为数学上的数列的前n项和#xff0c;而差分可以看成前缀和的逆运算。合理的使用前缀和与差分#xff0c;可以将某些复杂的问题简单化。
我们通过一个例子来理解前缀和算法的优势#xff1a;
一维前缀和#xff1a;
ww…
前缀和是指某序列的前n项和可以把它理解为数学上的数列的前n项和而差分可以看成前缀和的逆运算。合理的使用前缀和与差分可以将某些复杂的问题简单化。
我们通过一个例子来理解前缀和算法的优势
一维前缀和
www.nowcoder.com
我们可以通过暴力的解法去解决这个问题但是这样时间复杂度会比较高达到On*q
我们可以对暴力解法进行优化
我们以【1,4,7,2,5,8,3,6,9】这个数组来讲解前缀和快速求出数组中某个连续区间的元素和这个算法
index为数组下标至于为什么下标从一开始后面会讲 我们提前弄一个前缀和数组dp这个数组的元素dp【i】代表【1i】区间内所有元素之和 我们在求dp的时候肯定不可以用暴力解法不然的话时间复杂度又上去了
dp【i】代表 【1i】区间内所有元素之和那dp【i-1】代表 【1i-1】区间内所有元素之和
dp【i】就可以等于dp【i-1】arr【i】
那我们再来看看题目题目要求我们输出从l到r区间内所有元素之和
那我们可以直接输出dp【r】-dp【l-1】
#include iostream
#includevector
using namespace std;
int main() {int n,q;cinnq;vectorint arr(n1);for(int i1;in;i) cinarr[i];vectorlong long dp(n1);for(int i1;in;i) dp[i]dp[i-1]arr[i];while(q--){int l,r;cinlr;coutdp[r]-dp[l-1]endl;}return 0;
}
// 64 位输出请用 printf(%lld)二位前缀和
首先如果我们使用暴力解法时间复杂度直接就是O(nmq我们可以对其使用前缀和算法优化
我们可以创建一个n1m1的的数组arr和n1m1的的前缀和数组dp
这里数组坐标加一也是为了防止越界的情况
dp【i】【j】代表从1,1~ij这个区间内所有元素之和
我们如何快速求出dp【i】【j】的值呢以下面这个数组为例假设我们要求的是dp【3】【3】 我们先来观察一个通用图我们要求多少ABCD之和 ABCDABACD-A括号内的是一个整体
我们可以结合下标的关系推导进一步的关系 ABCDABACD-A
dp【i-1】【j】dp【i】【j-1】arr【i】【j】-dp【i-1】【j-1】
这样我们就求出来了dp的每一个数了回到题目上题目要求我们输出x1,y1)~(x2,y2)这个区间内的所有元素之和假设让我们输出是是这个区间
编辑
DABCD-AB-ACA
编辑
DABCD-AB-ACA dp【x2】【y2】-dp【x1-1】【y2】-dp【x2】【y1-1】dp【x1-1】【y1-1】
为了防止越界我们开辟数组也要多开一行一列
