範囲内の要素の数が他の範囲内にあるかどうかを調べるにはどうすればよいですか？

Question

私は何かを理解しようと少しの助けを必要とする：

順不同番号（15.000未満）の配列を考える - - 私はQは（Q < = 100000）の照会に答える必要があります Aから[I、J]は全てを有する大きな（又は等しい）Xよりもが、yより小さい

何範囲内の数字：以下のように変換する形式I、J、X、Yのtの数彼は5000より小さい配列を持っています。

私は印象を受けていますが、シーケンスの長さが長いためO（logN）のようなものが必要です。これは私にBIT（バイナリインデックス付きツリー - クエリのため） 2D BITは大きすぎるため、更新側であっても実行に多くの時間を要します。だから、私がここで見る唯一の解決策は、1D BITまたはSegment Treesでなければならないが、これらのデータ構造に基づいて解決策を立てる方法を理解することはできない。私は順序付けられた一連の数値の位置を保持しようとしましたが、与えられた形式のクエリに応答するBITの作り方を理解することはできません。

またアルゴリズムは、500msのような所定の制限に適合する必要があります。 編集1：前処理上のすべての操作のための500msのと答えるクエリ

EDIT 2：i、jはxよりも大きな要素を探すために、シーケンスAの最初と最後の要素の位置であると例： 位置1と4の間のように1、3、2、4、6、3とクエリ1、4、3、5（両端を含む）2があることがうY

EDIT 3よりも小さいです3より大きい（または等しい）要素（3および4）5より小さい

ありがとうございます！ P.S：英語が苦手な人には申し訳ありません！

Answer 1

BITで整理されたソート済みサブアレイの配列を作成することによって2D範囲のカウントを実装します。例えば、入力

[1, 3, 2, 4, 6, 3] 

にOracleは、スペース使用量はO（N Nログ）（できれば微）である

[[1] 
,[1, 3] 
,[2] 
,[1, 2, 3, 4] 
,[6] 
,[3, 6] 
]. 

あろう。建設には注意が必要な場合はO（N log N）時間か、そうでない場合はO（N log^2 N）時間がかかります（アプリケーションメチンクの理由はありません）。

シーケンスインデックスと値（これらのうちの4つは入力クエリに応答するために使用できる）で最大値を持つクエリに応答するには、配列のバイナリ検索を使用して最大インデックス最大値を超えない要素。クエリ時間はO（log^2 N）です。