POJ 3468(線分樹＋lazy思想)

#include <iostream>
#include <cstdio>
using namespace std;

__int64 total=0;
__int64 A[100000];

struct CNode
{
	int left,right;
	CNode *leftchild,*rightchild;
	__int64 sum;
	__int64 inc;
};

CNode* build(int l,int r)
{
	CNode* root=new CNode;
        root->left=l;
	root->right=r;
	root->sum=0;
	root->inc=0;
	root->leftchild=NULL;
	root->rightchild=NULL;
	if (l!=r)
	{
		int mid=(l+r)/2;
		root->leftchild=build(l,mid);
		root->rightchild=build(mid+1,r);
	}
	return root;
}

void add(int l,int r,int c,CNode* root)
{
	if (l<=root->left && r>=root->right)
	{
		root->inc+=c;
	}
	else
	{
		if (l>=root->left && r<=root->right)
		  root->sum+=(r-l+1)*c;
		else if (l>=root->left && r>root->right)
			root->sum+=(root->right-l+1)*c;
		else if (l<root->left && r>root->right)
			root->sum+=(root->right-root->left+1)*c;
		else
			root->sum+=(r-root->left+1)*c;
		if ( l<=(root->left+root->right)/2 ) add(l,r,c,root->leftchild);
		if ( r>(root->left+root->right)/2 ) add(l,r,c,root->rightchild);
	}
}

void getsum(int l,int r,CNode* root)
{
	if (l<=root->left && r>=root->right)
	{
		total+=root->sum;
		total+=(root->right-root->left+1)*root->inc;
	}
	else
	{
		root->sum+=(root->right-root->left+1)*root->inc;
		if (root->leftchild!=NULL)
		  root->leftchild->inc+=root->inc;
		if (root->rightchild!=NULL)
		  root->rightchild->inc+=root->inc;
		root->inc=0;
		if ( l<=(root->left+root->right)/2 ) getsum(l,r,root->leftchild);
		if ( r>(root->left+root->right)/2 ) getsum(l,r,root->rightchild);
	}
}

int main()
{
	int N,Q;
	int i;
	char ch;
	int a,b,c;
	
	scanf("%d%d",&N,&Q);
	CNode* root=build(1,N);
	scanf("%I64d",&A[0]);
	for (i=1;i<=N-1;i++)
	{
		scanf("%I64d",&A[i]);
		A[i]+=A[i-1];
	}
	getchar();
	while (Q--)
	{
		scanf("%c",&ch);
		if (ch=='Q')
		{
			scanf("%d%d",&a,&b);
			getchar();
			getsum(a,b,root);
			if (a>=2)
			  total+=A[b-1]-A[a-2];
			else
				total+=A[b-1];
			printf("%I64d
",total);
			total=0;
		}
		else
		{
			scanf("%d%d%d",&a,&b,&c);
			getchar();
			add(a,b,c,root);
		}
	}
	return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

__int64 A[100005];
__int64 total;

struct Node
{
	int l,r;
	struct Node *lchild,*rchild;
	__int64 sum,inc;
}Root;

void build(int l,int r,struct Node *root)
{
	root->l=l;
	root->r=r;
	root->lchild=root->rchild=NULL;
	root->sum=root->inc=0;
	if (l==r)
		return;
	int mid=(l+r)/2;
	root->lchild=new struct Node;
	build(l,mid,root->lchild);
	root->rchild=new struct Node;
	build(mid+1,r,root->rchild);
}

void add(int l,int r,int inc,struct Node *root)
{
	int mid=(root->l+root->r)/2;
	if (l<=root->l && r>=root->r)
	  root->inc+=inc;
	else if (l>mid)
	{
		root->sum+=(min(r,root->r)-l+1)*inc;
		add(l,r,inc,root->rchild);
	}
	else if (r<=mid)
	{
		root->sum+=(r-max(l,root->l)+1)*inc;
		add(l,r,inc,root->lchild);
	}
	else
	{
		root->sum+=(min(r,root->r)-max(l,root->l)+1)*inc;
		add(l,r,inc,root->lchild);
		add(l,r,inc,root->rchild);
	}
}

void query(int l,int r,struct Node *root)
{
	root->sum+=(root->r-root->l+1)*root->inc;
	if (root->lchild!=NULL)
		root->lchild->inc+=root->inc;
	if (root->rchild!=NULL)
		root->rchild->inc+=root->inc;
	root->inc=0;

	int mid=(root->l+root->r)/2;
	if (l<=root->l && r>=root->r)
		total+=root->sum;
	else if (l>mid)
		query(l,r,root->rchild);
	else if (r<=mid)
		query(l,r,root->lchild);
	else
	{
		query(l,r,root->lchild);
		query(l,r,root->rchild);
	}
}

int main()
{
	int N,Q,i,a,b,c;
	char s[2];
	scanf("%d%d",&N,&Q);
	scanf("%I64d",&A[1]);
	for (i=2;i<=N;i++)
	{
		scanf("%I64d",&A[i]);
		A[i]+=A[i-1];
	}
	build(1,N,&Root);
	for (i=1;i<=Q;i++)
	{
		scanf("%s",s);
		if (s[0]=='Q')
		{
			scanf("%d%d",&a,&b);
			query(a,b,&Root);
			total+=A[b]-A[a-1];
			printf("%I64d
",total);
			total=0;
		}
		else
		{
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,c,&Root);
		}
	}
}