avatar

目录
线段树初探

前言

线段树其实属于比较高级的数据结构了,本人并不是竞赛选手,这里的代码也是借鉴的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

说明:

  1. 数组仅可以在 update 函数下进行修改。
  2. 你可以假设 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 的空间去存储这颗线段树。

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

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

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

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

文章作者: imlgw
文章链接: http://imlgw.top/2019/12/09/xian-duan-shu/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 iMlGw0
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论