线段树总结-java版
目录
为什么要有线段树
下面我们从一个经典的例子来了解线段树，问题描述如下:从数组arr[0...n-1]中查找某个数组某个区间内的最小值，其中数组大小固定，但是数组中的元素的值可以随时更新。
对这个问题一个简单的解法是：遍历数组区间找到最小值，时间复杂度是O(n),额外的空间复杂度O(1)。当数据量特别大，而查询操作很频繁的时候，耗时可能会不满足需求。
另一种解法：使用一个二维数组来保存提前计算好的区间[i,j]内的最小值，那么预处理时间为O(n^2)，查询耗时O(1), 但是需要额外的O(n^2)空间，当数据量很大时，这个空间消耗是庞大的，而且当改变了数组中的某一个值时，更新二维数组中的最小值也很麻烦。
简介
线段树之所以称为“树”，是因为其具有树的结构特性。线段树由于本身是专门用来处理区间问题的（包括RMQ、RSQ问题等）。
对于每一个子节点而言，都表示整个序列中的一段子区间；对于每个叶子节点而言，都表示序列中的单个元素信息；子节点不断向自己的父亲节点传递信息，而父节点存储的信息则是他的每一个子节点信息的整合。
有没有觉得很熟悉？对，线段树就是分块思想的树化，或者说是对于信息处理的二进制化——用于达到O(logn)级别的处理速度，log以2为底。（其实以几为底都只不过是个常数，可忽略)。而分块的思想，则是可以用一句话总结为：通过将整个序列分为有穷个小块，对于要查询的一段区间，总是可以整合成k个所分块与m个单个元素的信息的并(0≤k,m≤sqrt{n})。但普通的分块不能高效率地解决很多问题，所以作为log级别的数据结构，线段树应运而生。
得到min的线段树样例
我们可以用线段树来解决这个问题：预处理耗时O(n)，查询、更新操作O(logn)，需要额外的空间O(n)。根据这个问题我们构造如下的二叉树
- 叶子节点是原始组数arr中的元素
- 非叶子节点代表它的所有子孙叶子节点所在区间的最小值
例如对于数组[2, 5, 1, 4, 9, 3]可以构造如下的二叉树（背景为白色表示叶子节点，非叶子节点的值是其对应数组区间内的最小值，例如根节点表示数组区间arr[0...5]内的最小值是1）：
由于线段树的父节点区间是平均分割到左右子树，因此线段树是完全二叉树，对于包含n个叶子节点的完全二叉树，它一定有n-1个非叶节点，总共2n-1个节点，因此存储线段是需要的空间复杂度是O(n)。
java实现
合成器
合成器，代表父节点，根据两个子节点得到的value
如果设置为最大或者最小之类的，怎么设置看测试那里
package datastructure.tree.segementtree;
/**合成器接口
* @author xusy
*
* @param <E>
*/
public interface Merger<E>{
/**合成方法，a和b代表一个父节点下的两个子节点的值
* @param a
* @param b
* @return 根据a和b，计算出的父节点对应的值
*/
public E merge(E a,E b);
}
线段树
可以看到每个节点对应的data中的左边界和右边界，没有记录在节点中，是在方法中不断递归计算的
一开始的root，手动设置index=0，左边界为0，右边界为length-1
然后子节点，左孩子对应[left,mid] 右孩子对应[mid+1,right]
如果想要得到某个区间，对应的问题的值，调用query(left,right) 即可
修改用set(index,value)
package datastructure.tree.segementtree;
/** 线段树
* @author xusy
*
* @param <E>
*/
public class SegementTree<E>{
/**
* 线段树中传入的值，存储的副本
*/
public E[] data;
/**
* 线段树中的节点，其中父节点的值为它的两个子节点merge后的值
*/
public E[] tree;
/**
* 合成器，构造线段树时候同时传入合成器
*/
public Merger<E> merger;
/**构造线段树
* @param data 传入的数据
* @param merger 传入的合成器
*/
public SegementTree(E[] data,Merger<E> merger){
this.merger=merger;
int length=data.length;
this.data=(E[])new Object[length];
//复制数据到data中
for(int i=0;i<length;i++){
this.data[i]=data[i];
}
//总共n个叶子节点，n-1个非叶子节点
tree=(E[])new Object[length*2-1];
//构造线段树
buildSegementTree(0,0,length-1);
}
/** 构造线段树中的tree中的节点
* @param treeIndex tree中对应节点的index
* @param left 这个节点对应data中的范围的左边界,root对应0
* @param right 这个节点对应data中的范围的右边界,root对应length-1
*/
public void buildSegementTree(int treeIndex,int left,int right){
if(left==right){
//如果left==right，证明递归结束，在对应的index设置data里left的值
tree[treeIndex]=data[left];
return;
}
//tree中父节点为treeIndex,的左右孩子的index
int leftChildIndex=getLeftChild(treeIndex);
int rightChildIndex=getRightChild(treeIndex);
int mid=left+(right-left)/2;
//构造左右孩子节点
buildSegementTree(leftChildIndex, left, mid);
buildSegementTree(rightChildIndex, mid+1, right);
//根据左右孩子的值，通过合成器，决定父节点的值
tree[treeIndex]=merger.merge(tree[leftChildIndex], tree[rightChildIndex]);
}
/**返回左孩子在数组中的位置
* @param index 父节点的index
* @return 左孩子节点的index
*/
public int getLeftChild(int index){
//可以这样看，root节点，index：0
//root的左孩子，index：1
//root的右孩子，index：2
//root的左孩子的左孩子，index：3
//root的左孩子的有孩子，index：4
return 2*index+1;
}
/**返回右孩子在数组中的位置
* @param index 父节点的index
* @return 右孩子节点的index
*/
public int getRightChild(int index){
return 2*index+2;
}
/**
* 打印线段树
*/
public void printSegementTree(){
System.out.println("开始打印线段树----------");
System.out.println("线段树数据的长度为"+data.length);
for(int i=0;i<tree.length;i++){
System.out.println("位置"+i+": "+tree[i]);
}
System.out.println("打印线段树结束----------");
}
/** 返回data中区间left和right间，对应的值
* @param left
* @param right
* @return
*/
public E query(int left,int right){
if(left<0||right<0||left>=data.length||right>=data.length||left>right){
return null;
}
return queryRange(0,0,data.length-1,left,right);
}
/** 在以tree中位置为treeIndex为根节点，而且该节点对应的data中的范围为[treeLeft,treeRight] <br>
* 查询范围为[queryLeft,queryRight]对应的值
* @param treeIndex
* @param treeLeft
* @param treeRight
* @param queryLeft
* @param queryRight
* @return
*/
public E queryRange(int treeIndex,int treeLeft,int treeRight,int queryLeft,int queryRight){
if(treeLeft==queryLeft&&treeRight==queryRight){
//如果该节点的范围正好对应查询范围，直接返回
return tree[treeIndex];
}
int leftChildIndex=getLeftChild(treeIndex);
int rightChildIndex=getRightChild(treeIndex);
int mid=treeLeft+(treeRight-treeLeft)/2;
if(queryLeft>=mid+1){
//如果查询范围仅仅对应左孩子或者右孩子
return queryRange(rightChildIndex, mid+1, treeRight, queryLeft, queryRight);
}
else{
if(queryRight<=mid){
return queryRange(leftChildIndex, treeLeft, mid, queryLeft, queryRight);
}
}
//查询范围，左右孩子都有
E resultLeft=queryRange(leftChildIndex, treeLeft, mid, queryLeft, mid);
E resultRight=queryRange(rightChildIndex, mid+1, treeRight, mid+1, queryRight);
//最终结果是左右孩子的合并
E result=merger.merge(resultLeft, resultRight);
return result;
}
/**在线段树中修改data中index的元素，设置新的值为value
* @param index
* @param value
*/
public void set(int index,E value){
if(index<0||index>=data.length){
return;
}
setValue(0,0,data.length-1,index,value);
}
/**在以tree中位置为treeIndex为根节点，而且该节点对应的data中的范围为[treeLeft,treeRight] 下，<br>
* 修改data中index的元素，设置新的值为value
* @param treeIndex
* @param treeLeft
* @param treeRight
* @param index
* @param value
*/
public void setValue(int treeIndex,int treeLeft,int treeRight,int index,E value){
if(treeLeft==treeRight){
tree[treeIndex]=value;
return;
}
int leftChildIndex=getLeftChild(treeIndex);
int rightChildIndex=getRightChild(treeIndex);
int mid=treeLeft+(treeRight-treeLeft)/2;
if(index<=mid){
setValue(leftChildIndex, treeLeft, mid, index, value);
}
else{
setValue(rightChildIndex, mid+1, treeRight, index, value);
}
tree[treeIndex]=merger.merge(tree[leftChildIndex], tree[rightChildIndex]);
}
}
测试
下面就有merger对象的生成方式，得到小的值
package datastructure.tree.segementtree;
public class Main {
public static void main(String[] args) {
Merger<Integer> merger=new Merger<Integer>() {
@Override
public Integer merge(Integer a, Integer b) {
if(a<b){
return a;
}
else{
return b;
}
}
};
Integer[] data=new Integer[]{1,4,7,-4,3};
SegementTree<Integer> tree=new SegementTree<>(data, merger);
tree.printSegementTree();
System.out.println(tree.query(1, 4));
tree.set(3, 0);
System.out.println(tree.query(1, 4));
}
}