宿題
O(logn*ログイン）。
kd-tree と range tree の 2 つの可能性を考えています。kd ツリーは、O(logn + k) の範囲内の要素を見つけることができるため、これに適しています (報告する必要がある k 要素の場合)。しかし、要素を報告する必要はありません。範囲内にある要素の数を計算する必要があるだけです。
範囲ツリーはその中で機能する可能性があります。各ノードに、それ自体よりも少ない数を保持するプロパティを設定できます。このようにして、O(logn) 回で特定の値よりも小さい要素の数を特定できます (2 つの境界に移動し、互いに小さいノードの数の差を見つけることによって)。ただし、これは (x,y) 次元の両方を持つデータ セットでは機能しないと思います。
私は正しい軌道に乗っていますか？
あなたが説明したのは、オンラインの2次元直交範囲カウント問題です。「オンライン」とは、データの前処理を行った後、クエリが次々と来ることを示します。「直交」は、範囲が軸に沿った長方形であることを示します。また、範囲レポートとは対照的に、範囲カウントは範囲内にあるアイテムの数のみをカウントします。
各ノードがその下のノードの総数を格納する kd ツリーは、最悪の場合、O(n^(1-1/k)) で範囲カウントを実行できます。これは、任意の直交範囲が kd ツリーの最大 O(n^(1-1/k)) 葉と交差できるためです。2 次元の場合、範囲カウント クエリを O(sqrt(n)) で実行できることを意味します。これは、必要な O((log(n))^2) よりも悪い結果です。
範囲ツリーは高次元で定義されているため、3 番目の段落は意味がありません。実際、これは高次元直交範囲カウント問題の教科書的な解法です。正確に O((log(n))^2) クエリ時間でカウントするオンライン 2 次元直交範囲を解決します。レンジ ツリーを独自に発見した数人の人物の 1 人であるジョン ルイス ベントレーによって書かれた、影響力のある 1 つの論文、「多次元の分割統治」を読むことをお勧めします。関連セクションは 2.1.2 です。
これは宿題の質問なので、詳細には触れませんが、おそらくすでに言いすぎました。