环己三烯的冬眠舱

天天网抑云，偶尔读点书。

0%

线段树（下）

发表于 更新于

概述

上一篇文章已经介绍了线段树的基本概念和实现方式。本文将介绍线段树的进阶技巧：懒标记（Lazy Tag） 。在不使用懒标记时，每次进行区间修改其实是进行了若干次单点修改，需要消耗大量的时间。为此，我们引入了懒标记，这样我们可以仅在需要时对节点的值进行更新，否则就给整个区间打上懒标记，表示这个区间所有的值都要加上这么多，只是我还懒得去改掉。如此操作，便可以在区间修改时节省大量时间。

代码实现

准备工作

同不带懒标记的线段树一样，我们需要预留 3 ~ 4 倍于原数组的储存空间。而不同点在于，由于我们需要存储每个节点的值和它对应的懒标记，所以我们不能简单地用一个int表示，而应该使用结构体。

1
2
3
4
5
struct node {
    long long val = 0;
    int lazytag = 0;
};
vector<node> tree(n*4);

构建线段树（不涉及懒标记）

1
2
3
4
5
6
7
8
9
10
11
12
void buildtree(int root, int start, int end) {
    if (start == end) {
        tree[root].val = nums[start];
        return;
    }
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start + end) / 2;
    buildtree(leftroot, start, mid);
    buildtree(rightroot, mid + 1, end);
    tree[root].val = tree[leftroot].val + tree[rightroot].val;
}

查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
long long query(int root, int start, int end, int l, int r) {
    if (l > end || r < start) return 0;
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start + end) / 2;
    if (l <= start && r >= end) return tree[root].val;
    if (tree[root].lazytag != 0) {
        //将lazytag向下推进
        tree[leftroot].lazytag += tree[root].lazytag;
        tree[leftroot].val += (long long)(mid - start + 1) * tree[root].lazytag;
        tree[rightroot].lazytag += tree[root].lazytag;
        tree[rightroot].val += (long long)(end-mid) * tree[root].lazytag;
        tree[root].lazytag = 0;
    }
    long long res = query(leftroot, start, mid, l, r) + query(rightroot, mid + 1, end, l, r);
    tree[root].val = tree[leftroot].val + tree[rightroot].val;
    return res;
}

修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void update(int root, int start, int end, int l, int r, int k) {
    if (l > end || r < start) return;
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start + end) / 2;
    if (l <= start && r >= end) {
        //如果需要修改的区间完全覆盖当前处理的区间，则整体打上lazytag留待以后处理。
        tree[root].val += (end - start + 1) * k;
        tree[root].lazytag += k;
        return;
    }
    if (tree[root].lazytag != 0) {
        //将lazytag向下推进。
        tree[leftroot].lazytag += tree[root].lazytag;
        tree[leftroot].val += (mid - start + 1) * tree[root].lazytag;
        tree[rightroot].lazytag += tree[root].lazytag;
        tree[rightroot].val += (end-mid) * tree[root].lazytag;
        tree[root].lazytag = 0;
    }
    update(leftroot, start, mid, l, r, k);
    update(rightroot, mid + 1, end, l, r, k);
    tree[root].val = tree[leftroot].val + tree[rightroot].val;
}

题解

题目请见《线段树（上）》的例题。

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
class Solution {
private:
    vector<int> nums;
    struct node {
        long long val = 0;
        int lazytag = 0;
    };
    vector<node> tree;
    void buildtree(int root, int start, int end) {
        if (start == end) {
            tree[root].val = nums[start];
            return;
        }
        int leftroot = root * 2;
        int rightroot = root * 2 + 1;
        int mid = (start + end) / 2;
        buildtree(leftroot, start, mid);
        buildtree(rightroot, mid + 1, end);
        tree[root].val = tree[leftroot].val + tree[rightroot].val;
    }
    void update(int root, int start, int end, int l, int r, int k) {
        if (l > end || r < start) return;
        int leftroot = root * 2;
        int rightroot = root * 2 + 1;
        int mid = (start + end) / 2;
        if (l <= start && r >= end) {
            //如果需要修改的区间完全覆盖当前处理的区间，则整体打上lazytag留待以后处理。
            tree[root].val += (end - start + 1) * k;
            tree[root].lazytag += k;
            return;
        }
        if (tree[root].lazytag != 0) {
            //将lazytag向下推进。
            tree[leftroot].lazytag += tree[root].lazytag;
            tree[leftroot].val += (mid - start + 1) * tree[root].lazytag;
            tree[rightroot].lazytag += tree[root].lazytag;
            tree[rightroot].val += (end-mid) * tree[root].lazytag;
            tree[root].lazytag = 0;
        }
        update(leftroot, start, mid, l, r, k);
        update(rightroot, mid + 1, end, l, r, k);
        tree[root].val = tree[leftroot].val + tree[rightroot].val;
    }
    long long query(int root, int start, int end, int l, int r) {
        if (l > end || r < start) return 0;
        int leftroot = root * 2;
        int rightroot = root * 2 + 1;
        int mid = (start + end) / 2;
        if (l <= start && r >= end) return tree[root].val;
        if (tree[root].lazytag != 0) {
            tree[leftroot].lazytag += tree[root].lazytag;
            tree[leftroot].val += (long long)(mid - start + 1) * tree[root].lazytag;
            tree[rightroot].lazytag += tree[root].lazytag;
            tree[rightroot].val += (long long)(end-mid) * tree[root].lazytag;
            tree[root].lazytag = 0;
        }
        long long res = query(leftroot, start, mid, l, r) + query(rightroot, mid + 1, end, l, r);
        tree[root].val = tree[leftroot].val + tree[rightroot].val;
        return res;
    }

public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        nums.resize(n,0);
        tree.resize(n * 4);
        buildtree(1, 0, n-1);
        for (int i = 0; i < bookings.size(); i++) {
            update(1, 1, n, bookings[i][0], bookings[i][1], bookings[i][2]);
        }
        vector<int> res;
        for (int i = 1; i <= n; i++) {
            res.push_back(query(1, 1, n, i, i));
        }
        return res;
    }
};

可以看到，代码真的非常非常长，而且效率也远不如直接用差分数组来得快。所以即便线段树可以高效地完成很多任务，我们也只在迫不得已时才写线段树。

有的没的

耶 复活了

前一阵子GitHub账号被封了，导致Blog直接上不来了。发了邮件申诉，刚好赶上周末美帝不上班，今晚刚解封，火速更新。不过其实GitHub被封并不影响我更新，前一阵子是忙着打CSGO去了…昨天掉大分，进入贤者模式，刚好今天解封了就更了一手。希望GitHub以后不要抽风了。

关于国际化模块

犹豫再三还是把定性研究方法导论退掉了，屁事太多了。要是周萍能把经典文献阅读搞成国际化，她就是我的永远的女神。如果不行的话就试试看选计院的国际化模块吧。申上了，爱了爱了

没事听点歌（陈奕迅 - 红玫瑰）