发布于 ，更新于 

线段树

闪击线段树

基本线段树

操作

push_up() 通过子区间计算父区间的数据

build() 将一段区间初始化成线段树

modify() * 修改单点数据 * 修改区间数据 (即 push_down())

query() 查询

push_down() 修改区间数据并递归修改子区间的数据

原理

还是用图理解

简单来说就是把一个区间整成类似上图的完全二叉树，父节点（区间）的数据可以由子节点（区间）的数据推出（如区间最大值，区间和等），同时父节点的更改可以推到子节点里。
可能有点抽象，但是把操作挨个解释就比较易懂了。

存储节点

使用结构体感觉比较清晰，配上指针就能脱离中括号的束缚了

1
2
3
4
5
6
7
8
9
10
11
12
struct Node {
    int u;
    int v;
    Node *lc, *rc;
    int l, r, mid;
    int lazy;  // 懒标记
    void init(int L, int R) {
        l = L;
        r = R;
        mid = l + r >> 1;
    }
} tr[N * 4];

同时 mid 是需要用到的变量，我这里选择直接存在里面，同时写一个初始化函数，直接传进去区间的左右端点，非常方便。

建立线段树

第一层区间为 \([l,r]\)

取 $mid = $

则第二层的区间分别是 \([l,mid], [mid+1,r]\)

目前节点为 \(u\)，线段树数组为 \(tr\)，build() 函数如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void build(Node* nod, int L, int R) {
    nod->init(L, R); // 记录区间范围
    if (L == R) { // 到达叶子节点就回溯
        nod->v = ori[L];
        nod->lc = nod->rc = tr; // 防止空指针，左右儿子指向第一个空节点
        return;
    }
    nod->lc = ++tail; // tail 是一个指向最后创建的节点的指针，这样是一个类似动态开点的操作
    nod->rc = ++tail;
    build(nod->lc, L, nod->mid);
    build(nod->rc, nod->mid + 1, R);
    push_up(nod);
}

查询

以区间和为例

设查询的区间为 \([l,r]\)，目前节点区间为 \([T_l,T_r]\)

则有二种情况

  1. \([l,r] \ni [T_l,T_r]\) 查询区间包含目前节点区间（因为每次查询都可能把查询区间切割开再下传，所以这种情况可视为严格包含）
  2. \([l,r]\cap[T_l,T_r] \neq \varnothing\)
  3. \([l,r]\not\ni[T_l,T_r]\) （不存在）

把第二种情况还需要再分开成三种情况

  1. \([l,r] \in [lc_l,lc_r]\) 即被左儿子区间包含
  2. \([l,r] \in [rc_l,rc_r]\) 即被右儿子区间包含
  3. \(l \leqslant mid , r > mid\) 即左右区间都不能单独覆盖查询区间，这种情况把查询区间从 mid 劈成两半再分别在左右儿子区间查询即可。

所以只用处理相应的情况就可以了

这里直接给出一个维护区间最大值的查询函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int query(Node* nod, int L, int R) {
    push_down(nod);
    
    if (nod->r == R && nod->l == L) { // 严格覆盖
        return nod->v;
    }
    
    if (nod->lc->r >= R) {
        return query(nod->lc, L, R);
    } else if (nod->rc->l <= L) {
        return query(nod->rc, L, R);
    } else {
        return query(nod->lc, L, nod->lc->r) + query(nod->rc, nod->rc->l, R);
    }
}

从子节点推出父节点数据

还是以区间和为例，父区间最大值为两个子区间最大值中的最大值。

1
2
3
void push_up(Node* nod) {
    nod->v = nod->lc->v + nod->rc->v;
}

修改区间值

理解起来其实挺简单的，比如给区间 \([L,R]\) 都加一个数 \(x\)，朴素写法直接用类似查询的方法递归到底部回溯的时候一个一个更新即可。

但是显然这样做效率很低，对于长度为 \(n\) 的一个区间，最坏情况下它对应 \(\log n\) 个极大区间（这些区间不存在可以合并的两个）；对于每一个极大区间来说修改它和它所有子区间的值的时间复杂度显然是他的长度，即 \(\operatorname{O}(len)\)。则如上朴素写法每次修改的时间复杂度最坏为 \(\operatorname{O}(n\log n)\)，属于是飞慢了。

优化的方式很容易想到，就是每次修改只需要保证需要用到的节点是正确的，其他节点先不管，需要用到的时候再更改。这种方式很像前端里面的一个优化“懒加载”，即一个网页如果有很多元素，一次全部加载完可能会缓慢，所以设备显示到哪里就只加载哪里的元素，看不到的元素能不加载就不加载。同样的，这种优化方式需要打标记，同时能不下放就不下放，子节点能不修改就不修改，被称为“懒标记”。

也就是说若一个节点拥有懒标记，那么该节点的子节点们都不知道这个懒标记的存在，同时也就表明该节点的叶子节点存储的信息均不是真实信息。如果需要用到当前拥有懒标记的节点的真实信息，就需要把懒标记下放到子节点，通过懒标记更改子节点数据，然后处理子节点更改造成的数据更改即可（直接 push_up）

假设目前要求维护区间和的同时处理区间加的操作，对于每一个节点来说，我们需要维护一个懒标记 \(lazy\) ，代表“当前区间的子区间需要加一个 \(lazy\) ”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void modify(Node* nod, int L, int R, int v) { // 给 [L,R] 每个数加 v
    if (L == nod->l && R == nod->r) { // 包含了
        nod->lazy += v; // 该区间的每个子区间都需要加 v
        nod->v += (nod->r - nod->l + 1) * v; // 当前区间一共有 R-L+1 个元素（因为严格包含所以 L 和 R 就是区间的左右端点）
        // 用不上子区间的数据，不下传懒标记直接结束
    } else {
        push_down(nod);
        /*
        判断三种情况
        */
        if (nod->lc->r >= R) {
            modify(nod->lc, L, R, v);
        } else if (nod->rc->l <= L) {
            modify(nod->rc, L, R, v);
        } else {
            modify(nod->lc, L, nod->lc->r, v);
            modify(nod->rc, nod->rc->l, R, v);
        }
        push_down(nod);
        push_up(nod);
    }
}
1
2
3
4
5
6
7
8
void push_down(Node* nod) {
    if (nod->lazy == 0) return;
    if (nod->lc) nod->lc->lazy += nod->lazy;
    if (nod->rc) nod->rc->lazy += nod->lazy;
    nod->lc->v += (nod->mid - nod->l + 1) * nod->lazy;
    nod->rc->v += (nod->r - nod->mid) * nod->lazy;
    nod->lazy = 0;
}

值得注意的是，加上懒标记之后，为了保证查询时访问的节点数据正确，需要在查询时添加 push_down() 操作（上文已加）。

完整实现

区间加修改&求区间和

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>

using namespace std;

#define N 1000150

struct Node {
    int u;
    int v;
    Node *lc, *rc;
    int l, r, mid;
    int lazy;  // 懒标记
    void init(int L, int R) {
        l = L;
        r = R;
        mid = l + r >> 1;
    }
} tr[N * 4];

int n, m;
int x, y, k;
int ori[N];
char beh;
int t1, t2, t3;
int cnt = 1;
Node* tail = tr;

void push_up(Node* nod) {
    nod->v = nod->lc->v + nod->rc->v;
}

void build(Node* nod, int L, int R) {
    nod->init(L, R);
    if (L == R) {
        nod->v = ori[L];
        nod->lc = nod->rc = tr;
        return;
    }
    nod->lc = ++tail;
    nod->rc = ++tail;
    build(nod->lc, L, nod->mid);
    build(nod->rc, nod->mid + 1, R);
    push_up(nod);
}

void push_down(Node* nod) {
    if (nod->lazy == 0) return;
    if (nod->lc) nod->lc->lazy += nod->lazy;
    if (nod->rc) nod->rc->lazy += nod->lazy;
    nod->lc->v += (nod->mid - nod->l + 1) * nod->lazy;
    nod->rc->v += (nod->r - nod->mid) * nod->lazy;
    nod->lazy = 0;
}

void modify(Node* nod, int L, int R, int v) {
    if (L == nod->l && R == nod->r) {
        nod->lazy += v;
        nod->v += (nod->r - nod->l + 1) * v;
    } else {
        push_down(nod);
        if (nod->lc->r >= R) {
            modify(nod->lc, L, R, v);
        } else if (nod->rc->l <= L) {
            modify(nod->rc, L, R, v);
        } else {
            modify(nod->lc, L, nod->lc->r, v);
            modify(nod->rc, nod->rc->l, R, v);
        }
        push_down(nod);
        push_up(nod);
    }
}

int query(Node* nod, int L, int R) {
    push_down(nod);
    if (nod->r == R && nod->l == L) {
        return nod->v;
    }

    if (nod->lc->r >= R) {
        return query(nod->lc, L, R);
    } else if (nod->rc->l <= L) {
        return query(nod->rc, L, R);
    } else {
        return query(nod->lc, L, nod->lc->r) + query(nod->rc, nod->rc->l, R);
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> ori[i];
    }
    build(++tail, 1, n);
    while (m--) {
        cin >> beh;
        if (beh == '1') {
            cin >> t1 >> t2 >> t3;
            modify(tr + 1, t1, t2, t3);
        } else {
            cin >> t1 >> t2;
            cout << query(tr + 1, t1, t2) << endl;
        }
    }

    return 0;
}

区间加乘同时存在

上文介绍了加法的懒标记，如果是单独乘法的懒标记也很好实现。但是如果需要同时处理加法、乘法两个区间操作该怎么办捏？

只需要使用一下分配律即可。

\((nod_cnod_v + nod_a) \cdot d=d \cdot nod_cnod_v+d \cdot nod_a\)

\(nod_c\) 即乘法懒标记， \(nod_a\) 即加法懒标记，\(d\) 是需要乘的数（操作数）

许可协议

本文采用 GNU 自由文档许可证 许可协议，转载请注明出处。

分享文章