算法与数据结构系列之[线段树]

1.什么是线段树

百度百科解释：

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

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。

其实，线段树就是一棵平衡的二叉树，可以用数组来存储，把数组分成若干个段，每个节点保存一个段，表示一个区间，父节点保存左右子节点区间和，子节点分别表示父节点的左右半区间，如果父节点保存的区间是[a,b],那么左子节点保存的区间为[a,(a+b)/2],右子节点保存的区间为[(a+b)/2+1,b]。

线段树大多数情况下本身是固定的，所以一般不用考虑向线段树中添加和删除元素，线段树要解决的主要是连续区间的动态查询问题，比如一个电商网站，要统计一段时间区间内的用户流量是多少？此时使用线段树效率比较高。

2.为什么要使用线段树

更新区间中一个元素或者一个区间的值,查询一个区间[i,j]的最大值，最小值，或者区间数字和,使用数组时间复杂度为O(n),使用线段树时间复杂度是O(logn),要比使用数组的效率高很多，所以使用线段树进行统计分析是很高效的。

3.线段树图示

图一

4.线段树的查询

如下图，查询[2,5],首先从根节点[0,7]开始查询，[2,5]一部分落在了根节点的左子节点[0,3]上，另一部分落在了根节点的右子节点[4,5]上
，所以把要查询的[2,5]分成查询[2,3]和查询[4,5],这样在根节点的左子节点上查询[2,3]，在根节点的右子节点上查询[4,5]

图二

接下来进行一次遍历，发现[0,3]的左子节点和要查询的[2,3]没关系，则在[0,3]的右子节点[2,3]上查询，发现[2,3就是要查询的值，停止向下遍历，直接取值 即可。查询[4,5]的过程也一样。

图三

5.代码实现：

Merget.java

/**
* 融合器
* @param <E>
*/
public interface Merger<E> {
   E merge(E a,E b);    //将两个元素融合成一个
}

SegmentTree.java

/**
* 线段树的实现
* @param <E>
*/
public class SegmentTree<E> {
    private  E[] tree;   //存放线段树节点
    private E[] data;  //存放线段树中的节点元素值
    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,data.length - 1);
    }

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

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

    //返回给定索引表示的左孩子节点的索引
    private int leftChild(int index){
        return index * 2 + 1;
    }

    //返回给定索引表示的右孩子的索引
    private int rightChild(int index){
        return index * 2 + 2;
    }

    /**
     * 线段树的创建
     * @param treeIndex 当前节点索引，从0开始
     * @param left 左区间端点
     * @param right 右区间端点
     */
    private void buildSegmentTree(int treeIndex,int left,int right){
        if(left == right){
            tree[treeIndex] = data[left];
            return;
        }

        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);

        //区间中点
        int mid = (left + right) / 2;

        //创建左右区间节点
        buildSegmentTree(leftTreeIndex,left,mid);
        buildSegmentTree(rightTreeIndex,mid+1,right);

        tree[treeIndex] = merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("[");
        for (int i = 0; i < 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();
    }

    //返回区间[queryL,queryR]的值
    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);
    }

    //在以当前节点treeIndex为根的线段树[left,right]范围里搜索区间[queryL,queryR]的值
    private E query(int treeIndex,int left,int right,int queryL,int queryR){
        if(queryL == left && queryR == right)
            return tree[treeIndex];

        int mid = (left + right) / 2;
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);

        if(queryL >= mid+1)
            return query(rightTreeIndex,mid+1,right,queryL,queryR);
        else if(queryR <= mid)
            return query(leftTreeIndex,left,mid,queryL,queryR);
        E leftResult = query(leftTreeIndex,left,mid,queryL,mid);
        E rightResult = query(rightTreeIndex,mid+1,right,mid+1,queryR);
        return merger.merge(leftResult,rightResult);
    }

    //将index位置的值更新为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);
    }

    //在以treeIndex为根的线段树中更新index的值为e
    private void set(int treeIndex,int left,int right,int index,E e){
        if(left == right){
            tree[treeIndex] = data[left];
            return;
        }

        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        int mid = (left + right) / 2;

        if(index >= mid + 1)
            set(rightTreeIndex,mid+1,right,index,e);
        else
            set(leftTreeIndex,left,mid,index,e);
        tree[treeIndex] = merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]);
    }

    public static void main(String[] args) {
        Integer[] nums = {-2,0,3,-5,2,1};
        SegmentTree<Integer> segmentTree = new SegmentTree<>(nums,(a,b) ->a + b);
        System.out.println(segmentTree);
        System.out.println(segmentTree.query(0,3));
    }
}

6.线段树应用
LeetCode第303题：区域和检索-数组不可变
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:

• 你可以假设数组不可变。
• 会多次调用 sumRange 方法。

1.使用线段树： 如图代码,将我们自己写的融合器接口和线段树的类复制到LeetCode，作为内部类。

图四

2.不使用线段树：

class NumArray {
    private int[] sum;//sum[i]存储前i个元素的和，sum[0] = 0
                    //sum[i]存储的nums[0...i-1]的和
    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题：区域和检索-数组可修改
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。

示例:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
说明:

• 数组仅可以在 update 函数下进行修改。
• 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的

1.不使用线段树（性能很差，提交时可能会报超出时间限制）

class NumArray {

    private int[] sum; //sum[i]存储前i个元素的和，sum[0] = 0
                        //sum[i]存储的nums[0...i-1]的和
    private int[] data;

    public NumArray(int[] nums){
        data= new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            data[i] = nums[i];
        }

        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 void update(int i,int val){
        data[i] = val;
        for(int j = i+1;j<sum.length;j++){
            sum[j] = sum[j-1] + data[j-1];
        }
    }

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

每一次的updata操作都是O(n)的时间复杂度，如果该操作进行m次，则整体的时间复杂度就是O(m*n)，所以执行的速度是很慢的。

2.使用线段树

图五

每一次sumRange和update操作的时间复杂度都为O(logn),各调用m次，各自总的时间负责度均为O(m*logn),比不使用线段树性能提升很多。

7.总结：

这篇介绍了线段树的概述，查询，以及代码实现，最后借LeetCode上两道区域检索的问题进行线段树的应用。分别都用了两种方法：使用线段树和使用数组，唯一不同的是第二个问题的数组是可以更新的，需要动态更新某个区间内的数组值，这样一比较使用线段树的优势就凸显出来了，我们已经知道，使用数组查询和更新的时间复杂度都是O(n),而使用线段树进行查询和更新的操作的时间复杂度都为O(logn),在上面第二个问题的中使用线段树的性能优势体现的非常明显。所以当需要动态更新区间值的时候，使用线段树是一个不错的选择。

本人微信公众号，点关注，不迷路