学步园

POJ-3468-A Simple Problem with Integers

http://poj.org/problem?id=3468

成段更新线段树

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 100005
int num[N];
struct cam
{
	int x;   //起点
	int y;   //终点
	__int64 sum;  //和
	int add;   //增量
}list[N*4];
void build(int k,int x,int y)
{
	int mid;
	list[k].add=0;
	list[k].x=x;
	list[k].y=y;
	if(list[k].x==list[k].y)
	{
		list[k].sum=num[x];
		return;
	}
    mid=(x+y)/2;
	build(k<<1,x,mid);
	build(k<<1|1,mid+1,y);
	list[k].sum=list[k<<1].sum+list[k<<1|1].sum;
}
void update(int k,int x,int y,int d)
{
	int mid;
	if(list[k].x==x&&list[k].y==y)
	{
		list[k].sum+=(list[k].y-list[k].x+1)*d;
		list[k].add+=d;
		return;
	}
	if(list[k].add!=0)
	{
		list[k<<1].sum+=(list[k<<1].y-list[k<<1].x+1)*list[k].add;
		list[k<<1|1].sum+=(list[k<<1|1].y-list[k<<1|1].x+1)*list[k].add;
		list[k<<1].add+=list[k].add;
		list[k<<1|1].add+=list[k].add;
		list[k].add=0;
	}
    mid=(list[k].x+list[k].y)/2;
	if(x>mid)
	update(k<<1|1,x,y,d);
	else if(y<=mid)
	update(k<<1,x,y,d);
	else
	{
		update(k<<1,x,mid,d);
		update(k<<1|1,mid+1,y,d);
	}
	list[k].sum=list[k<<1].sum+list[k<<1|1].sum;
}
__int64 find(int k,int x,int y)
{
	int mid;
	if(list[k].x==x&&list[k].y==y)
	return list[k].sum;
    if(list[k].add!=0)
	{
		list[k<<1].sum+=(list[k<<1].y-list[k<<1].x+1)*list[k].add;
		list[k<<1|1].sum+=(list[k<<1|1].y-list[k<<1|1].x+1)*list[k].add;
		list[k<<1].add+=list[k].add;
		list[k<<1|1].add+=list[k].add;
		list[k].add=0;
	}
	mid=(list[k].x+list[k].y)/2;
	if(x>mid)
	return find(k<<1|1,x,y);
	else if(y<=mid)
	return find(k<<1,x,y);
	return find(k<<1,x,mid)+find(k<<1|1,mid+1,y);
}
int main()
{
	int n,m,i;
	int a,b,d;
	char c;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	scanf("%d",&num[i]);
	build(1,1,n);
	while(m--)
	{
		getchar();
		c=getchar();
		if(c=='Q')
		{
			scanf("%d %d",&a,&b);
			printf("%I64d\n",find(1,a,b));
		}
		else 
		{
			scanf("%d %d %d",&a,&b,&d);
			update(1,a,b,d);
		}
	}
	return 0;
}