学步园

我都有点崩溃了,我发现我从来没有将线段树写的成功过,,每次都不是这个毛病就是那个毛病,真的狠烦!

而且我也发现了,如果一直用tree[i]的形式写用以写错,,以后不这么用了,用两个数组好了.

而且如果可以的话,,我还真的需要写成简便的那种写法了,,,.明天再练习一天吧,,其实我的时间真的不多了...

加油

贴出代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

struct Tree{
	int a;
	int b;
	__int64 col;
	__int64 sum;
}tree[444444];

void pushup(int i)
{
	tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
}

void pushdown(int i,int m)
{
	if(tree[i].col)
	{
		tree[i<<1].col+=tree[i].col;
		tree[i<<1|1].col+=tree[i].col;
		tree[i<<1].sum+=(m-(m>>1))*tree[i].col;
		tree[i<<1|1].sum+=(m>>1)*tree[i].col;
		tree[i].col=0;
	}
}


void Buildtree(int i,int a,int b)
{
	tree[i].a=a;
	tree[i].b=b;
	tree[i].col=0;
	if(a==b)
	{
		scanf("%I64d",&tree[i].sum);
		return;
	}
	int mid=(a+b)>>1;
	Buildtree(i<<1,a,mid);
	Buildtree(i<<1|1,mid+1,b);
	pushup(i);
}

void update(int i,int a,int b,int val)
{
	if(a<=tree[i].a&&tree[i].b<=b)
	{
		tree[i].col+=val;
		tree[i].sum+=(tree[i].b-tree[i].a+1)*val;
		return;
	}
	pushdown(i,tree[i].b-tree[i].a+1);
	int mid=(tree[i].a+tree[i].b)>>1;
	if(a<=mid)
		update(i<<1,a,b,val);
	if(b>mid)
		update(i<<1|1,a,b,val);
	pushup(i);
}

__int64 query(int i,int a,int b)
{
	if(a<=tree[i].a&&tree[i].b<=b)
	{
		return tree[i].sum;
	}
	pushdown(i,tree[i].b-tree[i].a+1);
	int mid=(tree[i].a+tree[i].b)>>1;
	__int64 ans=0;
	if(a<=mid)
		ans+=query(i<<1,a,b);
	if(b>mid)
		ans+=query(i<<1|1,a,b);
	return ans;
}

int main()
{
	int N,M;
	scanf("%d%d",&N,&M);
	Buildtree(1,1,N);
	for(int i=1;i<=M;i++)
	{
		char que[5];
		int a,b,val;
		scanf("%s",que);
		if(que[0]=='C')
		{
			scanf("%d%d%d",&a,&b,&val);
			update(1,a,b,val);
		}
		else if(que[0]=='Q')
		{
			scanf("%d%d",&a,&b);
			__int64 ans=query(1,a,b);
			printf("%I64d\n",ans);
		}
	}
	return 0;
}