algorithm-segmenttree

20. 线段树-segmentTree

简介

什么是线段树呢？线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

线段树的每个节点都表示一个区间，而根据线段树的不同特征，线段树的节点值可以表示这个区间里的最小值，最大值或者sum值等等。

最小线段树

下面我们以最小线段树为例来说明一下线段树的特性：

如果原始数据是一个数组，我们也以数组来表示线段树。

假设生成的线段树的起点index=1，并且对线段树中的每个非叶子节点index k来说，它的左子节点index=2* k, 而它的右子节点index=2* k+1 。

上图中，标黄色的是原始数组，总共有七个元素。

上面的树形结构就是根据原始数组构建出来的线段树了。

因为是最小线段树，每个非叶子节点存储的都是子节点中的最小值。

举个例子： index=1 的元素表示的是原始数组范围0-6，并且它的值是11，表示的是原始数组0-6范围中，最小的值是11。

11的左子节点表示的范围是0-3，右字节点表示的范围是4-6。

可以看出线段树是一个平衡二叉树（不一定是完全平衡二叉树）。

线段树的叶子节点表示的就是原始数组的每一个值。

注意，这里线段树中范围的表示方式，是通过同时传入treeIndex和数组的左右边界来表示的。

线段树的构建

我们先来看一个线段树构建的动画：

从上面的动画，我们可以看出我们使用的是递归构造的方法。

首先，我们定义两个数组：一个数组存放的是原始数组的引用，一个数组存放的是新生成的线段树。

新构建的segmentTree，对于满二叉树 最后一层的节点数乘以2 大致就是整棵树的节点数。

但是线段树并不一定是满二叉树，但是一定是平衡二叉树，所以需要多冗余一层。也就是 乘以4 就足以盛放所有的节点数。

新构建的segmentTree 以index=1为起点。

我们看一下构建线段树的代码：

   /**
     * 构建segmentTree
     * @param treeIndex 当前需要添加节点的索引
     * @param arrayLeft 数组的左边界
     * @param arrayRight 数组的右边界
     */
    private void build(int treeIndex, int arrayLeft, int arrayRight) {
        if (arrayLeft == arrayRight)   //如果相等则随便选择一个赋值
            segmentTree[treeIndex] = originalArray[arrayLeft];
        else {       // 否则分别构建左侧子树和右侧子树，并根据我们需要构建的segmentTree类型来设置当前节点的值
            build(left(treeIndex) , arrayLeft , (arrayLeft + arrayRight) / 2);
            build(right(treeIndex), (arrayLeft + arrayRight) / 2 + 1, arrayRight);
            int p1 = segmentTree[left(treeIndex)], p2 = segmentTree[right(treeIndex)];
            segmentTree[treeIndex] = (p1 <= p2) ? p1 : p2;
        } }

我们是递归调用build方法， 直到传入的arrayLeft == arrayRight，也就是说直到该节点是叶子节点的时候，就直接赋值。

如果不是叶子节点，则递归构建左子树和右子树。

最后构建他们的父节点，因为这里我们构建的是最小线段树，所以取两者的最小值。

线段树的搜索

先看一个动画：

上图中，我们搜索的是2-4范围的最小值。

怎么求出来呢？

我们从index=1开始，先判断0-6是否在2-4的范围内，如果不是，则继续搜索左子树和右子树。

搜索左子树：判断0-3是否在2-4的范围内，发现部分重叠，则继续搜索左右子树。

搜索左子树：判断0-1是否在2-4的范围内，发现超出了范围，停止搜索左子树。

搜索右子树：判断2-3是否在2-4范围内，是，则直接返回该节点的值，也就是13。

同样的道理，我们可以得到右节点的返回值是15。

然后比较13和15，得到小的那个13。

用java代码实现如下：

    /**
     * 范围查询
     * @param treeIndex 当前要查找的节点index
     * @param arrayLeft 数组左边界
     * @param arrayRight 数组右边界
     * @param searchLeft 搜索左边界
     * @param searchRight 搜索右边界
     * @return
     */
    private int rangeQuery(int treeIndex, int arrayLeft, int arrayRight, int searchLeft, int searchRight) {
        if (searchLeft >  arrayRight || searchRight <  arrayLeft) return -1; // 搜索超出数组范围
        if (arrayLeft >= searchLeft && arrayRight <= searchRight) return segmentTree[treeIndex];  // 搜索的是整个数组范围，则直接返回根元素

        // 否则左右搜索
        int p1 = rangeQuery(left(treeIndex) , arrayLeft, (arrayLeft+arrayRight) / 2, searchLeft, searchRight);
        int p2 = rangeQuery(right(treeIndex), (arrayLeft+arrayRight) / 2 + 1, arrayRight, searchLeft, searchRight);

        if (p1 == -1) return p2;   // 如果超出范围，则返回另外一个
        if (p2 == -1) return p1;
        return (p1 <= p2) ? p1 : p2; }  //返回最小的那个

线段树的更新

那么线段树如何更新呢？

我们同样可以使用递归的更新方法，先分别更新左右两个子树，然后再更新他们的父节点。

递归的结束条件是什么呢？

当传入的arrayLeft=arrayRight并且等于要更新的arryIndex的时候，就需要更新叶子节点的segmentTree的值了。

java实现代码如下所示：

   /**
     * 更新数组中的某个节点
     * @param treeIndex 树的index
     * @param arrayLeft 数组左边界
     * @param arrayRight 数组右边界
     * @param arrayIndex 要更新的数组index
     * @param newValue 要更新的值
     * @return
     */
    private int updatePoint(int treeIndex, int arrayLeft, int arrayRight, int arrayIndex, int newValue) {
        // 设置i 和 j 等于要更新的数组index
        int i = arrayIndex, j = arrayIndex;

        // arrayIndex超出范围，则直接返回
        if (i > arrayRight || j < arrayLeft)
            return segmentTree[treeIndex];

        // 左右两个index相等
        if (arrayLeft == i && arrayRight == j) {
            originalArray[i] = newValue; // 找到要更新的index
            return segmentTree[treeIndex] = originalArray[i]; // 更新segmentTree
        }

        // 分别获得左右子树的最小值
        int p1, p2;
        p1 = updatePoint(left(treeIndex) , arrayLeft , (arrayLeft + arrayRight) / 2, arrayIndex, newValue);
        p2 = updatePoint(right(treeIndex), (arrayLeft + arrayRight) / 2 + 1, arrayRight , arrayIndex, newValue);

        // 更新treeIndex的值
        return segmentTree[treeIndex] = (p1 <= p2) ? p1 : p2;
    }

同样的道理，我们可以生成最大线段树和Sum线段树。

线段树的复杂度

求线段树的区间统计，时间复杂度和二叉树的高度有关系，和元素的个数没关系，它的时间复杂度为 O(log n)。

本文的代码地址：

learn-algorithm

本文收录于 www.flydean.com

最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！

欢迎关注我的公众号:「程序那些事」,懂技术，更懂你！