线段树

发表于

线段树是一个能在 $O(logn)$ 的时间复杂度内进行区间修改和区间查询操作的数据结构。非常神奇！

建树操作

考虑如何构建一颗线段树：

我们对于一个区间 $[l, r]$ ，我们将其分为两个子区间 $[l, mid]$ 和 $[mid + 1, r]$ ，其中 $mid = \frac{l + r}2$ ，对于每一个区间采用递归的方式去建树，知道区间长度为 $1$ ，则将其作为叶子节点(具体参考代码)。

线段树的思想为我们在修改的同时维护每一个子区间，由子区间合并为一个大区间，所以支持区间快速合并的即可用线段树维护。其体现了一个均摊的思想。

对于代码会在最后一起给出。

Lazy-tag

非常明确地，如果是单点修改，我们只需要一直向上递归修改即可，但对于区间修改，如果我们采用暴力一点一点修改的话时间复杂度为 $O(nlogn)$，不如暴力……

我们似乎需要懒一点，不要修改的那么勤奋，最好是仅仅先修改需要用到的就可以了，所以，我们非常机制地引入了一个 Lazy-tag 的思想。

对于 Lazy-tag 即对于每一个节点多维护一个 tag 变量，假如说我们有一个节点维护的区间为 $[a, b]$ ，那么当我们需要修改整个 $[a, b]$ 的信息，如将区间 $[a, b]$ 的数全部加 $c$ ，我们可以暂时仅仅修改维护区间 $[a, b]$ 的这一个节点，暂时忽略其子区间的节点，同时我们给维护区间 $[a, b]$ 的节点上打一个 tag ，即说明此节点包含的区间被整体增加了 tag ，方便日后查询其子区间时修正，然后把维护区间 $[a, b]$ 节点的 sum 直接增加 $c * (b - a + 1)$ 即可。

区间查询

区间查询不多说了，递归查询子区间即可

另外需要注意在查询或修改到一个节点时必须将标记进行下放，即 pushdown 操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct Sgt{
    Sgt *lc, *rc;
    int sum, tag, l, r;
    Sgt(Sgt *lc, Sgt *rc, int l, int r) : lc(lc), rc(rc), l(l), r(r) {}
    static Sgt *build(int l, int r){
        int mid = l + r >> 1;
        return l == r ? new Sgt(0, 0, l, r) : new Sgt(build(l, mid), build(mid + 1, r), l, r);
    }
    void cover(int delta){
        sum += (r - l + 1) * delta;
        tag += delta;
    }
    void pushdown(){
        if(tag){
            lc->cover(tag), rc->cover(tag);
            tag = 0;
        }
    }
    void Add(int al, int ar, int delta){
        if(al > r || ar < l)    return;
        else if(al <= l && r <= ar) cover(delta);
        else    pushdown(), lc->Add(al, ar, delta), rc->Add(al, ar, delta), sum = lc->sum + rc->sum;
    }
    int Query(int al, int ar){
        if(al > r || ar < l)    return 0;
        else if(al <= l && r <= ar) return sum;
        else    return pushdown(), lc->Query(al, ar) + rc->Query(al, ar);
    }
}*sgt;

To be continued…