こんにちは、セグメント ツリーの問題を解決していましたが、セグメント ツリーのクエリ関数を少し変更することはできません。
実際に私が欲しいのは、クエリ関数がインデックス Qa と Qb の間の (int)(TotalArrayLength/3) 番目の最大要素を返すことです。
私が書いたクエリ関数は、index[1-based] a_begin と a_end の間の最大要素を返します。
しかし、インデックス[1ベース] a_beginとa_endの間の(int)(TotalArrayLength/3)番目の最大要素を返したいです。
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;
}
}
クエリを作成するには、クエリ関数を query(1,0,N-1,QA,QB) と呼びます。
また、上記のクエリ関数を記述するために、次の擬似コードを実装しました。
では、index[1-based] a_begin と a_end の間の (int)(TotalArrayLength/3)th Maximum 要素を見つけるにはどうすればよいでしょうか。
基本的に、私が解決している問題は次のとおりです。
最初は、配列には 0 個以上の要素が含まれています。ランダムに一部のデータが配列の最後に挿入され、TotalArraySize/3 th Max Elements in Array build を返すクエリがいつでも実行されます。
また、目的に適したデータ構造を選択しましたか。
どうもありがとう。