私が解決しなければならない問題は、クエリを刺すという 1D 問題の 4D バージョンです。数値が属する間隔を見つけます。セグメント ツリーの多次元実装を探しています。理想的には、それは Java であり、フラクショナル カスケードを使用します。
kd ツリー (k-NN 検索) と範囲ツリー (バウンディング ボックスが与えられ、その中のすべての点を見つける) には多次元実装が存在しますが、セグメント ツリーについては 1D 実装しか見つかりませんでした。
同じ問題に対処するために、同様の空間/時間の複雑さを持つ他のデータ構造を検討していただければ幸いです。
私のコメントを拡張すると、私が念頭に置いているバイナリ空間分割アルゴリズムはこれです。
スタブクエリはルートから始まり、現在のノードに割り当てられたすべての間隔をチェックし、適切な子に降りて繰り返します。小さなサブツリーの場合はブルート フォースに切り替える価値があるかもしれません。
半平面 x=t によって刺される間隔が多すぎる場合は、(a) 下半空間と交差する間隔と (b) 上半空間と交差する間隔で再帰を試みることができます。これにより間隔が複製されるため、スペース要件はもはや線形ではなく、おそらく、細分化が非生産的であることが判明した間隔のコレクションでブルート フォースに切り替える必要があります。