最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(8.3)创建线段树

    创建线段树

    我们已经了解了什么是线段树,并且想把线段树看成满的二叉树,这种情况下用数组就可以存储线段树。

    如果要考虑的区间有n个元素,数组开4*n的空间就可以承载整个线段树了,下面我们就具体的对这个4*n个空间里到底要存储什么才能构建线段树相应的逻辑进行介绍。

    比如我们处理求和这个线段树,也就是说我们线段树的目的是为了查询区间中的元素和的操作,相应的每个节点存储的就是一个区间中所有元素的和。

    如图:根节点存储的就是10个元素的和,左孩子存储的就是前五个元素的和,右孩子存储的是后五个元素的和,依次划分到叶子节点。

    代码演示

    完整的线段树创建代码

    public class SegmentTree {
    
        private E[] tree;
        private E[] data;
        private Merger merger;
    
        public SegmentTree(E[] arr, Merger merger){
    
            this.merger = merger;
    
            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, arr.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) / 2;
            int mid = l + (r - l) / 2;
            buildSegmentTree(leftTreeIndex, l, mid);
            buildSegmentTree(rightTreeIndex, mid + 1, r);
    
            tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
        }
    
        public int getSize(){
            return data.length;
        }
    
        public E get(int index){
            if(index < 0 || index >= data.length)
                throw new IllegalArgumentException("Index is illegal.");
            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();
        }
    }
    

    程序第35行如果我们这样写是报错的,错误的原因在于我们这个类型E不一定定义了加法,所以我们不能保证加法一定是合法的。

    对于我们之前的分析,如果这部分代码只写成加法代码,整个线段树的作用其实就局限住了,我们不希望我们线段树只能处理加法或者求区间的最大最小值,我们还是希望能自由的组合逻辑。

    tree[treeIndex] = tree[leftTreeIndex]+tree[rightTreeIndex];
    

    这种情况下我们可以创建一个新的接口Merger(融合器)

    public interface Merger {
        E merge(E a, E b);
    }
    

    下面在main函数中测试一下

    public class Main {
    
        public static void main(String[] args) {
    
            Integer[] nums = {-2, 0, 3, -5, 2, -1};
    //        SegmentTree segTree = new SegmentTree<>(nums,
    //                new Merger() {
    //                    @Override
    //                    public Integer merge(Integer a, Integer b) {
    //                        return a + b;
    //                    }
    //                });
    
            SegmentTree segTree = new SegmentTree<>(nums,
                    (a, b) -> a + b);
            System.out.println(segTree);
        }
    }
    

    运行程序,输出结果,仔细思考一下为什么打印出这个结构

    源码下载

    [dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

    导航目录

    [dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(8.3)创建线段树

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 134会员总数(位)
    • 3731资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 340稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级