poj3468 Simple Problem with Integers (线段树)

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of A_a, A_a+1, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a+1, ... , A_b.

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

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<iostream>
using namespace std;

struct node
{
	long long int  num;
	long long int left, right,mark;
};

node shu[2000000];

void creatshu(long long int l,long long int r,int i)
{
	shu[i].left = l;
	shu[i].right = r;
	shu[i].mark = 0;
	shu[i].num = 0;
	if (l==r)
	{
		scanf("%lld", &shu[i].num);
		return;
	}
	long long int mid = (l + r) / 2;
	creatshu(l, mid, i * 2);
	creatshu(mid + 1, r, i * 2 + 1);
	shu[i].num = shu[i * 2].num + shu[i * 2 + 1].num;
	return;
}

void pushnext(long long mark, int i)
{
	shu[i].mark += mark;
	shu[i].num += (shu[i].right - shu[i].left + 1)*mark;
}

void add(long long int l,long long  int r, long long int mark, int i)
{
	if (shu[i].left == l && shu[i].right == r)
	{
		shu[i].num += (shu[i].right - shu[i].left + 1)*mark;
		shu[i].mark += mark;
	}
	else
	{
		long long int mid = (shu[i].left + shu[i].right) / 2;
		/*if (shu[i].mark != 0)
		{
			add(shu[i].left, mid, shu[i].mark, i * 2);
			add(mid+1, shu[i].right, shu[i].mark, i * 2 + 1);
			shu[i].mark = 0;
		}*/
		if (shu[i].mark != 0)
		{
			pushnext(shu[i].mark, i * 2);
			pushnext(shu[i].mark, i * 2 + 1);
			shu[i].mark = 0;
		}
		 shu[i].num += (r - l + 1)*mark;
		if (r <= mid)
		{
			add(l,r, mark, i * 2);
		}
		else if (l > mid)
		{
			add(l,r, mark, i * 2 + 1);
		}
		else if (l <= mid && r > mid)
		{
			add(l, mid, mark, i * 2);
			add(mid + 1, r, mark, i * 2 + 1);
		}
	}
}




long long int search(long long int l,long long int r,int i)
{
	if (shu[i].left == l && shu[i].right == r)
	{
		return shu[i].num; 
	}
	else
	{
		long long int mid = (shu[i].left + shu[i].right) / 2;
	 /*f (shu[i].mark!=0)
	 {
		 if (r <= mid)
		 {
			 add(l, r, shu[i].mark, i * 2);
		 }
		 else if (l > mid)
		 {
			 add(l, r, shu[i].mark, i * 2 + 1);
		 }
		 else if (l <= mid && r > mid)
		 {
			 add(l, mid, shu[i].mark, i * 2);
			 add(mid + 1, r, shu[i].mark, i * 2 + 1);
		 }
		 shu[i].mark = 0;
	 }*/
			if (shu[i].mark != 0)
			{
				pushnext(shu[i].mark, i * 2);
				pushnext(shu[i].mark, i * 2 + 1);
				shu[i].mark = 0;
			}
		if (r <= mid)
		{
			return search(l, r, i * 2);
		}
		else if (l > mid)
		{
			return search(l, r, i * 2 + 1);
		}
		else if (l <= mid && r > mid)
		{
			return search(l, mid, i * 2)+search(mid+1,r,i*2+1);
			
		}
	}
}

int main()
{
	long long int len, ordernum;
	while (~scanf("%lld %lld", &len, &ordernum))
	{
		creatshu(1, len, 1);
		char order[100];
		long long int left, right,mark;
		for (int i = 0; i < ordernum; i++)
		{
			scanf("%s", order);
			if (order[0] == 'Q')
			{
				scanf("%lld %lld", &left, &right);
				printf("%lld\n", search(left, right, 1));
			}
			
			else if (order[0] == 'C')
			{
				scanf("%lld %lld %lld", &left, &right, &mark);
				add(left, right, mark, 1);
			}
		}
	}
	return 0;
}