线段树题解

#include<bits/stdc++.h>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
const int N=1e5+5;
int tree[N<<2],a[N];
void push_up(int p) {tree[p]=tree[ls(p)]+tree[rs(p)];}
void build(int p,int pl,int pr){
	if (pl==pr){
		tree[p]=a[pl];
		return;
	}
	int mid=(pl+pr)>>1;
	build(ls(p),pl,mid),build(rs(p),mid+1,pr);
	push_up(p);
}
int query(int l,int r,int p,int pl,int pr){
	if (l<=pl && pr<=r) return tree[p];
	int mid=(pl+pr)>>1,ans=0;
	if (l<=mid) ans+=query(l,r,ls(p),pl,mid);
	if (r>mid) ans+=query(l,r,rs(p),mid+1,pr);
	return ans;
}
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	int l,r;
	while (m--){
		scanf("%d %d",&l,&r);
		printf("%d\n",query(l,r,1,1,n));
	}
	return 0;
}