poj3468A Simple Problem with Integers(线段树，在段更新时要注意)

Description

You have N integers, A₁, A₂, ... , A_N. 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 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₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a₊₁, ... , A_b.

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

在段更新和查找时要注意，当父节点的下方和子节点的下方同时须要更新时不能直接覆盖了子节点的num，而是要加起来。

#include<iostream>
#include<stdio.h>
using namespace std;
#define N 100100
struct Tree
{
    __int64 sum,num;//分别表示当前段的总和，子点的每个点所要加的值
    bool b;//判断子节点是否要更新
}tree[4*N];
__int64 init[N+5];//初始时每个点的值
void builde(int l,int r,int k)
{
    int m=(l+r)/2;
    tree[k].b=false; tree[k].num=0;
    if(l==r)
    {
        tree[k].sum=init[r]; return ;
    }
    builde(l,m,k*2);
    builde(m+1,r,k*2+1);
    tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
}
void set_child(int l,int r,int k)
{
    int m=(l+r)/2;
    if(tree[k*2].b==true)//注意这里，不能直接覆盖了
        tree[k*2].num+=tree[k].num;
    else
        tree[k*2].num=tree[k].num;
    tree[k*2].sum+=(m-l+1)*tree[k].num;

    if(tree[k*2+1].b==true)
        tree[k*2+1].num+=tree[k].num;
    else
        tree[k*2+1].num=tree[k].num;
    tree[k*2+1].sum+=(r-m)*tree[k].num;
    tree[k*2].b=tree[k*2+1].b=true;
}
void updata(int l,int r,int k,int L,int R,__int64 num)
{
    int m=(l+r)/2;
    if(L<=l&&r<=R)
    {
        if(tree[k].b==true)
            tree[k].num+=num;
        else
            tree[k].num=num;
        tree[k].sum+=(r-l+1)*num;
         tree[k].b=true;
        return ;
    }
    if(tree[k].b==true)
        set_child(l,r,k);
    if(L<=m) updata(l,m,k*2,L,R,num);
    if(R>m) updata(m+1,r,k*2+1,L,R,num);
    tree[k].b=false;
    tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
}
__int64 SUM;
void calculate(int l,int r,int k,int L,int R)
{
    int m=(l+r)/2;
    if(L<=l&&r<=R)
    {
        SUM+=tree[k].sum; return ;
    }
    if(tree[k].b==true)
        set_child(l,r,k);
    if(L<=m) calculate(l,m,k*2,L,R);
    if(R>m) calculate(m+1,r,k*2+1,L,R);
    tree[k].b=false;
}
int main()
{
    int n,m,L,R,i;
    __int64 num;
    char ch[2];
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%I64d",&init[i]);
        getchar();
        builde(1,n,1);
    while(m--)
        {
            scanf("%s%d%d",ch,&L,&R);
            if(ch[0]=='Q')
            {
                SUM=0; calculate(1,n,1,L,R);
                printf("%I64d
",SUM);
            }
            else
            {
                scanf("%I64d",&num);
                updata(1,n,1,L,R,num);
            }
        }
}