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

Hint

The sums may exceed the range of 32-bit integers.

在这个题目中，他更新数据是成段更新，上面的题目都是一个点一个点更新，并且更新的次数不是很少，我们不可能去像点更新一样，将这些区域内的点都一个个更新过去。

前面提到过，线段树的每一个节点都代表着一段区间的性质，所以假如我们需要对于区间 [5,8] 里面的数都加上 10。（基于更新[2,2]后的那个线段树）。

A Simple Problem with Integers

如果我们将一个个点覆盖过去之后，现在的这课树是这样的。

我们可以发现对节点3来说，他所管辖的区间[5,8]都是要被更新的区间，并且他增加的指为40，即区间长度（4） * 修改的值（10）。我们可以发现，在区域更新的时候，对于一个节点来说，如果他所管理的区间被要更新的区间覆盖了，那我们就提早了知道这一个节点的值。

然后我们引入一个概念， lazy标记，还是对于开头的情况来说，如果我们使用了lazy标记之后，这一课线段树是这样的

A Simple Problem with Integers

在这一颗树上，我们只修改了2个节点，同时在节点3处增加了一个 lazy标记，在这个标记中 lazy = 10。(即整段区间内每一个点都要加上的值）。接下来，我们如果询问区间[1,8]的和，我们直接返回节点1就好了。如果我们询问区间 [3,8] 的和那么只需要返回 [3,4] + [5,8] 的值。我们可以看见如果不访问[5,8]的子区间的时候，我并不会用到里面的值。在这些时候，我们并不需要更新里面的值，更不更新都一样，不会被访问到。

如果我们现在需要查询 [1,5]的和，我们只需要将 lazy 标记下推，然后再更新对应的区间就好了。

A Simple Problem with Integers

然后我们返回 [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;
}

A Simple Problem with Integers

相关推荐