思路

求区间和。对于区间和，有两种方法：

• 线段树（只给出代码）。
• 前缀和。

前缀和

思路

前缀和就是定义一个数组 $s$，对于所有的 $s_n$，其值为

$$s_i=\sum_{i=0}^{n} a_i=s_{i-1}+a_i$$

这样：

$$\begin{aligned} \sum_{i=l}^{r} a_i &= a_{l}+a_{l+1}+...+a_{r-1}+a_{r} \\ &= (a_{1}+a_{2}+...+a_{r-1}+a_{r})-(a_{1}+a_{2}+...+a_{l-1})\\ &=\sum_{i=1}^{r} a_i-\sum_{i=1}^{l-1} a_i\\ &=s_r-s_{l-1} \end{aligned}$$

也就是说，$[l,r]$ 的和等于 $s_r-s_{l-1}$。

code

#include<bits/stdc++.h>
using namespace std;
long long s[100005],a[100005];
int n,m,l,r;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		s[i]=a[i]+s[i-1];
	}
	while(m--){
		cin>>l>>r;
		cout<<s[r]-s[l-1]<<'\n';
	}
	return 0;
}

线段树

线段树是一种二叉树，查询和修改的时间复杂度都是 $O(\log n)$，总体复杂度 $O(m \log n)$。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a[100005],lzy[400010],w[400010];
void push(const int u){//更新
	w[u]=w[u<<1]+w[(u<<1)+1];
}
void build(const int u,int l,int r){//建立
	if(r==l){
		w[u]=a[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(u*2,l,mid);
	build((u*2)+1,mid+1,r);
	push(u);
}
bool in(int L,int R,int l,int r){
	return (l<=L)&&(R<=r);
}
bool out(int L,int R,int l,int r){
	return (L>r)||(R<l);
}
void tag(int u,int l,ll x){
	lzy[u]+=x;
	w[u]+=l*x;
}
void pushdown(int u,int l,int r){
	int mid=(l+r)/2;
	tag(u*2,mid-l+1,lzy[u]);
	tag(u*2+1,r-mid,lzy[u]);
	lzy[u]=0;
}
ll sec_query(int u,int L,int R,int l,int r){
	int mid=(L+R)/2;
	if(in(L,R,l,r))	return w[u];
	else if(out(L,R,l,r))	return 0;
	else{
		pushdown(u,L,R);
		return sec_query(u*2,L,mid,l,r)+sec_query(u*2+1,mid+1,R,l,r);
	}	
}
void sec_updata(int u,int L,int R,int l,int r,ll x){
	if(in(L,R,l,r))	tag(u,R-L+1,x);
	else if(!out(L,R,l,r)){
		int mid=(L+R)/2;
		pushdown(u,L,R);
		sec_updata(u*2,L,mid,l,r,x);
		sec_updata(u*2+1,mid+1,R,l,r,x);
		push(u);
	}
}
int main(){
	int n,t;
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(t--){
		int x,y;
		cin>>x>>y;
		cout<<sec_query(1,1,n,x,y)<<'\n';
	}
	return 0;
}

尾声

点个赞吧，写代码不容易！！！