10.线段树(比较高级的数据结构)

2018-10-24 本文已影响53人哈哈大圣

一、线段树(区间树)的概念

Segment Tree;线段树属于高级数据结构，经常出现在算法竞赛中
为什么要使用线段树？对于有一类问题，我们关心的是线段(区间)

线段树针对的是一个固定的容量的结构

最经典的线段树的问题：区间染色有一面墙，长度为n,每次选择一段儿墙进行染色,m次操作后，我们可以看见多少种颜色？m次操作后，我们在[i,j]区间内看见多少种颜色？
注意

染色操作(更新区间)
查询操作(查询区间)
区间的大小范围不变！

另一类经典问题：区间查询查询一个区间[i,j]区间的最大值，最小值，总和比如：2017年注册用户中消费最高的用户？消费最少的用户？学习时间最长的用户？

这类问题底层解决方案的时间复杂度比较:

	使用数组实现	使用线段树
更新	O(n)	O(logn)
查询	O(n)	O(logn)

为什么要使用线段树.png

什么是线段树.png

2. 线段树的基础表示

平衡二叉树的定义：最大的深度和最小的深度的差最多可能为1

线段树不是完全二叉树
线段树是平衡二叉树
堆(完全二叉树)也是一个平衡二叉树

平衡二叉树.png

线段树依然可以用数组表示可以将线段树看做一个满二叉树，最深度的没有节点的看做空节点

看做满二叉树.png

线段树是最深度的一层或者两层存储n个元素，其他深度储存对应下一层的和或者什么的。

如果区间有n个元素，那么数组表示需要多少个节点呢？

需要多少个节点1.png

需要多少个节点2.png

需要多少个节点3.png

需要多少个节点4.png

3. 以求和为例创建一个线段树

要干的事儿：每一个父节点保存一个子范围内所有数值之和

虽然是以求和为例，但是这个线段树不仅仅只支持求和，它会根据传入的marge(推荐使用lamda表达式)操作自定义功能，比如去最大值/最小值

注意:线段的树的空间大小不发生变化

创建线段树的方法名为buildSegmentTree

递归创建的实现思想利用数组与满二叉树(不一定满，但是看做是满二叉树)的关系，从根节点开始，以二分法指定范围并以递归的方式创建节点，直到范围的左右边界相等，说明已经深度到最底层了(很神奇是吧！我也觉得，数学这个东西太牛逼了)每个父节点储存内容的规则是用户传入一个实现融合器接口的函数(方法)。详见下面的创建线段树的函数(方法)。

查询一个区间的和

对应为querySegmentTree函数
注意：这个方法不仅仅只能查询和，她可以根据实现merge接口的lamda表达式实现定制的逻辑，比如求最大数、最小数

递归实现思想：以跟节点开始，传入tree中对饮的节点索引treeIndex，相关节点负责的范围[r...l]需要查询的区间范围[queryL...queryR]，当前节点的区间与当前查询的区间相同时为终止条件，返回当前节点的值；如果当前需要查询的区间在当前节点的左子节点负责的范围，就继续在左子节点查询；对应的，如果当前需要查询的区间在当前节点右子节点负责的范围，就继续在右子节点查询；如果当前需要查询的区间横跨左右子节点负责的范围，将需要查询的区间从左右节点的边界处节段，分别对应进入左右子节点进行查询，并将结果进行merge操作！

跟新操作update

递归实现更新操作实现：实现思想与buildSegmentTree的思想是一样的，递归的改动所遍历的节点值，根据需要改变的索引与当前节点负责的范围之间的关系选择递归左子节点还是右子节点，当递归的节点所负责的左右范围相等时，表明已经递归到深处。

区间统一更新操作batchOpreation
比如讲区间[i,j]都加上n

递归实现现将原始数组对应的数据更新，再从树的根节点进行递归，没第一到一个节点就执行相应次数的更新操作。。。请参照相关代码进行理解！

具体实现如下代码

Merge.java接口，需要用户实现相应规则的接口

public interface Merge<E> {
    E merge(E a, E b);
}

SegmentTree.java,线段树的实现

public class SegmentTree<E> {

    private E[] tree; /**保存将要保存的树*/
    private E[] data; /**保存传入的数组，新建一个数组，避免操作原始数组*/
    private Merge<E> merge; /**保存传入实现融合器接口的类，建议写一个lamda表达式*/

    /**批量操作的接口，需要传入一个lamda表达式,这里不能使用private,否则不允许传入一个类*/
    public interface Batch<E> {
        E batch(E a, E b);
    }

    public SegmentTree(E[] arr, Merge<E> merge) {

        /**由于是泛型，所以目前定义数组不晓得用啥子类型
         * 只好用所有类的祖先Object来创了！*/
        data = (E[])new Object[arr.length];
        for(int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }

        this.tree = (E[])new Object[4 * arr.length];
        this.merge = merge;
        buildSegmentTree(0, 0, data.length - 1);
    }

    /**在treeIndex的位置创建表示区间[l...r]的线段树*/
    private void buildSegmentTree(int treeIndex, int l, int r) {

        /**递归到最深处，这个时候该储存数组中的东西了*/
        if(l == r) {
            this.tree[treeIndex] = this.data[l];
            return;
        }

        int leftChild = this.leftChild(treeIndex);
        int rightChild = this.rightChild(treeIndex);

        int middle = (l + r) / 2;
        this.buildSegmentTree(leftChild, l, middle);
        this.buildSegmentTree(rightChild, middle + 1, r);

        this.tree[treeIndex] = merge.merge(tree[leftChild], tree[rightChild]);
    }

    /**给定一个区间[lift,right]进行查询和操作*/
    public E querySegmentTree(int left, int right) {
        if(left < 0 || left >= data.length || right < 0 || right >= data.length)
            throw new IllegalArgumentException("Illegal range!");
        return query(0,0, data.length - 1, left, right);
    }

    private E query(int treeIndex, int l, int r, int queryL, int queryR) {
        if(queryL == l && queryR == r)
            return this.tree[treeIndex];

        int leftChild = this.leftChild(treeIndex);
        int rightChild = this.rightChild(treeIndex);
        int middle = (l + r) / 2;

        if(queryR <= middle)
            return this.query(leftChild, l, middle, queryL, queryR);
        else if(queryL > middle)
            return this.query(rightChild, middle + 1, r, queryL, queryR);
        else {
            E left = this.query(leftChild, l, middle, queryL, middle);
            E right = this.query(rightChild, middle + 1, r,middle + 1, queryR);
            return this.merge.merge(left, right);
        }
    }

    /**update操作*/
    public void update(int index, E e) {
        if(index < 0 || index >= data.length)
            throw new IllegalArgumentException("Index is illegal!");

        this.data[index] = e;
        update(0, 0, data.length - 1, index, e);
    }

    private void update(int treeIndex, int l, int r, int index, E e) {
        if(l == r) {
            tree[treeIndex] = e;
            return;
        }

        int leftChild = this.leftChild(treeIndex);
        int rightChild = this.rightChild(treeIndex);
        int middle = (r + l) / 2;

        if(index <= middle)
            update(leftChild, l, middle, index, e);
        else
            update(rightChild, middle + 1, r, index, e);

        tree[treeIndex] = merge.merge(tree[leftChild], tree[rightChild]);
    }

    /**区间批量操作，要求用户传入一个操作函数*/
    public void batchOpreation(int l, int r, E e, Batch<E> batch) {
        if(l < 0 || l >= data.length || r < l || r >= data.length)
            throw new IllegalArgumentException("The range is wrong!");

        for(int i = l; i <= r; i ++) {
            data[i] = batch.batch(data[i], e);
        }

        batchOpreation(0, 0, data.length - 1, l, r, e, batch);
    }

    private void batchOpreation(int treeIndex, int l, int r,
                                int rangeL, int rangeR, E e, Batch<E> batch){
        /**终止条件，递归到了最深的一层*/
        if(l == r) {
            tree[treeIndex] = data[l];
            return;
        }

        /**改变当前节点的储存信息，这波操作有点溜，我想出来的！！*/
        for(int i = 0; i < rangeR - rangeL + 1; i ++)
            tree[treeIndex] = batch.batch(tree[treeIndex], e);

        int middle = (l + r) / 2;
        int leftChild = this.leftChild(treeIndex);
        int rightChild = this.rightChild(treeIndex);

        if(rangeR <= middle)
            this.batchOpreation(leftChild, l, middle, rangeL, rangeR, e, batch);
        else if(rangeL > middle)
            this.batchOpreation(rightChild, middle + 1, r, rangeL, rangeR, e, batch);
        else {
            this.batchOpreation(leftChild, l, middle, rangeL, middle, e, batch);
            this.batchOpreation(rightChild, middle + 1, r, middle + 1, rangeR, e, batch);
        }

    }

    public int getSize() {
        return data.length;
    }

    public E get(int index) {
        if(index < 0 || index >= data.length)
            throw new IllegalArgumentException("Index is out of boundary!");

        return data[index];
    }

    /**返回完全二叉树的数组表示中，一个缩影所表示的元素的做孩子节点的索引*/
    private int leftChild(int index) {
        return 2 * index + 1;
    }

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

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("[");
        for(int i = 0; i < this.tree.length; i ++) {
            if(tree[i] != null)
                res.append(tree[i]);
            else
                res.append("null");

            if(i != tree.length - 1)
                res.append(", ");
        }
        res.append("]");
        return res.toString();
    }
}

四、leetCode上第303号问题

对于303号问题不推荐使用线段树解决

/**新建一个数组*/
class NumArray {
    private int[] sum;
    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];

        sum[0] = 0; // 这么设计是很有好处的
        for(int i = 1; i < sum.length; i ++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }

    }

    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

五、leetCode上第307号问题

推荐使用线段树解决307号问题

class NumArray {
    private interface  Merge<E> {
        /**见上面代码*/
    }
    
    private class SegmentTree<E> {
        /**见上面代码*/
    }
    
    private SegmentTree<Integer> segmentTree;

    public NumArray(int[] nums) {
        if(nums.length > 0) {
            Integer[] data = new Integer[nums.length];
            for(int i = 0; i < nums.length; i++) {
                data[i] = nums[i];
            }
            segmentTree = new SegmentTree<>(data, (a, b) -> a + b);
        }
    }

    public void update(int i, int val) {
        segmentTree.update(i, val);
    }

    public int sumRange(int i, int j) {
        return segmentTree.querySegmentTree(i, j);
    }
}