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.
Source
POJ Monthly--2007.11.25, Yang Yi
【分析】
很不错的数据结构，真的很不错....
跟树状数组有点像..
相比与普通线段树,zkw线段树具有标记永久化，简单好写的特点。
但zkw线段树占用的空间会相对大些，毕竟是2的阶乘...，然后应该不能可持久化吧(别跟我说用可持久化线段树维护可持久化数组....)
这样就不能动态分配内存了。。不过总体来说还是有一定的实用价值...
/*
宋代陆游
《临安春雨初霁》 世味年来薄似纱，谁令骑马客京华。
小楼一夜听春雨，深巷明朝卖杏花。
矮纸斜行闲作草，晴窗细乳戏分茶。
素衣莫起风尘叹，犹及清明可到家。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <queue>
#include <assert.h>
#include <map>
#include <ctime>
#include <cstdlib>
#include <stack>
#define LOCAL
const int INF = 0x7fffffff;
const int MAXN = + ;
const int maxnode = ;
using namespace std;
struct Node{
int l, r;
long long sum, d;
}tree[maxnode];
int data[MAXN], M;//M为总结点个数 //初始化线段树
void build(int l, int r){
for (int i = * M - ; i > ; i--){
if (i >= M){
tree[i].sum = data[i - M];
tree[i].l = tree[i].r = (i - M);//叶子节点
}
else {
tree[i].sum = tree[i<<].sum + tree[(i<<)+].sum;
tree[i].l = tree[i<<].l;
tree[i].r = tree[(i<<)+].r;
}
}
}
long long query(int l, int r){
long long sum = ;//sum记录和
int numl = , numr = ;
l += M - ;
r += M + ;
while ((l ^ r) != ){
if (~l&){//l取反，表示l是左节点
sum += tree[l ^ ].sum;
numl += (tree[l ^ ].r - tree[l ^ ].l + );
}
if (r & ){
sum += tree[r ^ ].sum;
numr += (tree[r ^ ].r - tree[r ^ ].l + );
}
l>>=;
r>>=;
//numl,numr使用来记录标记的
sum += numl * tree[l].d;
sum += numr * tree[r].d;
}
for (l >>= ; l > ; l >>= ) sum += (numl + numr) * tree[l].d;
return sum;
} void add(int l, int r, int val){
int numl = , numr = ;
l += M - ;
r += M + ;
while ((l ^ r) != ){
if (~l&){//l取反
tree[l ^ ].d += val;
tree[l ^ ].sum += (tree[l ^ ].r - tree[l ^ ].l + ) * val;
numl += (tree[l ^ ].r - tree[l ^ ].l + );
}
if (r & ){
//更新另一边
tree[r ^ ].d += val;
tree[r ^ ].sum += (tree[r ^ ].r - tree[r ^ ].l + ) * val;
numr += (tree[r ^ ].r - tree[r ^ ].l + );
}
l>>=;
r>>=;
tree[l].sum += numl * val;
tree[r].sum += numr * val;
}
//不要忘了往上更新
for (l >>= ; l > ; l >>= ) tree[l].sum += (numl+numr) * val;
}
int n, m; void init(){
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++) scanf("%d", &data[i]);
M = ;while (M < (n + )) M <<= ;//找到最大的段
build(, M - );
}
void work(){
while (m--){
char str[];
scanf("%s", str);
if (str[] == 'Q'){
int l, r;
scanf("%d%d", &l, &r);
printf("%lld\n", query(l, r));
}
else{
int val, l, r;
scanf("%d%d%d", &l, &r, &val);
if (val != ) add(l, r, val);
}
}
} int main(){ init();
work();
return ;
}