前缀和

例题1：前缀和

给定一个长度为N的数组：a1,a2,a3......an。（N<=10^6，1<= A[i]<=10^3）。接下来有M次查找，每次查找给两个整数l和r。求a[l]到a[r]的子段和是多少。（M<=10^6）。

解法1：直接枚举法（时间复杂度为n*n）

#include<iostream>
using namespace std;
int a[100005],n,m;
int main()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];cin>>m;for(int i=1;i<=m;i++){ int l,r,sum=0; cin>>l>>r;for(int j=l;j<=r;j++)sum+=a[j]; cout<<sum<<endl; }return 0;
} 

Copy

解法2：利用前缀和求解（时间复杂度为n）

前缀和也称前缀和数组：给定一个数组A，定义数组sum，数组中每一项sum[i]保存数组 A[i]到A[j]的和，数组sum称为数组A的前缀和数组。

如何计算前缀和？

for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)sum[i]=sum[i]+a[j];

Copy

sum[5]=A[1]+A[2]+A[3]+A[4]+A[5];
sum[5]=sum[4]+A[5];

Copy

通项公式：sum[i]=sum[i-1]+A[i];

举个栗子：设l=4, r=6;则子段A[4,6]=A[4]+A[5]+A[6]=sum[6]-sum[3];

sum[6]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6];
sum[3]=A[1]+A[2]+A[3];

Copy

通项公式：A[l,r]=sum[r]-sum[l-1];

详细代码如下：

#include<iostream>
using namespace std;
int a[100005],sum[100005],n,m;
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]+a[i];  //计算前缀和}  int l,r; for(int i=1;i<=m;i++){cin>>l>>r;cout<<sum[r]-sum[l-1]<<endl;  //计算子段和A[l,r] } return 0;
} 

Copy

你们想要的递推公式：

1. 后缀和: 定义数组sum，数组中每一项sum[i]保存数组A中[i...n]的和;


2. 递推公式: sum[i] = sumr[i+1]+A[i];


3. 前缀积: 定义数组mul，数组中每一项mul[i]保存数组A中[1…i]的积;

4. 递推公式: mul[0] = 1; mul[i]= mul[i-1]* A[i];


5. 后缀积: 定义数组mul，数组中每一项mul[i]保存数组A中[i…n]的积;

6. 递推公式: mul[n＋1]=1; mulr[i]= mur[i＋1]* A[i];


例题2：连乘问题

题目描述

给定 nn 个正整数： a_1,a_2,\cdots,a_na1​,a2​,⋯,an​，请计算并输出 \bar{A}_1,\bar{A}_2,\cdots,\bar{A}_nAˉ1​,Aˉ2​,⋯,Aˉn​，其中

{\bar{A}_i}=\frac{a_1\cdot a_2\cdot a_3\cdots a_n}{a_i}\bmod {10000}Aˉi​=ai​a1​⋅a2​⋅a3​⋯an​​mod10000

也就是说，\bar{A}_iAˉi​ 是 a_1a1​ 到 a_nan​ 除去 a_iai​ 的连乘。由于答案可能比较大，输出每个 \bar{A}_iAˉi​ 模 1000010000 的余数。

输入格式

第一行：单个正整数表示 nn；

第二行：nn 个正整数表示 a_1,a_2,\cdots,a_na1​,a2​,⋯,an​。

输出格式

共 nn 行：第 ii 行输出 \bar{A}_iAˉi​。

样例

输入1：

4
1 3 4 6

Copy

输出1:

72
24
18
12

Copy

数据范围/约定

- 对于 30\%30% 的数据，2\leq n \leq 10002≤n≤1000；

- 对于 60\%60% 的数据，2\leq n \leq 100002≤n≤10000；

- 对于 100\%100% 的数据，2\leq n \leq 1000002≤n≤100000，1\leq a_i \leq 100001≤ai​≤10000。

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
long long a[100001];
long long b[100001];
long long c[100001];
int main()
{long long n;cin >> n;b[0] = 1;c[n+1] = 1;for(int i = 1; i <= n; i++){cin >> a[i];b[i] = b[i-1] * a[i] % 10000;}for(int i = n; i >= 1; i--){c[i] = c[i+1] * a[i] % 10000;}for(int i = 1; i <= n; i++){cout << b[i-1] * c[i+1] % 10000 << endl; }
}

Copy

例题3：异或和

题目描述

  小可可在五年级暑假开始学习编程，编程语言中有一种“按位异或(xor)”的运算引起了他的莫大兴趣。于是，他思考这样的一个问题：给一个长度为 nn 的整数序列 AA，如何计算出满足下列两个条件的整数对 (l, r)(l,r) 的数量。

   1、1≤l≤r≤n1≤l≤r≤n；

   2、A_lAl​ xor A_{l+1}Al+1​ xor … xor A_rAr​ = A_lAl​ + A_{l+1}Al+1​ + … + A_rAr​

  这里的 xor 就是按位异或（C 或 C++语言中“按位异或”运算符为^），求 aa xor bb 的原理是：将 aa 和 bb 转换为二进制，如果 a、ba、b 的二进制表示中对应位置不相同，则异或结果的二进制表示中对应位置为 1，如果 a、ba、b 的二进制表示中对应位置相同，则异或结果的二进制表示中对应位置为 0。例如：计算 1010 xor 1212，二进制表示 1010 是 10101010，二进制表示 12 是 1100，1010 xor 1212 结果的二进制表示是 01100110，即为 6。具体为下式：

          

  小可可虽然提出了问题，但他自己不会解决，只好又要麻烦你解决啦。

输入格式

输入有两行：

第一行一个正整数 nn，表示整数序列 AA 的元素个数。

第二行有 nn 个整数，第 ii 个整数 A_iAi​ 表示整数序列 AA 的第 ii 个元素的值。

输出格式

输出一行，包括一个正整数，表示满足条件的整数对 (l, r)(l,r) 的数量。

样例输入1：

4
2 5 4 6

Copy

样例输出1：

5

Copy

解释1

样例 1 解释：

   (l, r) = (1, 1)、(2, 2)、(3, 3)、(4, 4)(l,r)=(1,1)、(2,2)、(3,3)、(4,4)显然满足条件，还有(l, r) = (1, 2)(l,r)=(1,2)也满足条件，因为 A_1 xor A_2=2 xor 5=7A1​xorA2​=2xor5=7，而 A_1 + A_2=2 + 5=7A1​+A2​=2+5=7。所以满足条件的整数对 (l, r)(l,r) 的数量为 5。

样例输入2：

19
885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1

Copy

样例输出2：

37

Copy

数据范围/约定

对于 20%的数据满足：A_i = 0 (1≤ i ≤n)Ai​=0(1≤i≤n)。

另有 30%的数据满足：1≤ n ≤ 50001≤n≤5000。

对于 100%的数据满足：1≤ n ≤ 200000，0≤ A_i ≤ 2^{20}1≤n≤200000，0≤Ai​≤220。

完整代码如下：

#include<bits/stdc++.h>
using namespace std;
/*①a^a = 0, a ^ 0 = a => a ^ b ^ a = b;=> xor[l, r] = xor[r] ^ xor[l-1]; ②前缀和：sum[l, r] = sum[r] - sum[l-1];③0^0 = 0, 0^1 = 1, 1^0 = 1, 1^1 = 0;0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 = 0(进1)。 ④a ^ b = a + b的前提是没有哪一位同时有1。⑤如果区间[l, r]满足累计异或=累加和。那么缩小区间，也满足条件。如果区间[l, r]满足累计异或=累加和，但是[l, r+1]不满足累计以后=累加和。那么[l, r+2]...[l, n]一定都不满足条件。    ⑥枚举右端点r，判断[1, r]中有多少个左端点l，使得[l, r]满足条件。a. 如果[l, r]不满足条件，那么[l, r+1]肯定不满足条件，对于r+1的计算，可以排除掉[1, l]。所以左端点是可以基于上一次枚举出的右段点r继续计算的。时间复杂度O(N);  
*/
const int N = 2e5 + 5;
int n, x, Xor[N], Sum[N];
long long ans;
int main()
{cin >> n;int l = 1; for(int r=1; r<=n; r++) {cin >> x;Xor[r] = Xor[r-1] ^ x;  //前缀异或 Sum[r] = Sum[r-1] + x;  //前缀和。while(l <= r && (Sum[r]-Sum[l-1]) != (Xor[r] ^ Xor[l-1])) l++;ans += r - l + 1;   //[l, r]都可以和r配对。 }cout << ans << endl;return 0; 
}

Copy

差分

[修改和查询]

给定一个长度为N的数列A[N]，所有元素初始值为0，首先进行m次修改操作，每次修改给定三个整数l，r和x，将A[l]到A[r]分别加上x。接着进行q次查询操作，每次查询给定两个整数l, r，输出A[l, r]的和。（1≤n≤10^6，1≤m ≤10^6，1≤g≤10^6，1≤x≤10^3）

[枚举+前缀和]


1. 枚举m次修改操作，每次修改操作进行（r-l+1）次加法操作，时间复杂度: 0（n²）


2. 利用前缀和，进行q次查询操作，时间复杂度:0（n）

#include<iostream>
using namespace std;
long long n,m,q,a[10005],sum[100000]; 
int main()
{cin>>n>>m>>q;int l,r,x;for(int i=1;i<=m;i++){ cin>>l>>r>>x;for(int j=l;j<=r;j++)a[j]+=x;}for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]; for(int i=1;i<=q;i++){cin>>l>>r;cout<<sum[r]-sum[l-1]<<endl; }return 0;
}

Copy

A[0] = 0;
for((int i=1;i<=n; i++)D[i]= A[i]-A[i-1];

Copy

差分和前缀和是互逆操作，差分数组D的前缀和数组SUMD和原数组A相同。sumd[i]=a[i]

sumd[3]=d[1]]+d[2]+d[3]=a[1]-a[0]+a[2]-a[1]+a[[3]-a[2]=a[3]-a[0]

sumd[i] = d[1]+d[2] + …+ d[i-1] +d[i]


= a[1]-a[0]+a[2]-a[1]+...+a[i-1]-a[i-2]+a[i]-a[i-1]

已知原数组A的差分数组D，即可在O（n）的时间复杂度下计算出原数组。


[修改和查询]

给定一个长度为N的数列A[N]，所有元素初始值为0，首先进行m次修改操作，每次修改给定三个整数，r和x，将A[]到A[r]分别加上x。接着进行q次查询操作，每次查询给定两个整数l，r，输出A[l，r]的和。（1≤n≤10^6，1≤m≤10^6，1≤q≤10^6，1≤x≤10^3）

[差分数组+前缀和]

1. 对原数列A的差分数列D进行M次修改操作，时间复杂度: o(n)

2. 利用前缀和，进行g次查询操作，时间复杂度: o(n)

   #include<iostream>
   using namespace std;
   long long n,m,q,a[100005],d[100005],sum[100000];
   int main( )
   {
   int l,r,x; 
   cin>>n>>m>>q;
   for(int i=1;i<=m;i++)
   { cin>>l>>r>>x;d[l]+=x; d[r+1]-=x;
   }
   for(int i=1;i<=n; i++)
   {//sumd[i]=sumd[i-1]+d[i];//因为sumd[i]=a[i] a[i]=a[i-1]+d[i];//计算d的前缀和，即原数组a sum[i]=sum[i-1]+a[i];//计算a的前缀和
   }
   for(int i=1;i<=q;i++)
   {cin>>l>>r;cout<<sum[r]-sum[l-1]<<endl;
   } 
   return 0;
   }
   

   Copy