数据结构笔记总结(8.4)线段树中的区间查询

线段树中的区间查询

比如我们要在这个线段树中查询[2,5]这个区间相应的信息,相当于是查询这个区间的和。从根节点开始出发
数据结构笔记总结(8.4)线段树中的区间查询

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

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

数据结构笔记总结(8.4)线段树中的区间查询

接下来继续往下查询,如图所示,我们要查询的最终结果只需要获取图中两节点结果之和就行了。
数据结构笔记总结(8.4)线段树中的区间查询

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

代码演示

// 返回区间[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));
    }
}

运行程序,输出结果
数据结构笔记总结(8.4)线段树中的区间查询

源码下载

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

导航目录

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

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » 数据结构笔记总结(8.4)线段树中的区间查询
分享到:
赞(0)

评论抢沙发

评论前必须登录!