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

    线段树中的区间查询

    比如我们要在这个线段树中查询[2,5]这个区间相应的信息,相当于是查询这个区间的和。从根节点开始出发

    在根节点包含了[0,7]区间的信息,显然我们要查询的是其子集,所以我们要向下去左右子树查找。

    由于我们要查询的[2,5]分别落在了左右子树,所以我们需要分别查询,如图

    接下来继续往下查询,如图所示,我们要查询的最终结果只需要获取图中两节点结果之和就行了。

    这个过程中我们不需要从头遍历,只需要在线段树上从根节点向下寻找相应的子区间,再把相应的子区间综合起来。

    代码演示

    // 返回区间[queryL, queryR]的值
    public E query(int queryL, int queryR){
    
        if(queryL < 0 || queryL >= data.length ||
                queryR < 0 || queryR >= data.length || queryL > queryR)
            throw new IllegalArgumentException("Index is illegal.");
    
        return query(0, 0, data.length - 1, queryL, queryR);
    }
    
    // 在以treeIndex为根的线段树中[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;
        // treeIndex的节点分为[l...mid]和[mid+1...r]两部分
    
        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, mid);
        E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);
        return merger.merge(leftResult, rightResult);
    }
    

    main函数中测试一下

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

    运行程序,输出结果

    源码下载

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

    导航目录

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

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

    常见问题FAQ

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

    参与讨论

    • 159会员总数(位)
    • 3736资源总数(个)
    • 1本周发布(个)
    • 0 今日发布(个)
    • 405稳定运行(天)

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

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