线段树

发表于 更新于 分类于 阅读次数： Valine：

本文转自线段树可以解决什么问题

线段树概述

线段树是什么？

线段树是一种高级数据结构，也是一种树结构，准确的说是二叉树。它能够高效的处理区间修改查询等问题。因此学习线段树，我们就是在学习一种全新的高级数据结构，学习它如何组织数据，然后高效的进行数据查询，修改等操作。

线段树树的基本操作有哪些？

  • 线段树的构建
  • 线段树的修改
  • 线段树的查询
    这些基本操作都会在后面部分讲到。

线段树的使用场景？

  • 用于维护区间信息（要求满足结合律）
  • 实现 [公式] 的区间修改
  • 持多种操作（加、乘），更具通用性

线段树问题举例

我们有时会遇到这样的问题: 给你一些数，组成一个序列，如[1 4 2 3],有两种操做: 操作一:给序列的第i个数加上X (X可以为负数) 操作二:询问序列中最大的数是什么? 格式query(start, end)，表示区间[start, end]内，最大值是多少？

思路解析
我们很容易得到一个朴素的算法: 将这些数存入一个数组, 由于要询问最大值, 我们只需要遍历这个区间[start, end]即可，找出最大值。 对于改变一个数, 我们就在这个数上加上X，比如A[i] = A[i] + X。 这个算法的缺点是什么呢？Query询问最大值复杂度O(N), 修改复杂度为O(1)，在有Q个query的情况下这样总的复杂度为O(QN), 那么对于查询来说这样的复杂度是不可以接受的，太高了！然后我们开始优化，如果你没有学过线段树，那么对于这个问题的优化是很难做的，甚至毫无头绪，基本上无从无从入手。

如果你学习了线段树，这个问题很容易解决，线段树就是一把区间问题解决的利刃，很多没有头绪的区间查询，修改问题都可以使用线段树解决。 那么这道题线段树应该怎么做？希望大家带着疑问阅读线段树的入门教程。

线段树的结构

首先线段树是一棵二叉树, 平常我们所指的线段树都是指一维线段树。 故名思义, 线段树能解决的是线段上的问题, 这个线段也可指区间. 我们先来看线段树的逻辑结构。

一颗线段树的构造就是根据区间的性质的来构造的, 如下是一棵区间[0, 3]的线段树，每个[start, end]都是一个二叉树中的节点。

1
2
3
4
5
         [0,3]
        /     \
   [0,1]       [2,3]
   /   \       /   \
[0,0] [1,1] [2,2] [3,3]

区间划分大概就是上述的区间划分。可以看出每次都将区间的长度一分为二,数列长度为n,所以线段树的高度是log(n),这是很多高效操作的基础。 上述的区间存储的只是区间的左右边界。我们可以将区间的最大值加入进来,也就是树中的Node需要存储left，right左右子节点外，还需要存储start, end, val区间的范围和区间内表示的值。

1
2
3
4
5
6
7
8
            [0,3]
           (val=4)
         /         \
     [0,1]         [2,3]
    (val=4)       (val=3)
    /    \         /    \
 [0,0]  [1,1]   [2,2]  [3,3]
(val=1)(val=4) (val=2)(val=3)

区间的第三维就是区间的最大值。 加这一维的时候只需要在建完了左右区间之后，根据左右区间的最大值来更新当前区间的最大值即可，即当前子树的最大值是左子树的最大和右子树的最大值里面选出来的最大值。

因为每次将区间的长度一分为二,所有创造的节点个数，即底层有n个节点，那么倒数第二次约n/2个节点，倒数第三次约n/4个节点，依次类推：

1
2
3
    n + 1/2 * n + 1/4 * n + 1/8 * n + ...
=   (1 + 1/2 + 1/4 + 1/8 + ...) * n
=   2n

所以构造线段树的时间复杂度和空间复杂度都为O(n)

二叉树的节点区间定义，[start, end]代表节点的区间范围，max 是节点在[start, end]区间上的最大值 left , right 是当前节点区间划分之后的左右节点区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 节点区间定义
// [start, end] 代表节点的区间范围
// max 是节点在(start,end)区间上的最大值
// left , right 是当前节点区间划分之后的左右节点区间
public class SegmentTreeNode {
    public int start, end, max;
    public SegmentTreeNode left, right;
    public SegmentTreeNode(int start, int end, int max) {
        this.start = start;
        this.end = end;
        this.max = max
        this.left = this.right = null;
    }
}

线段树区间最大值维护

给定一个区间，我们要维护线段树中存在的区间中最大的值。这将有利于我们高效的查询任何区间的最大值。给出A数组，基于A数组构建一棵维护最大值的线段树，我们可以在O(logN)的复杂度内查询任意区间的最大值：

比如原数组 A = [1, 4, 2, 3]

1
2
3
4
5
6
7
8
            [0,3]
           (val=4)
         /         \
     [0,1]         [2,3]
    (val=4)       (val=3)
    /    \         /    \
 [0,0]  [1,1]   [2,2]  [3,3]
(val=1)(val=4) (val=2)(val=3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 构造的代码及注释
public SegmentTreeNode build(int[] A) {
    // write your code here
    return buildhelper(0, A.length - 1, A);
}
public SegmentTreeNode buildhelper(int left, int right, int[] A){
    if(left > right){
        return null;
    }
    SegmentTreeNode root = new SegmentTreeNode(left, right, A[left]); // 根据节点区间的左边界的序列值为节点赋初值
    if(left == right){
        return root; // 如果左边界和右边界相等,节点左边界的序列值就是线段树节点的接节点值
    }
    int mid = (left + right) / 2; // 划分当前区间的左右区间
    root.left = buildhelper(left, mid, A);
    root.right = buildhelper(mid + 1, right, A);
    root.max = Math.max(root.left.max, root.right.max); // 根据节点区间的左右区间的节点值得到当前节点的节点值
    return root;
}

举一反三： 如果需要区间的最小值: root.min = Math.min(root.left.min, root.right.min); 如果需要区间的和: root.sum = root.left.sum + root.right.sum;

线段树的区间查询

1. 如何更好的查询Query

构造线段树的目的就是为了更快的查询。

给定一个区间，要求区间中最大的值。线段树的区间查询操作就是将当前区间分解为较小的子区间,然后由子区间的最大值就可以快速得到需要查询区间的最大值。

1
2
3
4
5
6
7
8
            [0,3]
           (val=4)
         /         \
     [0,1]         [2,3]
    (val=4)       (val=3)
    /    \         /    \
 [0,0]  [1,1]   [2,2]  [3,3]
(val=1)(val=4) (val=2)(val=3)
1
query(1,3) = max(query(1,1),query(2,3)) = max(4,3) = 4

上述例子将[1, 3]区间分为了[1, 1]和[2, 3]两个区间,因为[1, 1]和[2, 3]存在于线段树上，所以区间的最大值已经记录好了,所以直接拿来用就可以了。所以拆分区间的目的是划分成为线段树上已经存在的小线段。

2. 如何拆分区间变成线段树上有的小区间：

在线段树的层数上考虑查询 考虑长度为8的序列构造成的线段树区间[1, 8], 现在我们查询区间[1, 7]

第一层会查询试图查询[1, 7], 发现区间不存在，然后根据mid位置拆分[1, 4]和[5, 7] 第二层会查询[1, 4],[5, 7], 发现[1, 4]已经存在，返回即可，[5, 7]仍旧需要继续拆分 第三层会查询[5, 6],[7, 7], 发现[5, 6]已经存在，返回即可，[7, 7]仍旧需要继续拆分 第四层会查询[7, 7]

任意长度的线段，最多被拆分成logn条线段树上存在的线段，所以查询的时间复杂度为O(log(n)) 记住就好：）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 区间查询的代码及注释
public int query(TreeNode root, int start, int end) {
    if (start <= root.start && root.end <= end) {
        // 如果查询区间在当前节点的区间之内,直接输出结果
        return root.max;
    }
    int mid = (root.start + root.end) / 2; // 将当前节点区间分割为左右2个区间的分割线
    int ans = Integer.MIN_VALUE; // 给结果赋初值
    if (mid >= start) {   // 如果查询区间和左边节点区间有交集,则寻找查询区间在左边区间上的最大值
        ans = Math.max(ans, query(root.left, start, end));
    }
    if (mid + 1 <= end) { // 如果查询区间和右边节点区间有交集,则寻找查询区间在右边区间上的最大值
        ans = Math.max(ans, query(root.right, start, end));
    }
    return ans; // 返回查询结果
}

线段树的单点更新

1. 更新序列中的一个点

1
2
3
4
5
6
7
8
            [0,3]
           (val=4)
         /         \
     [0,1]         [2,3]
    (val=4)       (val=3)
    /    \         /    \
 [0,0]  [1,1]   [2,2]  [3,3]
(val=1)(val=4) (val=2)(val=3)

更新序列中的一个节点，如何把这种变化体现到线段树中去，例如，将序列中的第4个点A[3]更新为5, 要变动3个区间中的值,分别为[3,3],[2,3],[0,3]

提问：为什么需要更新这三个区间？：因为只有这三个在线段树中的区间，覆盖了3这个点。

1
2
3
4
5
6
7
           [0,3]
          (val=5)
        /         \
    [0,1]         [2,3]
   (val=4)       (val=5)
   /    \         /    \
[0,0]  [1,1]   [2,2]  [3,3]
1
(val=1)(val=4) (val=2)(val=5)

可以这样想,改动一个节点,与这个节点对应的叶子节点需要变动。因为叶子节点的值的改变可能影响到父亲节点，然后叶子节点的父亲节点也可能需要变动。

如果我们继续把A[2]从2变成4，线段树又该如何更新呢？ 线段树变化后的状态为：

1
2
3
4
5
6
7
           [0,3]
          (val=5)
        /         \
    [0,1]         [2,3]
   (val=4)       (val=5)
   /    \         /    \
[0,0]  [1,1]   [2,2]  [3,3]
1
(val=1)(val=4) (val=4)(val=5)

如果我们继续把A[1]从4变成3，线段树又该如何更新呢？ 线段树变化后的状态为：

1
2
3
4
5
6
7
8

           [0,3]
          (val=5)
        /         \
    [0,1]         [2,3]
   (val=3)       (val=5)
   /    \         /    \
[0,0]  [1,1]   [2,2]  [3,3]
1
(val=1)(val=3) (val=4)(val=5)

更新所以需要从叶子节点一路走到根节点, 去更新线段树上的值。因为线段树的高度为log(n),所以更新序列中一个节点的复杂度为log(n)。 因为每次从父节点走到子节点的时候，区间都是一分为二，那么我们要修改index的时候，我们从root出发，判断index会落在左边还是右边，然后继续递归，这样就可以很容易从根节点走到叶子节点，然后更新叶子节点的值，递归返回前不断更新每个节点的最大值即可。具体代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 单点更新的代码及注释
public void modify(SegmentTreeNode root, int index, int value) {
    // write your code here
    if(root.start == root.end && root.start == index) { // 找到被改动的叶子节点
        root.max = value; // 改变value值
        return ;
    }
    int mid = (root.start + root.end) / 2; // 将当前节点区间分割为2个区间的分割线
    if(index <= mid){ // 如果index在当前节点的左边
        modify(root.left, index, value); // 递归操作
        root.max = Math.max(root.right.max, root.left.max); // 可能对当前节点的影响
    }
    else {            // 如果index在当前节点的右边
        modify(root.right, index, value); // 递归操作
        root.max = Math.max(root.left.max, root.right.max); // 可能对当前节点的影响
    }
    return ;
}

如果需要区间的最小值或者区间的和，构造的时候同理。

线段树模板-线段树动态开点

来自 线段树动态开点+线段树图解

动态开点的线段树节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
     * 线段树的结点
     */
    static class Node {
        //左范围
        private int left;
        //右范围
        private int right;
        //区间和
        private int sum;
        //懒标记 0表示不需要操作
        private int lazy;
        //左子树和右子树
        Node leftChild, rightChild;

        public Node(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }


动态开点的更新

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
/**
     * 区间更新
     *
     * @param root  树的根
     * @param left  左边界
     * @param right 有边界
     * @param value 更新值
     */
    public void update(Node root, int left, int right, int value) {
        //不在范围内 直接返回
        if (root.left > right || root.right < left) {
            return;
        }
        //修改的区间包含当前结点
        if (root.left >= left && root.right <= right) {
            root.lazy = value;
            root.value += (root.right - root.left + 1) * value;
        } else {
            //动态开点
            lazyCreate(root);
            //下传lazy
            pushDown(root);
            //更新左子树
            update(root.leftChild, left, right, value);
            //更新右子树
            update(root.rightChild, left, right, value);
            //上传结果
            pushUp(root);
        }
    }

    /**
     * 创建左右子树
     *
     * @param root
     */
    public void lazyCreate(Node root) {
        if (root.leftChild == null) {
            root.leftChild = new Node(root.left, root.left + (root.right - root.left) / 2);
        }
        if (root.rightChild == null) {
            root.rightChild = new Node(root.left + (root.right - root.left) / 2 + 1, root.right);
        }
    }

    /**
     * 下传lazy
     *
     * @param root
     */
    public void pushDown(Node root) {
        if (root.lazy == 0) {
            return;
        }
        int value = root.lazy;
        root.leftChild.lazy = value;
        root.rightChild.lazy = value;
        root.leftChild.value += (root.leftChild.right - root.leftChild.left + 1) * value;
        root.rightChild.value += (root.rightChild.right - root.rightChild.left + 1) * value;
        root.lazy = 0;
    }

    /**
     * 上传结果
     *
     * @param root
     */
    public void pushUp(Node root) {
        root.value = root.leftChild.value + root.rightChild.value;
    }

动态开点的查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18



public int query(Node root, int left, int right) {
    if (left <= root.left && root.right <= right) {
        return root.value;
    }
    lazyCreate(root);
    pushDown(root);
    int mid = root.left + (root.right - root.left) / 2;
    if (right <= mid) {
        return query(root.leftChild, left, right);
    } else if (left > mid) {
        return query(root.rightChild, left, right);
    } else {
        return query(root.leftChild, left, mid) + query(root.rightChild, mid + 1, right);
    }
}

实战面试题

实战面试题1 - 731. 我的日程安排表 II

leetcode原题：https://leetcode.cn/problems/my-calendar-ii/

题目大意：

1
2
3
4
5
6
7
8
9
10
实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，  start <= x < end。

当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生三重预订。

每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

解题思路：
标准的区间求最大值，直接套用模板

题解：

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
112
113
114
115
116
117
118
119
120
121
122
123
class MyCalendarTwo {
    /**
     * 线段树的结点
     */
    static class Node {
        //左范围
        private int leftX;
        //右范围
        private int rightX;
        //最大值
        private int max;
        //懒标记 0表示不需要操作
        private int lazy;
        //左子树和右子树
        Node leftChild, rightChild;

        public Node(int leftX, int rightX) {
            this.leftX = leftX;
            this.rightX = rightX;
        }
    }

    private Node root;

    /**
     * 区间更新
     *
     * @param root  树的根
     * @param left  左边界
     * @param right 有边界
     * @param value 更新值,删除则相当于置为0
     */
    public void update(Node root, int left, int right, int value) {
        //不在范围内 直接返回
        if (root.leftX > right || root.rightX < left) {
            return;
        }
        //修改的区间包含当前结点
        if (root.leftX >= left && root.rightX <= right) {
            root.max += value;
            root.lazy += value;
        } else {
            //动态开点
            lazyCreate(root);
            //下传lazy
            pushDown(root);
            //更新左子树
            update(root.leftChild, left, right, value);
            //更新右子树
            update(root.rightChild, left, right, value);
            //上传结果
            pushUp(root);
        }
    }

    public int query(Node root, int left, int right) {
        if (left <= root.leftX && root.rightX <= right) {
            return root.max;
        }
        lazyCreate(root);
        pushDown(root);
        int mid = root.leftX + (root.rightX - root.leftX) / 2;
        if (right <= mid) {
            return query(root.leftChild, left, right);
        } else if (left > mid) {
            return query(root.rightChild, left, right);
        } else {
            return Math.max(query(root.leftChild, left, mid), query(root.rightChild, mid + 1, right));
        }
    }

    /**
     * 创建左右子树
     *
     * @param root
     */
    public void lazyCreate(Node root) {
        if (root.leftChild == null) {
            root.leftChild = new Node(root.leftX, root.leftX + (root.rightX - root.leftX) / 2);
        }
        if (root.rightChild == null) {
            root.rightChild = new Node(root.leftX + (root.rightX - root.leftX) / 2 + 1, root.rightX);
        }
    }

    /**
     * 下传lazy
     *
     * @param root
     */
    public void pushDown(Node root) {
        if (root.lazy > 0) {
            int value = root.lazy;
            root.leftChild.lazy += value;
            root.rightChild.lazy += value;
            root.leftChild.max += value;
            root.rightChild.max += value;
            root.lazy = 0;
        }
    }

    /**
     * 上传结果
     *
     * @param root
     */
    public void pushUp(Node root) {
        root.max = Math.max(root.leftChild.max, root.rightChild.max);
    }

    public MyCalendarTwo() {
        root = new Node(0, (int) 1e9);
    }

    public boolean book(int start, int end) {
        int query = query(root, start, end - 1);
        if (query >= 2) {
            return false;
        }
        update(root, start, end - 1, 1);
        return true;
    }
}