作者：一曲无痕奈何

链接：https://blog.csdn.net/qq_41479464/article/details/88586512

来源：CSDN

注意区间的改变！（原来的部分被重新区间的染色覆盖了）

注意以求和问题为列，把整个区间分为很多段，当你求那一段时候，这样直接就可以拿。

每一个孩子区间都是相应的父节点的半段

注意叶子节点不一定在最后一层

求和区间的实现：

定义一个接口（融合器就是方便我对区间的操作）

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));
    }
}

亲爱的读者：有时间可以点赞评论一下