首页 > > 程序设计 > C/C++ >

线段树 poj 3468

2018-06-17 22:51:04来源：未知阅读 ()

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

Hint

The sums may exceed the range of 32-bit integers

#include<iostream>
#include<stdio.h>
using namespace std;
struct node
{
    long long l_,r_,number,mark;
};
class segment_tree //这个代码是A不了的 应为用类 重复申请内存勒  把类取消了就可以了   思路最重要嘛 
{
    private:
        node data[100001*4];//储存 需要开四倍  怎么算的我也不知道 二叉树叶子节点 为n  总结点一定小于4n？ 
    public:
        void built(long long l,long long r,long long i)//建立线段树 
        {
            data[i].l_=l;data[i].r_=r;data[i].mark=0;data[i].number=0;
            if(l==r){   //如果是叶子节点 
            cin>>data[i].number; return ;}
            else
            {
                int mid=(l+r)/2;
                built(l,mid,i*2); //不是就往下建立左右孩子 
                built(mid+1,r,i*2+1);
            }
            data[i].number=data[i*2].number+data[i*2+1].number;
        }
        void down_mark(long long i)//更新缓存 
        {
            data[i*2].number+=data[i].mark*(data[i*2].r_-data[i*2].l_+1);
            data[i*2+1].number+=data[i].mark*(data[i*2+1].r_-data[i*2+1].l_+1);
            data[i*2].mark+=data[i].mark;  data[i*2+1].mark+=data[i].mark;
            data[i].mark=0; 
        }
        void add(long long l,long long r,long long x,long long i)//刷新区域； 
        {
            if(data[i].l_==l&&data[i].r_==r)
            {
                data[i].number+=(data[i].r_-data[i].l_+1)*x;
                data[i].mark+=x; return ;
            }
            if(data[i].mark) down_mark(i);
            int mid=(data[i].l_+data[i].r_)/2;
            if(l>=mid+1) add(l,r,x,i*2+1);//区间全在右孩子 
            else if(r<=mid) add(l,r,x,i*2); //区间全在左孩子 
            else{                              //左右各一部分 
                add(l,mid,x,i*2);
                add(mid+1,r,x,i*2+1);
            }
            data[i].number=data[i*2].number+data[i*2+1].number;
        }
        long long query(long long l,long long r,long long i)//查询 
        {
            if(l==data[i].l_&&data[i].r_==r)
            return data[i].number;
            if(data[i].mark) down_mark(i);
            int mid=(data[i].l_+data[i].r_)/2;
            if(l>=mid+1) return query(l,r,i*2+1);
            else if(r<=mid) return query(l,r,i*2);
            else{
                return query(l,mid,i*2)+query(mid+1,r,i*2+1);
            }
        }
};
long long m,n,a,b,c;
char ch[2];
int main()//这里吐槽一句 真的不想用scanf。。。 太不习惯了 
{
    while(scanf("%lld%lld",&m,&n)!=EOF)
    {
        segment_tree q;
        q.built(1,m,1);
        while(n--)
        {
            scanf("%s,",&ch);//cin>>ch;  
            if(ch[0]=='Q'){
                scanf("%lld%lld",&a,&b);//cin>>a>>b;
                 cout<<q.query(a,b,1)<<endl;
            }
            else{
                scanf("%lld%lld%lld",&a,&b,&c);//cin>>a>>b>>c; 
                q.add(a,b,c,1);
            }
        }
    }
    return 0;
}