A Simple Problem with Integers
Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 75541 Accepted: 23286 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 4Sample Output
4
55
9
15Hint
The sums may exceed the range of 32-bit integers.Source
POJ Monthly--2007.11.25, Yang Yi
朴素的向下更新会产生很多不必要的操作，所以lazy思想便是，用到再更新，不用就暂存到当前区间。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <climits>
#include <queue>
#define ll long long using namespace std; //lazy思想的线段树区间更新，区间查询，感觉不难 const int MAX = ;
ll num[MAX]; struct nodes
{
int left,right;
ll large,add;
} tree[MAX*]; void pushup(int root)//代替递归向上更新
{
tree[root].large = tree[root*].large + tree[root*+].large;
}
void pushdown(int root)//递归向下更新
{
if(tree[root].add)
{
tree[root*].add += tree[root].add;
tree[root*+].add += tree[root].add;
tree[root*].large += tree[root].add * (tree[root*].right - tree[root*].left + );
tree[root*+].large += tree[root].add * (tree[root*+].right - tree[root*+].left + );
tree[root].add = ;
}
}
void build(int root,int left,int right)//建树过程，也是初始化更新过程
{
tree[root].left = left;
tree[root].right = right;
tree[root].add = ;//不能忘记这个值的初始化为0
if(left == right)
{
tree[root].large = num[left];
return;//注意这里的递归结束条件
} int mid = (left+right)/; build(*root,left,mid);
build(*root+,mid+,right); pushup(root);//该子区间建立好后，该区间更新
} void update(int root,int left,int right,ll val)
{
if(left == tree[root].left && right == tree[root].right) // 刚好进入到所需区间，就可以更新到当前区间直接返回
{
tree[root].add += val; // 用当前节点的add变量记录区间每个元素的累加量
tree[root].large += val * (right - left + );//更新当前区间和
return;
}
pushdown(root); //否则向下更新一层，继续找合适区间
int mid = (tree[root].left+tree[root].right)/;
if(left <= mid && right > mid)
{
update(*root,left,mid,val);
update(*root+,mid+,right,val);
}
else if(left > mid)
{
update(*root+,left,right,val);
}
else
{
update(*root,left,right,val);
}
pushup(root);
} ll query(int root ,int left,int right)
{
if(left == tree[root].left && right == tree[root].right) //如果是合适区间，直接返回节点值
{
return tree[root].large;
}
pushdown(root); //否则向下更新一层，继续查找合适区间
int mid = (tree[root].left+tree[root].right)/;
ll ans = ;
if(right > mid && left <= mid)
{
ans += query(*root,left,mid);
ans += query(*root+,mid+,right);
}
else if(left > mid)
{
ans += query(*root+,left,right);
}
else
{
ans += query(*root,left,right);
}
return ans;
} int main(void)
{
int n,q,i,x,y;
ll c;
char cmd;
scanf("%d %d",&n,&q);
for(i = ; i <= n; i++)
scanf("%lld",&num[i]);
build(,,n);
for(i = ; i < q; i++)
{
getchar();
scanf("%c",&cmd);
if(cmd == 'Q')
{
scanf("%d %d",&x,&y);
printf("%lld\n",query(,x,y));
}
else
{
scanf("%d %d %lld",&x,&y,&c);
update(,x,y,c);
}
}
return ;
}