通知
  • 关于网站更多信息请加QQ群(1061691290)
  • jpress升级到4.x,显示有些问题,修复中
  • 网站还会持续更新
文章来源于网络,无法注明出处的还请谅解,如果出处注明错误(如仍是载转),请联系我修改

java贪心算法(线段树)的详细介绍

868人浏览 / 0人评论 / | 这是对我有帮助的文章  | 分类: 算法  | 标签: 数据结构与算法  | 

作者:一曲无痕奈何

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

来源:CSDN

segment_tree2.png

segment_tree3.png

注意区间的改变!(原来的部分被重新区间的染色覆盖了)

segment_tree4.png

segment_tree5.pngsegment_tree6.png

segment_tree7.png

segment_tree8.png

segment_tree9.png

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

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

segment_tree10.png

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

segment_tree11.png

segment_tree12.png

segment_tree13.png

求和区间的实现:

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

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

segment_tree14.png

下面是对区间查询的代码实现和思路:

segment_tree15.png

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

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

segment_tree16.png


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

点赞(0) 打赏

全部评论

还没有评论!