#include <stdio.h>

#define MAXN 410000

struct Node
{
	__int64 sum ;
	int	begin, end ;
	Node () {sum = 0 ; begin = end = 0 ;}
} tree[MAXN] ;


void Build (int subroot, int b, int e)
{
	tree[subroot].begin = b ;
	tree[subroot].end = e ;
	if (b < e)
	{
		int mid = (b + e) / 2 ;
		Build (2 * subroot, b, mid) ;
		Build (2 * subroot + 1, mid + 1, e) ;
	}
}

void Insert (int subroot, int b, int e, int value)
{
	
	tree[subroot].sum += value * (e - b + 1) ;
	if (tree[subroot].begin < tree[subroot].end)
	{
		int mid = (tree[subroot].begin + tree[subroot].end) / 2 ;	
		if (e <= mid)		Insert (2 * subroot, b, e, value) ;
		else if (b > mid)	Insert (2 * subroot + 1, b, e, value) ;
		else
		{
			Insert (2 * subroot, b, mid, value) ;
			Insert (2 * subroot + 1, mid + 1, e, value) ;
		}
	}
}

__int64 Query (int subroot, int b, int e)
{
	if (tree[subroot].begin == b && tree[subroot].end == e)
		return tree[subroot].sum ;
	else
	{
		int mid = (tree[subroot].begin + tree[subroot].end) / 2 ;
		if (e <= mid)		return Query (2 * subroot, b, e) ;
		else if (b > mid)	return Query (2 * subroot + 1, b, e) ;
		else
			return Query (2 * subroot, b, mid) + Query (2 * subroot + 1, mid + 1, e) ;
	}
}

int main ()
{
	int N, Q, a, b, c, i, temp ;
	int root = 1 ;
	char choice[10] ; ;

	scanf ("%d%d", &N, &Q) ;
	Build (root, 1, N) ;

	for (i = 1 ; i <= N ; i++)
	{
		scanf ("%d", &temp) ;
		Insert (root, i, i, temp) ;
	}

	while (Q--)
	{
		getchar () ;
		scanf ("%s", choice) ;
		if (choice[0] == 'Q')
		{
			scanf ("%d%d", &a, &b) ;
			printf ("%I64d\n", Query (root, a, b)) ;
		}
		else
		{
			scanf ("%d%d%d", &a, &b, &c) ;
			Insert (root, a, b, c) ;
		}
	}
	
	return 0 ;
}

• Re:我用线段树，为什么会超时呢？是不是进入死循环了？ (1945) yueashuxia 2010-07-30 14:17:29