前言

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

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

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

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

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