线段树模板（hdu1166）

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <math.h>

#include <bitset>

#include <vector>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#define MAXN 1010100

#define LL long long

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define ll __int64

#define INF 0x7fffffff

#define cs(s) freopen(s,"r",stdin)

#define mem(x) memset(x,0,sizeof(x))

#define PI acos(-1)

#define eps 1e-10

using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int lcm(int a,int b){return a/gcd(a,b)*b;}

LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

//head

const int maxn=5e4+1;

string gao;

int tree[maxn<<2],a[maxn<<2],t,n;

void build(int now,int l,int r){

	if(l==r){tree[now]=a[l];return;}//叶子节点直接赋值

	int mid=(l+r)/2;

	build(now<<1,l,mid);

	build(now<<1|1,mid+1,r);

	tree[now]=tree[now<<1]+tree[now<<1|1];//向下传递

}

void update(int now,int l,int r,int val,int ne){

	if(l==ne&&l==r){

		tree[now]+=val;

		return;

	}else{

		int mid=(l+r)/2;

		if(ne<=mid)update(now<<1,l,mid,val,ne);

		if(ne>mid)update(now<<1|1,mid+1,r,val,ne);

		tree[now]=tree[now<<1]+tree[now<<1|1];

	}

}

LL que(int now,int l,int r,int dx,int dy){

	if(l>=dx&&r<=dy)return tree[now];

	else{

		int mid=(l+r)/2;

		LL sum=0;

		if(dx<=mid)sum+=que(now<<1,l,mid,dx,dy);

		if(dy>mid) sum+=que(now<<1|1,mid+1,r,dx,dy);

		return sum;

	}

}

int main(){

	ios::sync_with_stdio(false);

	cin>>t;

	for(int test=1;test<=t;test++){

		mem(tree);

		cout<<"Case "<<test<<':'<<endl;

		cin>>n;

		for(int i=1;i<=n;i++)cin>>a[i];

		build(1,1,n);

		while(1){

			cin>>gao;

			if(gao=="End")break;

			if(gao[0]=='Q'){

				int l,r;

				cin>>l>>r;

				cout<<que(1,1,n,l,r)<<endl;

			}else if(gao[0]=='S'){//减

				int p,val;

				cin>>p>>val;

				update(1,1,n,-val,p);

			}else{//加

				int p,val;

				cin>>p>>val;

				update(1,1,n,val,p);

			}

		}

	}

	return 0;

}