2

こんにちは、セグメント ツリーの問題を解決していましたが、セグメント ツリーのクエリ関数を少し変更することはできません。

実際に私が欲しいのは、クエリ関数がインデックス 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 を返すクエリがいつでも実行されます。

また、目的に適したデータ構造を選択しましたか。

どうもありがとう。

4

1 に答える 1

0

私の最初のことは次のとおりです。

各 query() 呼び出しの戻り値として、K サイズのソート済みリストを使用する必要があります。クエリが中間点の左または右に完全にある場合は、その結果を返します。クエリが中間点にまたがっている場合は、返されたときに各子の結果をマージします。ルートに戻ったら、結果のソートされたリストで 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 に答える