POJ3468,A Simple Problem with Integers（線段樹-區間查詢-區間更新）

線段樹的裸題。

給定N個數，有兩種操作，一種使[a,b]區間内所有數加上c，另一種詢問[a,b]區間内所有數的和。

代碼如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e5+6;
const int inf=0x3f3f3f3f;
ll a[maxn];
struct Node
{
	int l,r;
	ll lazy,sum;	//lazy為更新延遲标記，sum記錄目前區間的數的總和
}tr[maxn<<2];

void push_up(int rt)	
{
	tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
}

void push_down(int rt)
{
	tr[rt<<1].lazy+=tr[rt].lazy;	//注意這裡是+=，不是=
	tr[rt<<1|1].lazy+=tr[rt].lazy;
	tr[rt<<1].sum+=(tr[rt<<1].r-tr[rt<<1].l+1)*tr[rt].lazy;
	tr[rt<<1|1].sum+=(tr[rt<<1|1].r-tr[rt<<1|1].l+1)*tr[rt].lazy;
	tr[rt].lazy=0;	//最後記得記得要指派為0
}

void build(int rt,int l,int r)
{
	tr[rt].l=l;	tr[rt].r=r;
	tr[rt].lazy=0;
	if(tr[rt].l==tr[rt].r)
	{
		tr[rt].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	push_up(rt);
}

void update(int rt,int l,int r,ll val)
{
	if(l<=tr[rt].l&&tr[rt].r<=r)
	{
		tr[rt].lazy+=val;	//這裡也是要+=，不是=
		tr[rt].sum+=(tr[rt].r-tr[rt].l+1)*val;
		return;
	}
	if(tr[rt].l==tr[rt].r)	return;
	if(tr[rt].lazy)
		push_down(rt);
	int mid=(tr[rt].r+tr[rt].l)>>1;
	if(mid<l)	update(rt<<1|1,l,r,val);
	else if(mid>=r)	update(rt<<1,l,r,val);
	else
	{
		update(rt<<1,l,mid,val);
		update(rt<<1|1,mid+1,r,val);
	}
	push_up(rt);	//最後面這個push_up别忘了
}

void query(int rt,int l,int r,ll &sum)
{
	if(l<=tr[rt].l&&tr[rt].r<=r)
	{
		sum+=tr[rt].sum;
		return;
	}
	if(tr[rt].l==tr[rt].r)	return;
	if(tr[rt].lazy)
		push_down(rt);	//query函數内也要記得用push_down函數
	int mid=(tr[rt].l+tr[rt].r)>>1;
	if(mid<l)	query(rt<<1|1,l,r,sum);
	else if(mid>=r)	query(rt<<1,l,r,sum);
	else
	{
		query(rt<<1,l,mid,sum);
		query(rt<<1|1,mid+1,r,sum);
	}
}

int main()
{
	int n,q;
	while(~scanf("%d%d",&n,&q))
	{
		for(int i=1;i<=n;++i)
			scanf("%lld",&a[i]);
		build(1,1,n);
		while(q--)
		{
			char s[2];
			int l,r;
			scanf("%s%d%d",s,&l,&r);
			if(s[0]=='Q')
			{
				ll sum=0;
				query(1,l,r,sum);
				printf("%lld\n",sum);
			}
			else
			{
				ll val;
				scanf("%lld",&val);
				update(1,l,r,val);
			}
		}
	}
	return 0;
}