线段树初探

reso1mi 收录于数据结构

2019-12-09 约 1197 字预计阅读 3 分钟

前言

线段树其实属于比较高级的数据结构了，本人并不是竞赛选手，这里的代码也是借鉴的 bobo 老师的视频课来实现的，面试什么的一般是不会考的，这里主要是出于兴趣练练手

问题引入

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 函数的调用次数是均匀分布的。

这题如果数组不能修改的话就好说了，可以直接利用数组的前缀和，但是这里数组是会变化的，难道没更新一次都要重新遍历么？那也太慢了吧，有没有一种结构能高效的插入同时也能高效的查询？

线段树

线段树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性（它是一颗平衡二叉树），它基本能保持每个操作的复杂度为O(logN)

线段树的每个节点表示一个区间，父区间为[a,b] 则左子区间为[a,(a+b)/2]右子区间为[(a+b)/2+1,b] 最底层的叶子节点就是对应的一个个具体的元素值，这里我们采用数组来实现线段树

import java.util.function.*;
public class SegmentTree<E>{
    
    private E[] data;

    private E[] tree;

    private BiFunction<E,E,E> function;

    public SegmentTree(E[] arr,BiFunction<E,E,E> function){
        data = (E[]) new Object[arr.length];
        this.function=function;
        System.arraycopy(arr,0,data,0,arr.length);
        //值得思考为什么是 4n
        tree = (E[]) new Object[4*arr.length];
        buildSegmentTree(0,0,arr.length-1);
    }

    //根据传入的 BiFuction 构建线段树
    private void buildSegmentTree(int index,int left,int right){
        if (left==right) {
            tree[index] =data[right];
            return;
        }
        int leftIndex=leftChild(index);
        int rightIndex=rightChild(index);
        int mid=left+(right-left)/2;
        buildSegmentTree(leftIndex,left,mid);
        buildSegmentTree(rightIndex,mid+1,right);
        //根据业务需求传入 BiFunction
        tree[index]=function.apply(tree[leftIndex],tree[rightIndex]);
    }

    //范围搜索
    public E searchRange(int left,int right){
        return searchRange(0,0,data.length-1,left,right);
    }

    private E searchRange(int rootIndex,int left,int right,int targetLeft,int targetRight){
        if (targetLeft == left && targetRight == right) {
            return tree[rootIndex];
        }
        int mid=left+(right-left)/2;
        if (targetLeft>mid) {
            return searchRange(rightChild(rootIndex),mid+1,right,targetLeft,targetRight);
        }
        if (targetRight<=mid) {
            return searchRange(leftChild(rootIndex),left,mid,targetLeft,targetRight);
        }
        return function.apply(searchRange(leftChild(rootIndex),left,mid,targetLeft,mid),searchRange(rightChild(rootIndex),mid+1,right,mid+1,targetRight));
    }

    public void update(int index,E e){
        if (index<0 || index>=data.length) {
            throw new IllegalArgumentException("index illegal");
        }
        update(0,0,data.length-1,index,e);
    }

    public void update(int rootIndex,int left,int right,int targetIndex,E e){
        if (left == right) {
            tree[rootIndex]=e;
            return;
        }
        int mid=left+(right-left)/2;
        if (targetIndex<=mid) {
            update(leftChild(rootIndex),left,mid,targetIndex,e);
        }else{
            update(rightChild(rootIndex),mid+1,right,targetIndex,e);
        }
        tree[rootIndex]=function.apply(tree[leftChild(rootIndex)],tree[rightChild(rootIndex)]);
    }

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

    public E get(int index){
        if (index<0 || index>=data.length) {
            throw new IllegalArgumentException("index is illegal!");
        }
        return data[index];
    }

    //左孩子
    private int leftChild(int index){
        return index*2+1;
    }

    //右孩子
    private int rightChild(int index){
        return index*2+2;
    }
}

没啥好说的，整体还是挺简单的，代码中用到了 Java8 的函数式接口，确实挺方便的

其实我觉得有一个比较关键的点就是线段树需要多大的数组空间？

首先一颗 H 层（H 从 1 开始）的满二叉树一共有 2^H-1 个节点，我们忽略那一个节点，约为2^H个节点，而最后一层（h-1 层）有 2^(h-1)个节点，也就是说最后一层的节点树大致等于前面所有层节点的和，所以我们可以得出一个结论，在线段树中如果需要表示的区间大小为 n，并且 n 刚好等于 2 的 k 次幂的话（也就是放好构成一颗满二叉树），那么就只需要 2n 的节点个数，但是如果是n=2^k+c 那么当前层就存不下这 n 个元素，需要存到下一层，也就是空间还需要* 2，所以最后我们就需要 4n 的空间去存储这颗线段树。

这个时候再回头去做上面的题就会很简单了😁

线段树其实还有很多的扩展，上面的是最最最基本的最简单的线段树结构，我还根本就没摸到线段树的门😂，只是知道了有这么个结构

由于我实在是太菜了，也没有时间去了解那些结构了

当然面试的时候并不会考线段树这些玩意儿，我也只是为了练练手，真正的竞赛的题目也不会像上面那么简单，了解即可😅

目录

线段树初探

前言

问题引入

线段树