题解 | 《算法竞赛进阶指南》整数的一个小问题

【题目】

给定长度为N的数列A，然后输入M行操作指令。
第一类指令形如“C l r d”，表示把数列中第l~r个数都加d。
第二类指令形如“Q X”，表示询问数列中第x个数的值。
对于每个询问，输出一个整数表示答案。

【题解】

区间更新，单点查询，第一反应要么树状数组，要么线段树。个人更擅长线段树，就说说线段树吧。线段树是一种数据结构，是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。设树的最高层即是区间最大的 $[1,N]$ ，那么最高层就会分出两个子结点，也就是最高层的左儿子和右儿子，左儿子被分配到 $[1,(1+N)>>1]$ 的区间，而右儿子被分配到 $[(1+N)>>1|1,N]$ 的区间，即是区间对半开，如果对上面的 $(1+N)>>1$ 和 $(1+N)>>1|1$ 不理解的，可以在草稿纸上算一下。这样的话，我们就可以规定每个树上的点所代表的左边界为 $l$ 、右边界为 $r$ ，那么当前点所代表的区间就是 $[l,r]$ ,左儿子就是 $[l,(l+r)>>1]$ ，右儿子就是 $[(l+r)>>1|1,r]$ 。那么我们就可以利用这个性质来建立线段树，即依照这个性质，建立叶结点到 $l==r$ ，也就是单个元素的时候。建立完成后，我们就可以使用线段树节省时间的一个核心思想，Lazy思想，也就是线段树中的懒标记，这个思想就在于每次的更新不会更新到最底层，而是更新到需要更新区间能完全覆盖的区间，比如假设我要更新 $[2,6]$ 区间，那么我可能就只更新 $[2,3]$ 和 $[4,6]$ 区间所在的两点，而不是更新深度很深的单点 $[2],[3],\dots,[6]$ 。那么我们有些小伙伴就会问，这样的话，下次要查询这些单点的话，值还是会跟原来的一样呀。这个的时候就需要懒标记来解决。即如果更新到被覆盖到的区间，就不继续往下更新，而是更新好这个区间的值后，做一个标记，比如更新的内容是+2，那么这个标记就+2。下次再查询或者更新到这个区间所在的点的时候，就往下面的左儿子和右儿子传递标记，让左儿子和右儿子所代表的区间更新标记所代表的值，并且左儿子和右儿子也做个这个标记，以之后遍历到它们时，能传给它们的左儿子和右儿子。具体的写法，可以看看下面的这道题的AC代码，试着理解一下。

时间复杂度：线段树的建树复杂度 $O(N)$ ，查询复杂度 $O(logN)$ ，更新复杂度 $O(logN)$ ，此题整体复杂度 $O(MlogN)$

#include<iostream>
#define Sca(x) scanf("%d",&x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Scl(x) scanf("%lld",&x)
#define For(i,x,y) for(int i=x;i<=y;i++)
#define Pri(x) printf("%d\n",x)
#define Prl(x) printf("%lld\n",x)
typedef long long ll;
using namespace std;
const int N = 1e5+5;
struct Segt{
    #define lc (p<<1)
    #define rc (p<<1|1)
    #define MID (tree[p].l+tree[p].r)>>1
    struct Seg{
        int l, r;
        ll sum, lz;
        void init(int left, int right, int val=0){ 
            l = left; 
            r = right; 
            sum = val; 
            lz = 0; 
        }
        void update(ll val){
            sum += val*(r-l+1);
            lz += val;
        }
    }tree[N<<2];

    void pushdown(int p){
        tree[p].sum = tree[lc].sum + tree[rc].sum;
    }

    void pushup(int p){
        tree[lc].update(tree[p].lz);
        tree[rc].update(tree[p].lz);
        tree[p].lz = 0;
    }

    void build(int l, int r, int p){
        tree[p].init(l, r);
        if(l==r){
            Scl(tree[p].sum);
            return ;
        }
        int mid = MID;
        build(l, mid, lc);
        build(mid+1, r, rc);
        pushdown(p);
    }

    void update(int l, int r, int p, int val){
        if(tree[p].l>=l&&tree[p].r<=r){
            tree[p].update(val);
            return ;
        }
        if(tree[p].lz) pushup(p);
        int mid = MID;
        if(l<=mid) update(l, r, lc, val);
        if(r>mid) update(l, r, rc, val);
        pushdown(p);
    }

    ll query(int pos,int p){
        ll sum = 0;
        if(tree[p].l==pos && tree[p].r==pos) return tree[p].sum;
        if(tree[p].lz) pushup(p);
        int mid = MID;
        if(pos<=mid) sum = query(pos, lc);
        if(pos>mid) sum = query(pos, rc);
        return sum;
    }
}t;


int main(){
    int n, m;
    Sca2(n, m);
    t.build(1, n, 1);
    For(i,1,m){
        char cmd; scanf(" %c", &cmd);
        if(cmd == 'C'){
            int l, r, d;
            scanf("%d%d%d", &l, &r, &d);
            t.update(l, r, 1, d);
        }
        else if(cmd == 'Q'){
            int pos; Sca(pos);
            Prl(t.query(pos,1));
        }
    }
}