网站开发女生适合吗,运城网站制作路90,赣州网上商城入驻方案,飓风算法受影响的网站文章目录 前缀和前缀和例题题意 差分差分例题及code↓模版例题输入样例#xff1a;输出样例#xff1a; code↓ 前缀和
前缀和定义#xff1a; 前缀和数组的第 i i i 位即为原数组 1 1 1 ~ i i i 位的和
原数组#xff1a; 1 2 3 4 5
前缀和数组#xff1… 文章目录 前缀和前缀和例题题意 差分差分例题及code↓模版例题输入样例输出样例 code↓ 前缀和
前缀和定义 前缀和数组的第 i i i 位即为原数组 1 1 1 ~ i i i 位的和
原数组 1 2 3 4 5
前缀和数组1 3 5 9 14我们由此可以推导出公式 a n s [ i ] a [ i ] a n s [ i − 1 ] ans[i]a[i]ans[i-1] ans[i]a[i]ans[i−1]
其中 a n s [ i − 1 ] ans[i-1] ans[i−1]即为前面( 1 1 1 ~ i − 1 i-1 i−1)的所有数的总和将 a n s [ i − 1 ] a [ i ] ans[i-1]a[i] ans[i−1]a[i] 即是原数组 1 1 1 ~ i i i 位的总和 for(int i1;in;i) cina[i],ans[i]a[i]ans[i-1];
//其中ans[i]是前缀和数组,a[i]是原数组前缀和例题
P8218 【深进1.例1】求区间和
题意
给定 n n n 个正整数组成的数列 a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_n a1,a2,⋯,an 和 m m m 个区间 [ l i , r i ] [l_i,r_i] [li,ri]分别求这 m m m 个区间的区间和。
对于所有测试数据 n , m ≤ 1 0 5 , a i ≤ 1 0 4 n,m\le10^5,a_i\le 10^4 n,m≤105,ai≤104
#include bits/stdc.h
using namespace std;
const int maxn1e55;
long long n,m,a[maxn]{},sum[maxn]{};
int main(){cinn;for(int i1;in;i){cina[i];sum[i]sum[i-1]a[i];//建立前缀和数组}cinm;for(int i1;im;i){long long l,r;//求l~r的区间和cinlr;coutsum[r]-sum[l-1]endl;//注意是r~(l-1)}return 0;
}差分
差分定义 我们令 a a a 为 b b b 的差分数组则 a a a 的前缀和数组为 b b b
我们由此可以运用等式的性质由前缀和公式推导出差分公式 a [ i ] a n s [ i ] a n s [ i − 1 ] a[i]ans[i]ans[i-1] a[i]ans[i]ans[i−1] for(int i1;in;i) cina[i],ans[i]a[i]ans[i-1];for(int i1;in;i) cha[i]ans[i]-ans[i-1];
//其中ans[i]是前缀和数组,a[i]是原数组,cha[i]是差分数组我们来举例解释一下↓
原数组 1 2 3 4 5
前缀和数组 1 3 5 9 14
差分数组 1 1 1 1 1
差分数组的前缀和数组1 2 3 4 5由此我们可以得知差分数组的前缀和数组即为原数组
若是将差分数组cha的cha[l]x,cha[r1]-x那么原数组a的a[l]~a[r]会依次加上x
原数组 1 2 3 4 5
前缀和数组 1 3 5 9 14
差分数组 1 1 1 1 1
差分数组的前缀和数组1 2 3 4 5我们来举例解释一下↓
原数组 1 2 3 4 5
前缀和数组 1 3 5 9 14
差分数组 1 12 1 1 1-2
差分数组 1 3 1 1 -1
差分数组的前缀和数组1 4 5 6 5
我们令x2,l2,r4,
那么我们需要达到的操作是将原数组的l~r位加上2,cha[l]x,cha[r1]-x之后,
cha[]的前缀和数组达成了需要达成的操作差分例题及code↓
这道题目真的很基础QWQ
模版例题
输入一个长度为 n n n 的整数序列。接下来输入 T T T 个操作每个操作包含三个整数 l , r , c l,r,c l,r,c表示将序列中 [ l , r ] [l,r] [l,r] 之间的每个数加上 c c c
请你输出进行完所有操作后的序列。
输入样例
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1输出样例
3 4 5 3 4 2code↓
#include bits/stdc.h
using namespace std;
const int maxn2e610;
int input[maxn],cha[maxn],n,T;
int main(){cinnT;for(int i1;in;i)cininput[i];for(int j1;jn;j) cha[j]input[j]-input[j-1];while(T--){int l,r,c;cinlrc;cha[l]cha[l]c,cha[r1]cha[r1]-c;}int sum0;for(int i1;in;i) sumcha[i],coutsum ;return 0;
}
