Skip to main content

前缀和 & 差分

参考资料​

前缀和​

前缀和可以简单理解为「数列的前 nn 项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。

Sk=∑i=1kAi=A1+A2+⋯+AkS_k=\sum_{i=1}^k A_i=A_1+A_2+\dots+A_k ∑i=abAi=Sb−Sa−1\sum_{i=a}^b A_i=S_b-S_{a-1}

差分​

差分是一种和前缀和相对的策略，可以当做是求和的逆运算。

Ak=Sk−Sk−1A_k=S_k-S_{k-1}

STL​

例题​

洛谷 P8218 【深进1.例1】求区间和​

洛谷 P8218 【深进1.例1】求区间和

给定由 nn 个正整数组成的序列 a1,a2,…,ana_1, a_2, \dots, a_n 和 mm 个区间 [li,ri][l_i,r_i]，分别求这 mm 个区间的区间和。

Code (1)
#include <bits/stdc++.h>
using namespace std;

const int N=100005;
int a[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		a[i]+=a[i-1];
	}
	int m;
	cin>>m;
	while(m--)
	{
		int l,r;
		cin>>l>>r;
		cout<<a[r]-a[l-1]<<'\n';
	}
	return 0;
}