自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:13:54，当前版本为作者最后更新于2022-03-19 12:47:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【深进1.例1】求区间和

前缀和差分模板题。

我们定义一个数列 $\{a_n\}$ 的前缀和为 $S_n=\sum \limits_{i=1}^n a_i=a_1+a_2+\dots+a_n$。

有了前缀和之后，我们可以使用差分来进行静态的区间求和。具体而言，对于一个区间 $[l,r]$，区间的和 $a_l+a_{l+1}+\dots+a_r=S_r-S_{l-1}$。

证明的话直接展开，$S_r=a_1+a_2+\dots+a_{l-1}+a_{l}+a_{l+1}+\dots+a_r$，$S_{l-1}=a_1+a_2+\dots+a_{l-1}$，这样 $S_r-S_{l-1}$ 便等于 $a_l+a_{l+1}+\dots+a_r$，即所求的区间和了，预处理出前缀和，单次就是 $O(1)$ 复杂度可以完成的事情了。

参考代码（std）：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
#include <vector>

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int n,m,a[100050],s[100050];

int main()
{
	n=read();
	for (int i=1;i<=n;i++)
		s[i]=s[i-1]+(a[i]=read());
	m=read();
	for (int i=1;i<=m;i++)
	{
		int l=read(),r=read();
		cout << s[r]-s[l-1] << endl;
	}
	return 0;
}