| Time Limit: 5000MS | Memory Limit: 131072K | |
| Total Submissions: 97008 | Accepted: 30285 | |
| Case Time Limit: 2000MS | ||
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
Source
【题解】
线段树的区间递增。
输入数据的时候，要用到build过程，只有到达最底端的节点的时候，才输入这个节点。然后要记得往上更新它的父亲节点。即由sum[左儿子],sum[右儿子]，更新sum[爸爸]。
然后是懒惰标记的使用<=修改。
我们到达的这个节点，如果它所代表的区间，被所询问的区间所覆盖。则直接修改这个节点的sum值即可，至于它的儿子们，则只要标记一下即可(add[rt] = xx)，等我们需要访问它的时候再往下更新即可。
其他的则没有啥了。
【代码】
#include <cstdio>
int n, q;
__int64 sum[100001 * 4] = { 0 }, add[100001 * 4] = { 0 }; //开4倍是保险的做法。
void downpush(int rt, int len)//查看rt这个节点有没有懒惰标记。如果有的话就给它的儿子们贴上标记，同时清楚这个
{//标记，同时更新儿子的sum信息。
if (add[rt] != 0)
{
add[rt << 1] += add[rt];//左儿子加上父节点的懒惰标记值。
add[rt << 1 | 1] += add[rt];//右儿子也要加上父节点的懒惰标记值。
sum[rt << 1] += (len - (len >> 1))*add[rt];//左儿子的sum值要根据懒惰标记改变。不能写成(len - (len >> 1))*add[rt<<1],因为可能add[rt<<1]
//在未加上add[rt]之前已经不等于0了，而那个add[rt<<1]之前是已经累加过的，不能重复累加。
//这里的len-(len >> 1)则是这个区间它的长度。给每个位置都加上add[rt]。总和就是....
sum[rt << 1 | 1] += (len >> 1)*add[rt];//右儿子则是同理。
add[rt] = 0;//懒惰标记已经操作过了。就置为0；
}
}
void uppush(int rt) //这是对儿子节点进行操作过后。回溯父节点的时候更新sum[rt]；
{
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void updata(int l, int r, int num, int begin, int end, int rt)//要求的区间是l,r，当前节点rt所代表的区间为begin,end;要增加的值为num;
{
if (l <= begin && end <= r) //如果当前这个节点所代表的区间被所要求的区间覆盖。那么就直接修改这个区间的和，然后加上懒惰标记
{//表示它的儿子节点们没有更新过。下次要记得更新。
add[rt] += num;
sum[rt] += (end - begin + 1)*num;//修改这个节点所代表的区间的区间和。
return;
}
downpush(rt, end - begin + 1);//看看这个节点有没有懒惰标记，如果有的话就先处理懒惰标记。
int m = (begin + end) >> 1;//获取中间节点。
if (l <= m)
updata(l, r, num, begin, m, rt << 1);//如果所要求的区间和当前这个节点所代表的区间的左半部分有交集，则递归往左递增。
//这样会不断地缩小区间。直到节点所代表的区间被那个交集覆盖(可能被分成了很多块)
if (m < r)//右边也是一样的，如果有小的区间有交集。则递归右边。
updata(l, r, num, m + 1, end, rt << 1 | 1);
uppush(rt);//这是用节点的儿子来更新节点的sum值。
}
void build(int l, int r, int rt)//建树的过程<=>也即输入数据的过程(把数据输入到整棵树的最下面(叶子节点处)
{
if (l == r)
{
scanf("%I64d", &sum[rt]);//输入数据
return;
}
int mid = (l + r) >> 1;//获取中点
build(l, mid, rt << 1);//然后往左递归
build(mid + 1, r, rt << 1 | 1);//往右递归
uppush(rt);//然后根据儿子的sum信息来更新当前节点rt的sum信息。
}
__int64 query(int l, int r, int begin, int end, int rt)//所询问的区间是l,r然后当前节点rt所代表的区间为begin,end;
{
if (l <= begin && end <= r)
{
return sum[rt];//如果当前节点所代表的区间被所询问的区间所覆盖，则直接返回这个区间的和。
}
downpush(rt, end - begin + 1);//如果这个节点有懒惰标记，则要往下更新儿子节点的sum值。
int mid = (begin + end) >> 1;//返回这个区间的中点
__int64 re = 0;
if (l <= mid)//如果这个节点所代表的区间的左半部分和所询问的区间有交集。则递归寻找那个交集。顺便把那个交集的和累加一下。
re += query(l, r, begin, mid, rt << 1);
if (mid < r)//这个是右边有交集的情况。也是一样累加右边的交集的区间和就可以了。
re += query(l, r, mid + 1, end, rt << 1 | 1);
return re;//返回总的区间和。
}
int main()
{
//freopen("F:\rush.txt", "r", stdin);
//freopen("F:\rush_out.txt", "w", stdout);
scanf("%d%d", &n, &q);
build(1, n, 1); //输入n个数据
for (int i = 1; i <= q; i++)//输入q个操作。
{
char op[10];
scanf("%s", op);
int a, b, c;
if (op[0] == 'C')//如果是递增操作
{
scanf("%d%d%d", &a, &b, &c);
updata(a, b, c, 1, n, 1);//(a,b)的范围内都递增c。如果要递减，c就是负数，这点可以用在树状数组上面。
}
else
{
scanf("%d%d", &a, &b);//这是询问区间和。
printf("%I64d
", query(a, b, 1, n, 1));
}
}
return 0;
}