java实现数据结构09（线段树详解代码之自定义线段树）

刺骨的言语ヽ痛彻心扉 2023-06-23 11:55 19阅读 0赞

## 融合接口 ##

/** * @description: 两个元素融合为一个元素 * @author: liangrui * @create: 2019-12-18 17:38 **/
    public interface Merger<E> { 
    
        /** * 融合方法，由用户自定义具体实现 * @param e1 * @param e2 * @return */
        E merge(E e1,E e2);
    }

## 自定义线段树 ##

import java.util.Arrays;
    
    /** * @description: 自定义线段树 * @author: liangrui * @create: 2019-12-18 17:12 **/
    public class SegmentTree<E> { 
        private E[] tree;
        private E[] data;
        private Merger<E> merger;
    
        /** * 有参构造函数 * @param arr */
        public SegmentTree(E[] arr,Merger<E> merger){ 
            data=(E[])new Object[arr.length];
            for (int i = 0; i < arr.length; i++) { 
                data[i]=arr[i];
            }
            //因为tree中会有许多为null的孩子，所以需要的空间要*4
            tree=(E[])new Object[4*arr.length];
            this.merger=merger;
    
            //构建线段树
            buildSegmentTree(0,0,data.length-1);
        }
    
        private void buildSegmentTree(int treeIndex, int l, int r) { 
            if (l==r){ 
                tree[treeIndex]=data[l];
                return;
            }
    
            int leftTreeIndex=leftChildIndex(treeIndex);
            int rightTreeIndex=rightChildIndex(treeIndex);
    
            //这里不使用int mid=(l+r)/2是因为(l+r)可能会溢出超过int最大值
            int mid=l+(r-l)/2;
    
            buildSegmentTree(leftTreeIndex,l,mid);
            buildSegmentTree(rightTreeIndex,mid+1,r);
    
            tree[treeIndex]=merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]);
        }
    
        /** * 获取元素个数 * @return */
        public int getSize(){ 
            return data.length;
        }
    
        /** * 获取指定下标元素 * @param index * @return */
        public E get(int index){ 
            if (index<0||index>=data.length){ 
                throw new IllegalArgumentException("Illegal index.");
            }
            return data[index];
        }
    
        /** * 获取左孩子下标 * @param index * @return */
        private int leftChildIndex(int index){ 
            return index*2+1;
        }
    
        /** * 获取右孩子下标 * @param index * @return */
        private int rightChildIndex(int index){ 
            return index*2+2;
        }
    
        /** * 查询指定区间 * @param queryL * @param queryR * @return */
        public E query(int queryL,int queryR){ 
            if (queryL<0||queryL>=data.length||queryR<0||queryR>=data.length||queryL>queryR){ 
                throw new IllegalArgumentException("Illegal Index");
            }
            return query(0,0,data.length-1,queryL,queryR);
        }
    
        /** * 递归查询 * @param treeIndex * @param l * @param r * @param queryL * @param queryR * @return */
        private E query(int treeIndex, int l, int r, int queryL, int queryR) { 
            if (l==queryL&&r==queryR){ 
                return tree[treeIndex];
            }
    
            int leftChildIndex=leftChildIndex(treeIndex);
            int rightChildIndex=rightChildIndex(treeIndex);
    
            int mid=l+(r-l)/2;
    
            if (queryL>=mid+1){ 
                return query(rightChildIndex,mid+1,r,queryL,queryR);
            }else if (queryR<=mid){ 
                return query(leftChildIndex,l,mid,queryL,queryR);
            }
    
            E leftResult=query(leftChildIndex,l,mid,queryL,mid);
            E rightResult=query(rightChildIndex,mid+1,r,mid+1,queryR);
    
            return merger.merge(leftResult,rightResult);
        }
    
        /** * 修改 * @param index * @param e */
        public void set(int index,E e){ 
            if (index<0||index>=data.length){ 
                throw new IllegalArgumentException("Illegal index.");
            }
            data[index]=e;
            set(0,0,data.length-1,index,e);
        }
    
        private void set(int treeIndex, int l, int r, int index, E e) { 
            if (l==r){ 
                tree[treeIndex]=e;
                return;
            }
    
            int leftChildIndex=leftChildIndex(treeIndex);
            int rightChildIndex=rightChildIndex(treeIndex);
    
            int mid=l+(r-l)/2;
    
            if (index>=mid+1){ 
                set(rightChildIndex,mid+1,r,index,e);
            }else { 
                set(leftChildIndex,l,mid,index,e);
            }
    
            tree[treeIndex]=merger.merge(tree[leftChildIndex],tree[rightChildIndex]);
        }
    
    
        @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();
    
        }
    }

## main测试 ##

public class Main { 
    
        public static void main(String[] args) { 
           Integer[] nums={ -2,0,3,-5,2,-1};
           //父=左孩子+右孩子
           SegmentTree<Integer> segmentTree=new SegmentTree<>(nums, (e1,e2) -> e1+e2);
    
            System.out.println("tree:"+segmentTree);
    
            //区间查询
            System.out.println(segmentTree.query(0,2));
            System.out.println(segmentTree.query(0,5));
            System.out.println(segmentTree.query(2,4));
    
            segmentTree.set(0,2);
            System.out.println("tree:"+segmentTree);
    
            //区间查询
            System.out.println(segmentTree.query(0,2));
            System.out.println(segmentTree.query(0,5));
            System.out.println(segmentTree.query(2,4));
        }
    }

## 测试结果： ##

> tree:\[-3,1,-4,-2,3,-3,-1,-2,0,null,null,-5,2,null,null,null,null,null,null,null,null,null,null,null\]  
> 1  
> \-3  
> 0  
> tree:\[1,5,-4,2,3,-3,-1,2,0,null,null,-5,2,null,null,null,null,null,null,null,null,null,null,null\]  
> 5  
> 1  
> 0