RenaMoe's Blog

念念不忘，必有回响

0%

总结 线段树/树状数组

发表于 更新于 分类于 ， Valine：

虽然是总结，但是真的讲不出点啥，贴个板子就溜

毕竟就我自己看

树状数组

单点修改，区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define lowbit(x) (x & -x)

inline void update(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += k;
}

inline int query(int x) {
    int ans = 0;
    for (int i = x; i; i -= lowbit(i))
        ans += tr[i];
    return ans;
}

// 修改
update(x, k)
// 查询l到r区间和
query(r) - query(l-1)

单点修改，区间查询好像还能CDQ分治

进阶操作：区间修改，单点查询

用树状数组维护差分序列

1
2
3
4
5
// 区间修改
update(l, k)
update(r+1, -k)
// 单点查询
query(x)

很多时候需要配合二分，直接套上去是 \(\mathcal O(\log^2 n)\) 的。

树状数组虽然是拍扁的线段树，但是仍然保留不少好的性质，其实可以在树状数组上二分的，单次 \(\mathcal O(\log n)\)。

线段树

区间修改，区间查询

要开4倍空间

每个节点的l，r可以存下来，也可以现算（卡空间的话）

包装起来比较优美

最好动态开点（存\(lson\)和\(rson\)），当成二叉堆存也行（比较难调，还丑）

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
struct Segtree {
    struct Leave {
        int ls, rs, sum, lazy;
    };
    Leave tr[N<<2];
    int cnt;
    int val[N];

    inline void push_up(int suc) {
        tr[suc].sum = tr[tr[suc].ls].sum + tr[tr[suc].rs].sum;
    }

    inline void push_down(int suc, int L, int R) {
        int ls = tr[suc].ls, rs = tr[suc].rs, mid = (L + R) >> 1;
        tr[ls].lazy += tr[suc].lazy;
        tr[ls].sum += (mid - L + 1) * tr[suc].lazy;
        tr[rs].lazy += tr[suc].lazy;
        tr[rs].sum += (R - mid) * tr[suc].lazy;
        tr[suc].lazy = 0;
    }

    void build(int suc, int L, int R) {
        tr[suc].lazy = 0;
        if (L == R) {
            tr[suc].sum = val[L];
            return;
        }
        int mid = (L + R) >> 1;
        tr[suc].ls = ++cnt, tr[suc].rs = ++cnt;
        build(tr[suc].ls, L, mid), build(tr[suc].rs, mid+1, R);
        push_up(suc);
    }

    void change(int suc, int L, int R, int cl, int cr, int k) {
        if (cl <= L && R <= cr) {
            tr[suc].sum += (R - L + 1) * k;
            tr[suc].lazy += k;
            return;
        }
        push_down(suc, L, R);
        int mid = (L + R) >> 1;
        if (cl <= mid)
            change(tr[suc].ls, L, mid, cl, cr, k);
        if (cr > mid)
            change(tr[suc].rs, mid+1, R, cl, cr, k);
        push_up(suc);
    }

    int query(int suc, int L, int R, int ql, int qr) {
        if (ql <= L && R <= qr)
            return tr[suc].sum;
        push_down(suc, L, R);
        int mid = (L + R) >> 1;
        if (qr <= mid)
            return query(tr[suc].ls, L, mid, ql, qr);
        if (ql > mid)
            return query(tr[suc].rs, mid+1, R, ql, qr);
        return query(tr[suc].ls, L, mid, ql, qr) + query(tr[suc].rs, mid+1, R, ql, qr);
    }
};

线段树基本上都套板子，会魔改的只有\(push\_up()\)和\(query()\)的合并操作

势能线段树

没有 lazy tag 的暴力修改。

区间开根

SP2713

每个数开方几次就会变成1，暴力修改即可。

打tag记录区间是否都为1。

区间改成约数

CF920F

同上。

线段树维护序列操作

基本上都是多了维护前缀答案和后缀答案，从而利于合并。

区间最大子段和

SPOJ1043

SPOJ1716

记录每个节点的最大子段和，最大前缀，最大后缀，区间和。

区间涂色

P2894

维护前缀空房数和后缀空房数，同上。

线段树合并

合并的是动态开点线段树。

若两棵树重合的点数为 \(m\)，单次合并复杂度 \(\mathcal O(m\log n)\)，所以适用于插入点数较少的情况。

注意线段树空间复杂度 \(\mathcal O(n\log n)\)，\(n=10^5\) 的话开到 \(5\times 10^6\) 吧。

个人觉得还算好理解。

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
30
31
32
33
34
struct SegTree {
    int cnt;
    int sum[NN], ans[NN], ls[NN], rs[NN], rt[N];
    inline void push_up(int suc) {
        sum[suc] = max(sum[ls[suc]], sum[rs[suc]]);
        if (sum[ls[suc]] >= sum[rs[suc]]) ans[suc] = ans[ls[suc]];
        else ans[suc] = ans[rs[suc]];
    }
    void update(int &suc, int l, int r, int x, int k) {
        if (!suc) suc = ++cnt;
        if (l == r) {
            sum[suc] += k;
            ans[suc] = sum[suc] > 0 ? l : 0;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) update(ls[suc], l, mid, x, k);
        else update(rs[suc], mid + 1, r, x, k);
        push_up(suc);
    }
    int merge(int u, int v, int l, int r) {
        if (!u || !v) return u + v;
        if (l == r) {
            sum[u] += sum[v];
            ans[u] = sum[u] > 0 ? l : 0;
            return u;
        }
        int mid = (l + r) >> 1;
        ls[u] = merge(ls[u], ls[v], l, mid);
        rs[u] = merge(rs[u], rs[v], mid + 1, r);
        push_up(u);
        return u;
    }
} T;

一些题目