线段树

发表于 更新于 分类于 ， 阅读次数： 本文字数： 4.3k 阅读时长 ≈ 4 分钟
引言：数据结构——线段树

线段树

线段树

也叫区间树(Segment Tree)

有些问题我们关注的是一个区间

例如区间染色问题

区间染色问题：有一个数组区间[0~N]区间，每次操作，我们将其一段染为一种颜色（颜色可以覆盖）

  1. 经过m次操作后，我们能看到多少种颜色？
  2. m次操作后，我们能在[i , j]区间内看到多少种颜色？

审题我们可以知道主要有两种操作：

  1. 染色操作
  2. 查询操作

自然而然我们会选择遍历数组，但是这样的话，染色操作和查询操作都需要O(N)的复杂度

再比如计算机经常会有的区间查询操作，我们可能也要统计一个区间的最大值，最小值，区间和等等信息。

再比如，你想统计一下2020年你们项目中消费最高的用户，消费最少的用户，学习时间最长的用户。

如果我们使用线段树，我们进行这种的操作都可以实现在O(log N)之内

那么什么是线段树？

和普通的树唯一的区别，就是每个节点存放的数据是一个区间

image-20200924202808602

线段树特点：

  • 是一棵平衡二叉树（任意节点的最大深度和最小深度的差最大为1）
  • 可以使用数组来表示（虽然叶子结点不会分布在同一层，但是我们可以把不存在的叶子结点当做空来处理）
  • 一个n个节点的线段树需要开辟4n个空间

为什么一个n个节点的线段树需要4n个空间？

对于一颗平衡二叉树来说，第一层有2^0个节点，一直到第h层，有2^h个节点。整棵树总共有着2^(h+1）-1个节点，对比最后一层和全部节点数我们会有这样的感觉，几乎最后一层的节点数就和整棵树的大小是一样的，而线段树基本就是使用最后一层来存储元素。

有了上述的观念，我们再来看这个问题。因为我们要以满二叉树的标准来存储元素，假设有n个节点，而n=2^h，我们只需要使用2n个存储空间即可。，但是如果再多一个节点，我们就需要再开辟一行空间，也就是再来一行，需要使用4n个空间

线段树代码

（无增添操作，线段树的优势在于实现更新和查询操作）

这里我们使用一个接口，来表示两个元素之间的相互操作。例如相加操作、相减操作等等一系列甚至是复杂的业务操作

1
2
3
4
5
6
7
/**
 * @Date 2020/9/24 21:19
 * 线段树业务
 */
public interface Merger<E> {
    E merge(E a, E b);
}
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
import java.util.Arrays;

/**
 * @Date 2020/9/24 20:54
 * 线段树
 */
public class SegmentTree<E> {
    private E[] data;
    private E[] tree;
    // 根据具体业务决定
    private Merger<E> merger;

    public SegmentTree(E[] arr, Merger<E> merger) {
        this.merger = merger;
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        tree = (E[]) new Object[4 * arr.length];
        buildSegmentTree(0, 0, arr.length - 1);
    }

    /**
     * 递归创建线段树
     *
     * @param treeIndex
     * @param l         左端下标
     * @param r         右端下标
     */
    private void buildSegmentTree(int treeIndex, int l, int r) {
        // 如果只有一个元素
        if (l == r) {
            tree[treeIndex] = data[l];
            return;
        }
        // 注意这里的范围，可以写为 (r+l)/2，但是r+l可能会出现整型溢出的问题
        // 所以我们这样写 l+(r-l)/2
        int mid = l + (r - l) / 2;
        buildSegmentTree(leftChild(treeIndex), l, mid);
        buildSegmentTree(rightChild(treeIndex), mid + 1, r);
        //tree[treeIndex] = tree[rightChild(treeIndex)] + tree[leftChild(treeIndex)];
        //假如我们的业务需要求分段的和，我们就可以写为+的形式
        //所以这里我们使用一个新的接口来进行两个泛型的运算
        tree[treeIndex] = merger.merge(tree[leftChild(treeIndex)], tree[rightChild(treeIndex)]);
    }

    /**
     * 返回区间[queryL, queryR]的值
     *
     * @param queryL
     * @param queryR
     * @return
     */
    public E query(int queryL, int queryR) {
        if (queryL < 0 ||
                queryL >= data.length ||
                queryR < 0 ||
                queryR >= data.length ||
                queryL > queryR) {
            throw new IllegalArgumentException("索引不正确");
        }

        return query(0, 0, data.length - 1, queryL, queryR);
    }

    /**
     * 在以treeID为根的线段树中[l...r]的范围内，搜索区间[queryL...queryR]的值
     */
    private E query(int treeIndex, int l, int r, int queryL, int queryR) {
        if (l == queryL && r == queryR) {
            return tree[treeIndex];
        }
        int mid = l + (r - l) / 2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        //要查询的部分在右子树
        if (queryL >= mid + 1) {
            return query(rightTreeIndex, mid + 1, r, queryL, queryR);
        } else if (queryR <= mid) {
            return query(leftTreeIndex, l, mid, queryL, queryR);
        } else {
            E leftResult = query(leftTreeIndex, l, mid, queryL, mid);
            E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);
            return merger.merge(leftResult, rightResult);
        }
    }

    /**
     * 将index位置的值更新为e
     *
     * @param index
     * @param e
     */
    public void set(int index, E e) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("索引不正确");
        }
        data[index] = e;
        set(0, 0, data.length - 1, index, e);
    }

    /**
     * @param treeIndex
     * @param l
     * @param r
     * @param index
     * @param e
     */
    private void set(int treeIndex, int l, int r, int index, E e) {
        if (l == r) {
            tree[treeIndex] = e;
            return;
        }
        int mid = l + (r - l) / 2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        if (index >= mid + 1) {
            set(rightTreeIndex, mid + 1, r, index, e);
        } else {
            set(leftTreeIndex,l,mid,index,e);
        }
        // 更新每一级的范围
        tree[treeIndex] = merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]);
    }

    public E get(int index) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("索引不正确");
        }
        return data[index];
    }

    /**
     * 当做满二叉树来存储，那么肯定符合完全二叉树的性质
     *
     * @return
     */
    private int leftChild(int index) {
        return 2 * index + 1;
    }

    private int rightChild(int index) {
        return 2 * index + 2;
    }

    @Override
    public String toString() {
        return "SegmentTree{" +
                "tree=" + Arrays.toString(tree) +
                '}';
    }
}