【数据结构】线段树

算法提高课笔记

原理

时间复杂度：O(logn)

线段树是一棵二叉树，把一段区间分成多个部分

类似堆的方式，用一维数组存整棵树

对于编号x的结点：

• 父结点 $\lfloor x\rfloor$，表示为 x >> 1
• 左子树 $2x$，表示为 x << 1
• 右子树 $2x+1$，表示为 x << 1 | 1

对于长度为n的区间，最坏估计有 $4n-1$ 个结点，因此 开数组时空间一般开 $4n$

pushup

由子结点计算父结点的信息

模板：

// u表示当前树中结点编号 lr表示树中结点左右子结点
void pushup(Node &u, Node &l, Node &r)
{
    /* 此处用[l]和[r]的值更新[u] */
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
1
2
3
4
5
6
7
8
9
10

build

将一段区间初始化为线段树

1. 首先记录下当前区间的左右端点，如果左端点和右端点相等就直接返回
2. 如果不相等，取中间值 mid，然后分别递归左右两段

模板：

// u表示当前树中结点编号 lr表示区间左右端点
void build(int u, int l, int r)
{
    if (l == r) // 左右端点相同表示到达叶子结点
    {
        tr[u] = {    }; // 创建该结点
    }
    else
    {
        tr[u].l = l, tr[u].r = r;
        int mid = l + r >> 1; // 取中间值
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); // 分别构造左右两棵子树
        pushup(u); // 利用pushup更新该点
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

modify

修改单点或区间（需要用到push_down操作）

修改单点模板：

// u为当前树中结点编号 要把x位置的值更新为v
void modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x) // 到达叶子结点 直接更新
    {
        tr[u] = {     };
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1; // 取中间值
        if (x <= mid) modify(u << 1, x, v); // 要更新的位置在左半部分
        else modify(u << 1 | 1, x, v); // 要更新的位置在右半部分
        pushup(u); // 更新此位置结点
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

修改区间模板：

void modify(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r) // 当前树中结点在所求区间之内
    {
        tr[u].sum += (i64)(tr[u].r - tr[u].l + 1) * d; // 更新区间信息
        tr[u].add += d; // 打上懒标记
    }
    else // 当前树中结点不在所求区间之内
    {
        pushdown(u); // 将懒标记向下传递
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, d); // 与左半段有重合部分就更新左半段
        if (r > mid) modify(u << 1 | 1, l, r, d); // 与左半段有重合部分就更新左半段
        pushup(u); // 由于modify修改了区间结点的信息，所以被修改的结点的祖先结点都需要重算一遍
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

query

查询区间信息

假设我们要查询某区间的最大值

定义 [l, r] 为我们要查询的区间，[Tl, Tr] 为树中结点（当前我们正在维护的区间），这两个区间会有如下两种关系：

• $[Tl,Tr]\subset [l,r]$，树中结点完全包含在要查询的区间内部
  这种情况直接返回当前区间最大值即可
• $[l,r]\bigcap [Tl,Tr]\ne \varnothing$，二者有交集
  和左边有交集就递归到左边做一遍，和右边有交集就递归到右边做一遍
  即l > mid只递归右边，r <= mid只递归左边，否则左右都递归

模板：

Node query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u]; // 当前区间在被查询区间之内 直接返回
    else
    {
        int mid = tr[u].l + tr[u].r >> 1; // 取中间值
        if (r <= mid) return query(u << 1, l, r); // 被查询区间在当前区间左半部分
        else if (l > mid) return query(u << 1 | 1, l, r); // 被查询区间在当前区间右半部分
        else // 被查询区间横跨当前区间的左右两部分
        {
            auto left = query(u << 1, l, r); // 计算出左半部分值
            auto right = query(u << 1 | 1, l, r); // 计算出右半部分值
            Node res;
            pushup(res, left, right); // 更新结果
            return res;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

pushdown（懒标记 / 延迟标记）

将父结点的修改更新到子结点

单点修改可以只用pushup，涉及到区间修改就需要使用pushdown

懒标记 ：在当前树中结点上打上懒标记，就表示对以当前树中结点为根结点的每一个子树都进行操作（根结点自己不用操作）

那么懒标记怎么进行传递呢？

焗个栗子：比如我们在蓝色的这一段区间上打上懒标记

每当我们需要遍历蓝色区间结点下方的子结点时，我们就把懒标记传递给下一层结点，同时把根结点的懒标记删除，就像这样：

当然，除了传递标记，我们还需要对线段树中记录的值进行更新，比如说这个线段树记录的是区间和，打上懒标记表示这一段区间每一个数都要加上a，那么我们在传递懒标记的同时，还需要让下方结点的区间和加上(r - l + 1) * a，其中(l - r + 1)表示下方被更新结点的区间长度

以此类推，每当我们需要遍历下方结点时，就把懒标记向下传，并更新下方结点的值

以上就是pushdown操作的基本内容

模板：

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add) // 当前结点有懒标记 向下传递
    {
        left.add += root.add, left.sum += (i64)(left.r - left.l + 1) * root.add;
        right.add += root.add, right.sum += (i64)(right.r - right.l + 1) * root.add;
        root.add = 0;
    }
}
1
2
3
4
5
6
7
8
9
10

例题：一个简单的整数问题2

原题链接

给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：

C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r，表示询问数列中第 l∼r 个数的和。
对于每个询问，输出一个整数表示答案。

输入格式

第一行两个整数 N,M。

第二行 N 个整数 A[i]。

接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。

输出格式

对于每个询问，输出一个整数表示答案。

每个答案占一行。

数据范围

$1\le N,M\le 105,$
$|d|\le 10000,$
$|A[i]|\le 109$

输入样例

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
1
2
3
4
5
6
7

输出样例

4
55
9
15
1
2
3
4

code

#include 

using namespace std;

using i64 = long long;
typedef long long LL;

const int N = 100010;

int n, m;
int w[N];
struct Node
{
    int l, r;
    i64 sum, add; // 区间和和懒标记
}tr[N * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add) // 当前结点有懒标记 向下传递
    {
        left.add += root.add, left.sum += (i64)(left.r - left.l + 1) * root.add;
        right.add += root.add, right.sum += (i64)(right.r - right.l + 1) * root.add;
        root.add = 0;
    }
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r], 0};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r) // 当前树中结点在所求区间之内
    {
        tr[u].sum += (i64)(tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d; // 打上懒标记
    }
    else // 当前树中结点不在所求区间之内
    {
        pushdown(u); // 将懒标记向下传递
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, d); // 与左半段有重合部分就更新左半段
        if (r > mid) modify(u << 1 | 1, l, r, d); // 与左半段有重合部分就更新左半段
        pushup(u); // 由于modify修改了区间结点的信息，所以被修改的结点的祖先结点都需要重算一遍
    }
}

i64 query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(u); // 为了让查询到的最小结点都已计算过祖先结点的懒标记
    int mid = tr[u].l + tr[u].r >> 1;
    i64 sum = 0;
    if (l <= mid) sum = query(u << 1, l, r);
    if (r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    build(1, 1, n);

    char op;
    int l, r, d;
    while (m -- )
    {
        cin >> op >> l >> r;
        if (op == 'C')
        {
            cin >> d;
            modify(1, l, r, d);
        }
        else cout << query(1, l, r) << '\n';
    }
}
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

扫描线法

放一道例题

亚特兰蒂斯

原题链接

有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。

其中一些甚至包括岛屿部分地图。

但不幸的是，这些地图描述了亚特兰蒂斯的不同区域。

您的朋友 Bill 必须知道地图的总面积。

你自告奋勇写了一个计算这个总面积的程序。

输入格式

输入包含多组测试用例。

对于每组测试用例，第一行包含整数 n，表示总的地图数量。

接下来 n 行，描绘了每张地图，每行包含四个数字 x1,y1,x2,y2（不一定是整数），(x1,y1) 和 (x2,y2) 分别是地图的左上角位置和右下角位置。

注意，坐标轴 x 轴从上向下延伸，y 轴从左向右延伸。

当输入用例 n=0 时，表示输入终止，该用例无需处理。

输出格式

每组测试用例输出两行。

第一行输出 Test case #k，其中 k 是测试用例的编号，从 1 开始。

第二行输出 Total explored area: a，其中 a 是总地图面积（即此测试用例中所有矩形的面积并，注意如果一片区域被多个地图包含，则在计算总面积时只计算一次），精确到小数点后两位数。

在每个测试用例后输出一个空行。

数据范围

$1\le n\le 10000,$
$0\le x1<x2\le 100000,$
$0\le y1<y2\le 100000$

注意，本题 n 的范围上限加强至 10000。

输入样例

2
10 10 20 20
15 15 25 25.5
0
1
2
3
4

输出样例

Test case #1
Total explored area: 180.00 
1
2

code

#include 

using namespace std;

const int N = 100010;

int n;
struct Segment
{
    double x, y1, y2;
    int k;
    bool operator< (const Segment &t) const
    {
        return x < t.x;
    }
}seg[N * 2];
struct Node
{
    int l, r;
    int cnt;
    double len;
}tr[N * 8]; // 线段树

vector<double> ys; // 存储纵坐标

int find(double y)
{
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}

void pushup(int u)
{
    if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l]; // 这一段被完全覆盖 所以直接算长度
    else if (tr[u].l != tr[u].r) // 没有被完全覆盖 分成左右两段分别来看
    {
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    }
    else tr[u].len = 0; // 叶子结点
}

void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if (l != r)
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        // cnt和len都是0所以不需要pushdown
    }
}

void modify(int u, int l, int r, int k)
{
    if (tr[u].l >= l && tr[u].r <= r) // 完全覆盖
    {
        tr[u].cnt += k;
        pushup(u); // 更新该节点的len
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        pushup(u);
    }
}

int main()
{
    int T = 1;
    while (scanf("%d", &n), n)
    {
        ys.clear();
        for (int i = 0, j = 0; i < n; i ++ )
        {
            double x1, x2, y1, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            // 把所有竖着的线段存进segment
            seg[j ++ ] = {x1, y1, y2, 1};
            seg[j ++ ] = {x2, y1, y2, -1};
            ys.push_back(y1), ys.push_back(y2); // 把所有纵坐标存进ys
        }

        // 纵坐标去重
        sort(ys.begin(), ys.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());

        build(1, 0, ys.size() - 2); // 纵坐标点的数量到ys-1 线段数量就是ys-2

        sort(seg, seg + n * 2);

        double res = 0;
        for (int i = 0; i < n * 2; i ++ )
        {
            if (i) res += tr[1].len * (seg[i].x - seg[i - 1].x);
            modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k);
        }

        cout << "Test case #" << T << '\n';
        T ++ ;
        printf("Total explored area: %.2lf\n\n", res);
    }
}
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