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[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; }