嗨,我正在解决段树的问题,但是我无法对段树的查询功能进行一点修改。
实际上我想要的是我的查询函数应该返回索引 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 到目前为止。
另外,我是否为此目的选择了正确的数据结构。
非常感谢。