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