太暴力了，优化一下


> #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 ;
> }