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