高级数据结构入门——线段树篇

发表于2017-10-23更新于2022-02-06字数统计1.4k阅读时长10分

引言

　　线段树是一种二叉搜索树，能够对区间进行高效询问与修改（只要该操作满足结合律）。它常被用于解决区间最值查询（RMQ，即 Range Minimum/Maximum Query）、区间和查询，区间修改等问题。常见的线段树的实现方式分为两类：递归式与非递归式。相对来说，递归式线段树的灵活性更强，但其时空复杂度的常数往往更大；而非递归式线段树的代码更加简单，但其处理单点的复杂度要高于递归版线段树。当线段树应用于大规模数据时，通常会把多个分散区间提取出来，单独作为线段树的一个结点对待，以减少整个程序的内存消耗。这一技巧被称为线段树的离散化。

原理

　　为了便于讲解，笔者将本段分为以下几个步骤：构建、维护、查询。（非递归式线段树的原理部分仍在施工中……）

构建

　　递归版线段树的构建过程是自顶向下的，其实现的关键在于构建函数。我们先将整个区间作为参数传入构建函数，随后构建函数会检查该区间是否为单元素。如果是，则将数据存入该结点，反之，则将区间平分然后分别传入下一层构建函数，当下一层的构建函数执行完成时，该结点的左右子节点都必定已得到对应的区间的值。那么，将其求和并存入当前层结点内即可结束构建操作。

　　（以下为部分草稿，请读者先跳过该段。）（而非递归式线段树则是自底向上的，它的本质是一颗完全二叉树。为了便于操作，我们需要将整个线段树“压扁”然后存进数组里。首先，我们假设根结点所在的位置为 0 ，那么当我们选取的某个结点在数组中的位置是 N 时 ，其左子树的位置为 (N << 1) + 1，而其右子树的位置为 (N + 1) << 1，其父结点的位置则为 (N - 1) >> 1。）

维护

　“懒惰即是美德。”——《代码之髓》

　　线段树实现高效区间修改的原理，即是懒惰标记（Lazy-Tag）思想。简单地说，当我们进行区间修改的时候，我们并不是真正的修改与区间有交集的每一个结点，而是把修改信息储存在第一次访问到的被修改区间完整覆盖的结点上。那么，当我们在另一次修改里经过这些结点时（即此时这个被存放了修改信息的结点与修改区间存在交集但不被完全覆盖），我们只需将该结点储存的修改信息传递给这个结点的左右子结点即可。这一操作被称为下推（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
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//Solution to https://www.luogu.org/problem/show?pid=3372
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long INT64;
const int MAXN = (100000 << 2) + 10;
INT64 data[MAXN], tag[MAXN];
int n, m;

struct Node {
    int left, right;
    INT64 val;
};

Node tree[MAXN];

void build(int i, int l, int r) {
    tree[i].left = l;
    tree[i].right = r;
    if (l == r) {
        tree[i].val = data[l];
    } else {
        int mid = (l + r) >> 1;
        build(i << 1, l, mid);
        build((i << 1) | 1, mid + 1, r);
        tree[i].val = tree[i << 1].val + tree[(i << 1) + 1].val;
    }
}

void pushdown(int i) {
    int lc = i << 1;
    int rc = (i << 1) + 1;
    tree[lc].val += (tree[lc].right - tree[lc].left + 1) * tag[i];
    tree[rc].val += (tree[rc].right - tree[rc].left + 1) * tag[i];
    tag[lc] += tag[i];
    tag[rc] += tag[i];
    tag[i] = 0;
}

void update(int i, int x, int y, INT64 k) {
    int lc = i << 1, rc = (i << 1) | 1;
    if (tree[i].left > y || tree[i].right < x) return;
    if (x <= tree[i].left && tree[i].right <= y) {
        tree[i].val += (tree[i].right - tree[i].left + 1) * k;
        tag[i] += k;
    } else {
        if (tag[i]) pushdown(i);
        update(lc, x, y, k);
        update(rc, x, y, k);
        tree[i].val = tree[lc].val + tree[rc].val;
    }
}

INT64 query(int i, int x, int y) {
    int lc = i << 1, rc = (i << 1) + 1;
    if (x <= tree[i].left && tree[i].right <= y)
        return tree[i].val;
    if (tree[i].left > y || tree[i].right < x)
        return 0;
    if (tag[i]) pushdown(i);
    return query(lc, x, y) + query(rc, x, y);
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> data[i];
    }
    build(1, 1, n);
    int t, x, y; INT64 k;
    for (int i = 1; i <= m; i++) {
        cin >> t;
        if (t == 1) {
            cin >> x >> y >> k;
            update(1, x, y, k);
        } else {
            cin >> x >> y;
            cout << query(1, x, y) << endl;
        }
    }
    return 0;
}