A Simple Problem with Integers
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.
在这个题目中， 他更新数据是成段更新， 上面的题目都是一个点一个点更新， 并且更新的次数不是很少， 我们不可能去像点更新一样， 将这些区域内的点都一个个更新过去。
前面提到过，线段树的每一个节点都代表着一段区间的性质， 所以假如我们需要对于区间 [5,8] 里面的数都加上 10。（基于更新[2,2]后的那个线段树）。
如果我们将一个个点覆盖过去之后， 现在的这课树是这样的。
我们可以发现对节点3来说， 他所管辖的区间[5,8]都是要被更新的区间，并且他增加的指为40，即 区间长度（4） * 修改的值（10）。 我们可以发现，在区域更新的时候， 对于一个节点来说， 如果他所管理的区间 被 要更新的区间 覆盖了， 那我们就提早了知道这一个节点的值。
然后我们引入一个概念， lazy标记， 还是对于开头的情况来说， 如果我们使用了lazy标记之后， 这一课线段树是这样的
在这一颗树上， 我们只修改了2个节点， 同时在节点3处增加了一个 lazy标记， 在这个标记中 lazy = 10。(即整段区间内每一个点都要加上的值）。接下来， 我们如果询问区间[1,8]的和， 我们直接返回节点1就好了。 如果我们询问区间 [3,8] 的和 那么只需要返回 [3,4] + [5,8] 的值。 我们可以看见如果不访问[5,8]的子区间的时候， 我并不会用到里面的值。 在这些时候， 我们并不需要更新里面的值， 更不更新都一样， 不会被访问到。
如果我们现在需要查询 [1,5]的和， 我们只需要将 lazy 标记下推，然后再更新对应的区间就好了。
然后我们返回 [1,4] + [5,5] 的值就好了。
总结就是：
lazy标记的含义就是延迟更新，在我们不需要访问区间内部时就保留lazy标记的值，如果需要访问内部的时候，我们要先将lazy标记下推， 因为可能lazy标记还需要继续往下走。
在区域更新的时候，如果 当前区间 被 更新的区间完全覆盖了， 就直接在这个节点加上 区间长度*修改的值， 并且更新这个点的lazy标记。
操作代码：
PushDown --- 将lazy标记下推
void PushDown(int rt, int llen, int rlen){
if(lazy[rt]){
lazy[rt*2] += lazy[rt];
lazy[rt*2+1] += lazy[rt];
tree[rt*2] += lazy[rt] * llen;
tree[rt*2+1] += lazy[rt] * rlen;
lazy[rt] = 0;
}
}
void Update(int l, int r, int rt, int L, int R, int C){
if(L <= l && r <= R){
tree[rt] += (LL)C*(r-l+1);
lazy[rt] += C;
return;
}
int m = (l+r) / 2;
PushDown(rt, m-l+1, r-m);
if(L <= m) Update(l, m, rt*2, L, R, C);
if(m < R) Update(m+1, r, rt*2+1, L, R, C);
PushUp(rt);
}
LL Query(int l, int r, int rt, int L, int R){
if(L <= l && r <= R) return tree[rt];
LL ans = 0;
int m = (l+r) / 2;
PushDown(rt, m-l+1, r-m);
if(L <= m) ans += Query(l, m, rt*2, L, R);
if(m < R) ans += Query(m+1, r, rt*2+1, L, R);
return ans;
}
注意的就是每次对子区间进行修改的时候，我们都需要提前先把lazy标记下推。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
const int N = 1e5+10;
using namespace std;
int t,n,q;
long long tree[N<<2];
long long lazy[N<<2];
int a[N];
void PushUp(int rt){
tree[rt] = tree[rt*2] + tree[rt*2+1]; ///区间和的更新操作
}
void PushDown(int rt, int llen, int rlen){
if(lazy[rt]){
lazy[rt*2] += lazy[rt];
lazy[rt*2+1] += lazy[rt];
tree[rt*2] += lazy[rt] * llen;
tree[rt*2+1] += lazy[rt] * rlen;
lazy[rt] = 0;
}
}
void Build(int l,int r,int rt){
// l,r 代表的是这个区间内的左端点 和 右端点， rt代表的是 [l,r] 这个区间内的值是存在哪一个位置的。
if(l==r){
//scanf("%d",&tree[rt]);
tree[rt] = a[l];
return;
}
int m=(l+r)/2;// 对于区间区分，我们一般将m点划入左半边区间
Build(l,m,rt*2);
Build(m+1,r,rt*2+1);
PushUp(rt); // PushUp 函数是通过2个子节点来更新现在这个节点的状态， 对于不同的要求需要不同的写法。
}
long long Query(int l,int r,int rt,int L,int R){// [L,R]为查询区间
if(L<=l&&r<=R){
return tree[rt];// 如果成立则满足查询区间覆盖了当前区间， 直接返回当前区间的值
}
int m=(l+r)/2;
long long res=0;
PushDown(rt, m-l+1, r-m);
if(L<=m) res+=Query(l,m,rt*2,L,R);//左边有一部分需要查询的区域。
if(m<R) res+=Query(m+1,r,rt*2+1,L,R);//右边有一部分。
return res;
}
void Updata(int l,int r,int rt,int L,int R,int C){// l,r,rt 与前面的定义一样， L代表的是要更新区间的位置，C代表的是修改后的值
if(L <= l && r <= R){// 这里不能写成 if(l == L) 因为有可能左端点恰好是要更新的位置， 但是还有右端点， 我们直接更新的只有区间 [L,L]。
tree[rt] += (long long)C*(r-l+1);
lazy[rt] += C;
return ;
}
int m=(l+r)/2;
PushDown(rt, m-l+1, r-m);
if(L<=m) Updata(l,m,rt*2,L,R,C);//要更新的区间在左边部分，所以往左边走，更新左边
if(m < R) Updata(m+1,r,rt*2+1,L,R,C);//要更新的区间在右边部分， 往右边走，更新右边
PushUp(rt);//更新完子节点之后需要更新现在的位置， 需要保证线段树的性质。
}
int main()
{
scanf("%d%d",&n,&q);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
Build(1,n,1);
char tmp[10];
int a,b,c;
while(q--){
scanf("%s",tmp);
if(strcmp(tmp,"C")==0){
scanf("%d%d%d",&a,&b,&c);
Updata(1,n,1,a,b,c);
}
if(strcmp(tmp,"Q")==0){
scanf("%d%d",&a,&b);
printf("%lld\n",Query(1,n,1,a,b));
}
}
//cout << "Hello world!" << endl;
return 0;
}
投递牛客等公司10个岗位 >