2

嗨，我正在解决段树的问题，但是我无法对段树的查询功能进行一点修改。

实际上我想要的是我的查询函数应该返回索引 Qa 和 Qb 之间的 (int)(TotalArrayLength/3) th 最大元素。

我编写的查询函数返回 index[1-based] a_begin 和 a_end 之间的最大元素。

但我想返回 index[1-based] a_begin 和 a_end 之间的 (int)(TotalArrayLength/3)th 最大元素。

    int query(int Nodenumber,int t_begin,int t_end,int a_begin,int a_end)
    {
        if (t_begin>=a_begin && t_end<=a_end)
            return Tree[Nodenumber];
        else
        {
            int mid=((t_begin+t_end)/2);
            int res = -1;

            if (mid>=a_begin && t_begin<=a_end)
                res = max(res,query(2*Nodenumber,t_begin,mid,a_begin,a_end));

            if (t_end>=a_begin && mid+1<=a_end)
                res = max(res,query(2*Nodenumber+1,mid+1,t_end,a_begin,a_end));

            return res;
        }
    }

注意进行查询，我将查询函数称为查询（1,0，N-1，QA，QB）。

我还实现了以下伪代码来编写上面的查询函数，

那么我应该如何修改以在 index[1-based] a_begin 和 a_end 之间找到 (int)(TotalArrayLength/3)th 最大元素。

基本上，我要解决的问题是：

最初，数组包含 0 个或更多元素。随机一些数据将被插入到数组的末尾，并且在任何时候都要做一个查询，返回 TotalArraySize/3 th Max Elements in Array build 到目前为止。

另外，我是否为此目的选择了正确的数据结构。

非常感谢。

4

1 回答 1

0

我的第一个是：

您需要使用 K 大小的排序列表作为每个 query() 调用的返回值。如果查询完全位于中点的左侧或右侧，则返回该结果。如果查询跨越中点，则在每个子节点返回时合并它们的结果。一旦你回到根，然后你返回结果排序列表中的第 k 个元素。

方法签名（在 Java 中）将是：

List<Integer> query(int Nodenumber,int t_begin,int t_end,int a_begin,int a_end)

最大堆数据结构可以完成相同的工作。只需从索引之间的项目构建最大堆并弹出头部 k 次。

段树将擅长多个查询，其中堆在整体内存和对数据的单个查询方面会更好。

于 2012-07-01T19:49:15.930 回答