java线段树的详细介绍
注意区间的改变！（原来的部分被重新区间的染色覆盖了）
注意以求和问题为列，把整个区间分为很多段，当你求那一段时候，这样直接就可以拿。
每一个孩子区间都是相应的父节点的半段
注意叶子节点不一定在最后一层
求和区间的实现：
定义一个接口（融合器就是方便我对区间的操作）
public interface Merge<E> {
E merge(E a,E b);
}
public class SegMentTree<E> {
private E[] tree;
private E data[] ;//存储一个副本
private Merge<E> merge;//用户构造好这个线段树时候同时构造好融合器
//考虑整个区间
public SegMentTree(E[] arr,Merge<E>merge){ //传入一个融合器
this.merge = merge;
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);
}
//在treeIndex的位置创建表示区间[l,r]的线段树
private void buildSegMentTree(int treeIndex, int l, int r) {
if (l==r){ //递归结束的条件
tree[treeIndex] = data[l];
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int mid = l+(r-l)/2;//这样定义中间位置放置溢出
buildSegMentTree(leftTreeIndex,l,mid); //创建左子树
buildSegMentTree(rightTreeIndex,mid+1,r);//创建右子树
//这个E的类型无法用求和
tree[treeIndex] = merge.merge(tree[leftTreeIndex],tree[rightTreeIndex]); //求和
//tree[treeIndex] = Math.max(tree[leftTreeIndex],tree[rightTreeIndex]); //求两者之间的最大值
}
public int getSize(){
return data.length;
}
public E get(int index){
return data[index];
}
private int leftChild(int index){
return 2*index+1;
}
private int rightChild(int index){
return 2*index+2;
}
@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();
}
}
class Main{
public static void main(String [] args){
Integer nums[] = {1,2,3,4,-5,-9,10,125,32};
//SegMentTree<Integer> segMentTree = new SegMentTree<Integer>(nums,(a,b)->a+b);
SegMentTree<Integer> segMentTree = new SegMentTree<Integer>(nums, new Merge<Integer>() {
@Override
public Integer merge(Integer a, Integer b) {
return a+b;
}
});
System.out.println(segMentTree);
}
}
下面是对区间查询的代码实现和思路：
定义一个接口（融合器就是方便我对区间的操作）
public interface Merge<E> {
E merge(E a,E b);
}
public class SegMentTree<E> {
private E[] tree;
private E data[] ;//存储一个副本
private Merge<E> merge;//用户构造好这个线段树时候同时构造好融合器
//考虑整个区间
public SegMentTree(E[] arr,Merge<E>merge){ //传入一个融合器
this.merge = merge;
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);
}
//在treeIndex的位置创建表示区间[l,r]的线段树
private void buildSegMentTree(int treeIndex, int l, int r) {
if (l==r){ //递归结束的条件
tree[treeIndex] = data[l];
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int mid = l+(r-l)/2;//这样定义中间位置放置溢出
buildSegMentTree(leftTreeIndex,l,mid); //创建左子树
buildSegMentTree(rightTreeIndex,mid+1,r);//创建右子树
//这个E的类型无法用求和
tree[treeIndex] = merge.merge(tree[leftTreeIndex],tree[rightTreeIndex]); //求和
//tree[treeIndex] = Math.max(tree[leftTreeIndex],tree[rightTreeIndex]); //求两者之间的最大值
}
public int getSize(){
return data.length;
}
public E get(int index){
return data[index];
}
private int leftChild(int index){
return 2*index+1;
}
private int rightChild(int index){
return 2*index+2;
}
//返回区间[queryL,queryR]的值
public E query(int queryL,int queryR){
return query(0,0,data.length-1,queryL,queryR);
}
//在以treeID为根的线段树中[l...r]的范围里，搜索区间[queryl,queryr]的值
private E query(int treeIndex,int l,int r,int queryL,int queryR){
if(l==queryL&&r==queryR)
return tree[treeIndex];
int mid = l + (r-l)/2;
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
if (queryL>=mid+1){
return query(rightTreeIndex,mid+1,r,queryL,queryR);
}else if (queryR<=mid){
return query(leftTreeIndex,l,mid,queryL,queryR);
}
//分散在两个区间
E leftResult = query(leftTreeIndex,l,mid,queryL,queryR);
E rightResult = query(rightTreeIndex,mid+1,r,mid+1,queryR);
return merge.merge(leftResult,rightResult);
}
@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();
}
}
class Main{
public static void main(String [] args){
Integer nums[] = {1,2,3,4,-5,-9,10,125,32};
//SegMentTree<Integer> segMentTree = new SegMentTree<Integer>(nums,(a,b)->a+b);
SegMentTree<Integer> segMentTree = new SegMentTree<Integer>(nums, new Merge<Integer>() {
@Override
public Integer merge(Integer a, Integer b) {
return a+b;
}
});
System.out.println(segMentTree);
System.out.println(segMentTree.query(0,2));
}
}