pku -- 3468 A Simple Problem with Integers(線段樹)

題目連接配接：http://poj.org/problem?id=3468

Time Limit: 5000MS Memory Limit: 131072K

Total Submissions: 17698 Accepted: 4581

Case Time Limit: 2000MS

Description

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.

The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.

Each of the next Q lines represents an operation.

"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.

"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5

1 2 3 4 5 6 7 8 9 10

Q 4 4

Q 1 10

Q 2 4

C 3 6 3

Q 2 4

Sample Output

4

55

9

15

Hint

The sums may exceed the range of 32-bit integers.

題意：

給定Q (1 ≤ Q ≤ 100,000)個數A1,A2 … AQ,，

以及可能多次進行的兩個操作:

1) 對某個區間Ai … Aj的每個數都加n(n可變）

2) 求某個區間Ai … Aj的數的和

題目的資料規模容不得我們用簡單的方法去解決。

本人也是第一天接觸線段樹，在之前AC了一道比較水的線段樹後基本上能自己建構線段樹

本題的解法正是利用了線段樹。

值得注意的是 1.資料範圍，儲存資料必須用long long 或__int64儲存（除了區間可以用整形，其他最後用64位）

                   2.隻存和，會導緻每次加數的時候都要更新到葉子節點，速度太慢，這是必須要避免的。

本題樹節點結構：

struct CNode

{

    int a ,b; //區間起點和終點

    CNode * left, * right;

    long long nSum; //原來的和

    long long Inc; //增量c的累加

}; //本節點區間的和實際上是nSum+Inc*(R-L+1)

                 3.在增加時，如果要加的區間正好覆寫一個節點，則增加其節點的Inc值，不再往下走，否則要更新nSum,再将增量往下傳在查詢時，如果待查區間不是正好覆寫一個節點，就将節點的Inc往下帶，然後将Inc代表的所有增量累加到nSum上後将Inc清0，接下來再往下查詢

#include <iostream>
using namespace std;
#define MAXN 100010
int N,Q;

__int64 num[MAXN], ans ,x;

struct data
{
	__int64 sum,inc;
	int l,r;
}Tree[4*MAXN];

void CreateTree(int k,int l,int r)								//構樹
{
	Tree[k].l = l;
	Tree[k].r = r;
	Tree[k].inc = 0;
	if(l == r)
		Tree[k].sum = num[l];
	else
	{
		int mid=(l+r)>>1;
		CreateTree(k+k,l,mid);
		CreateTree(k+k+1,mid+1,r);
		Tree[k].sum = Tree[k+k].sum + Tree[k+k+1].sum;
	}
}


void Add(int k,int l,int r,__int64 inc)								//C操作
{
	if(Tree[k].l == l && Tree[k].r == r)
	{
		Tree[k].inc += inc;
	}
	else
	{
		int mid = Tree[k+k].r;
		Tree[k].sum += (r-l+1)*inc;
		if(l>mid)
			Add(k+k+1,l,r,inc);
		else if(r<=mid)
			Add(k+k,l,r,inc);
		else
		{
			Add(k+k ,l,mid,inc);
			Add(k+k+1 ,mid+1,r,inc);
		}
	}
}

void Query(int k,int l,int r,__int64 temp)
{
	temp += Tree[k].inc;
	if(Tree[k].l == l &&Tree[k].r == r)
	{
		ans+= Tree[k].sum + temp * (r-l+1);
	}
	else
	{

		int mid = Tree[k+k].r;
		if(l>mid)
			Query(k+k+1,l,r,temp);
		else if(r<=mid)
			Query(k+k,l,r,temp);
		else
		{
			Query(k+k ,l,mid,temp);
			Query(k+k+1 ,mid+1,r,temp);
		}
	}
}

int main()
{
	int i,j;
	char ch;
	while(scanf("%d%d",&N,&Q)!=EOF)
	{
		
		
		for(i=1;i<=N;i++)
			scanf("%I64d",&num[i]);
		
		CreateTree(1,1,N);

		while(Q--)
		{
			getchar();
			scanf("%c %d %d",&ch,&i,&j);
			if(ch=='Q')
			{
				ans = 0;
				Query(1,i,j,0);
				printf("%I64d\n",ans);
			}
			else
			{
				scanf("%I64d",&x);
				Add(1,i,j,x);
			}
		}
	}
}