首页 > 其他分享 >数据结构 玩转数据结构 9-4 线段树中的区间查询

数据结构 玩转数据结构 9-4 线段树中的区间查询

时间:2023-01-17 16:56:43浏览次数:62  
标签:queryR index return int tree 玩转 数据结构 树中 queryL

0    课程地址

https://coding.imooc.com/lesson/207.html#mid=13846

 

1    重点关注

1.1    线段树区间查询

见3.1

 

 

2    课程内容

 

 

3    Coding

3.1    线段树区间查询代码实现

  • 关键图

 

  • 关键代码
//3     查询线段树区间
    public E query(int queryL,int queryR){
        if(queryL<0||queryR>= data.length||queryL>queryR){
            throw new IllegalArgumentException("index is error");
        }
        return query(queryL,queryR,0,0, data.length-1);
    }

    private E query(int queryL,int queryR,int index,int l,int r){

        if(queryL == l&&queryR == r){
            return tree[index];
        }

        int mid = l+(r-l)/2;
        int leftIndex = getLeftChild(index);
        int rightIndex = getRightChild(index);

        //如果
        if(queryL>=mid+1){
            return query(queryL,queryR,rightIndex,mid+1,r);
        }else if(queryR<=mid){
            return query(queryL, queryR,leftIndex,l,mid);
        }else{
            E leftE = query(queryL, mid,leftIndex,l,mid);
            E rightE = query(mid+1,queryR,rightIndex,mid+1,r);
            return merger.merge(leftE, rightE);
        }
    }

 

  • 线段树类:
package com.company;

/**
 * 线段树
 * 根据入参数组的元素个数,制造出线段树节点元素个数
 * @author weidoudou
 * @date 2023/1/15 15:24
 **/
public class SegmentTree<E> {
    //1     初始化线段树元素和数组元素
    private E[] data;
    private E[] tree;
    private Merge<E> merger;

    /**
     * 初始化数组元素和tree(4*元素个数上节有推导)
     * @author weidoudou
     * @date 2023/1/15 15:34
     * @param nums 请添加参数描述
     * @return null
     **/
    public SegmentTree(E [] nums,Merge<E> merger){
        data = (E[])new Object[nums.length];
        for(int i = 0; i < nums.length; i++){
            data[i] = nums[i];
        }

        this.merger = merger;

        tree = (E[])new Object[4*nums.length];
        buildSegmentTree(0,0,data.length-1);
    }

    //2     创建线段树
    private void buildSegmentTree(int index,int l,int r){
        //2.1   终止条件
        if(l==r){
            tree[index] = data[l];

        //2.2   循环条件
        }else{
            //定义mid 将线段树节点平均拆分
            int mid = l+(r-l)/2;
            int indexL = getLeftChild(index);
            int indexR = getRightChild(index);
            buildSegmentTree(indexL,l,mid);
            buildSegmentTree(indexR,mid+1,r);
            tree[index] = merger.merge(tree[indexL],tree[indexR]);
        }

    }

    //3     查询线段树区间
    public E query(int queryL,int queryR){
        if(queryL<0||queryR>= data.length||queryL>queryR){
            throw new IllegalArgumentException("index is error");
        }
        return query(queryL,queryR,0,0, data.length-1);
    }

    private E query(int queryL,int queryR,int index,int l,int r){

        if(queryL == l&&queryR == r){
            return tree[index];
        }

        int mid = l+(r-l)/2;
        int leftIndex = getLeftChild(index);
        int rightIndex = getRightChild(index);

        //如果
        if(queryL>=mid+1){
            return query(queryL,queryR,rightIndex,mid+1,r);
        }else if(queryR<=mid){
            return query(queryL, queryR,leftIndex,l,mid);
        }else{
            E leftE = query(queryL, mid,leftIndex,l,mid);
            E rightE = query(mid+1,queryR,rightIndex,mid+1,r);
            return merger.merge(leftE, rightE);
        }
    }


    //4     基本方法
    public int getSize(){
        return data.length;
    }

    public E get(int index){
        if(index<0||index>=getSize()){
            throw new IllegalArgumentException("get失败");
        }
        return data[index];
    }

    public int getLeftChild(int index){
        return index*2+1;
    }

    public int getRightChild(int index){
        return index*2+2;
    }

    public String toString(){
        StringBuffer sbf = new StringBuffer();
        sbf.append("[");
        for(int i = 0;i< tree.length;i++){
            if(tree[i]!=null){
                sbf.append(tree[i]);
            }else{
                sbf.append("null");
            }
            if(i!=tree.length-1){
                sbf.append(",");
            }
        }


        sbf.append("]");
        return sbf.toString();
    }


}

 

  • 自定义接口
package com.company;

/**
 * 融合函数
 * @author weidoudou
 * @date 2023/1/17 6:38
 **/
public interface Merge<E> {
    E merge(E left,E right);
}

 

  • 测试类:
    public static void main(String[] args) {
        Integer[] nums = {-2,0,3,-5,2,1};
        SegmentTree<Integer> segmentTree = new SegmentTree<>(nums, new Merge<Integer>() {
            @Override
            public Integer merge(Integer left, Integer right) {
                return left*right;
            }
        });

        System.out.println(segmentTree.query(0,5));
    }

 

  • 测试结果:
0

Process finished with exit code 0

 

标签:queryR,index,return,int,tree,玩转,数据结构,树中,queryL
From: https://www.cnblogs.com/1446358788-qq/p/17058167.html

相关文章

  • 读编程与类型系统笔记09_泛型数据结构
    1. 恒等函数1.1. 在代数中,恒等函数指的是函数f(x)=x1.2. 恒等逻辑与getNumbers()和assembleWidgets()的问题域解耦,因为恒等逻辑和问题域是正交的,或者说是独立的2.......
  • 数据结构 玩转数据结构 9-3 创建线段树
    0课程地址https://coding.imooc.com/lesson/207.html#mid=13845 1重点关注1.1创建线段树见3.1 1.2代码如何引入方法见3.1 2......
  • 【ES6】JS的Set和Map数据结构
    【ES6】JS的Set和Map数据结构​​一、Set​​​​1、基本用法​​​​2、4种操作方法​​​​3、4种遍历方法​​​​4、Set的应用​​​​1)Set转化为数组​​​​2)去除数组......
  • C/C++数据结构题目[2023-01-16]
    C/C++数据结构题目[2023-01-16]以下内容二选一题目1:校园导航系统的设计与实现问题描述:校园导航系统能够提供校园内场所信息和路径查询。以传媒大学校园为例,校园内包......
  • 跳跃表数据结构与算法分析
    作者:京东物流纪卓志目前市面上充斥着大量关于跳跃表结构与Redis的源码解析,但是经过长期观察后发现大都只是在停留在代码的表面,而没有系统性地介绍跳跃表的由来以及各种常量......
  • 跳跃表数据结构与算法分析
    作者:京东物流纪卓志目前市面上充斥着大量关于跳跃表结构与Redis的源码解析,但是经过长期观察后发现大都只是在停留在代码的表面,而没有系统性地介绍跳跃表的由来以及各种......
  • 玩转云端 | 天翼云数据加密,护航企业数据安全
    有交流就会产生信息,为了防止信息泄露,人们通常会采取一些特殊的措施来保护信息。很早以前,“数据加密”就出现在人类的生活中。比如:由姜子牙创造的历史上最早的密钥——阴符(兵......
  • 【数据结构与算法】二分查找算法(C++实现)
    两种写法,取决于划分规则。这两种写法是学的yxc的,至此以后,写二分查找再也不含糊了!yxc的分享在此:二分查找算法模板第一种写法:boolbinarySearch(vector<int>&nums,int......
  • 【Java 数据结构及算法实战】系列 013:Java队列07——双端队列Deque
    双端队列(Deque),顾名思义是可以在队列的两端插入和移除元素的特殊队列。Java提供了java.util.Deque<E>接口以提供对双端队列的支持。该接口是JavaCollectionsFramework的一......
  • 【Java数据结构及算法实战】系列008:Java队列02——阻塞队列BlockingQueue
    阻塞队列(BlockingQueue)是一种支持额外操作的队列,这两个附加的操作是:l  在队列为空时,获取元素的线程会等待队列变为非空。l  当队列满时,存储元素的线程会等待队列可用。J......