直交範囲クエリのためのデータ構造

d次元空間における点の集合が与えられたとき、直交範囲クエリは指定されたd次元ボックス内の点の数を要求するものです。我々は、点の挿入と削除、および直交範囲クエリを実行するためのデータ構造とアルゴリズムを提示します。n操作の最悪の場合の時間計算量はO(n logd n)であり、空間使用量はO(n logd-1 n)です。（ここでのO記法はnに関するものであり、定数はdに依存することが許されます。）次に、直交範囲クエリの複雑性に関する決定木境界について簡単に論じます。d次元でn操作を処理するために、高さO(dn log n)の決定木が構築できることを示します（ここで、暗黙の定数はdやnに依存しません）。これは、標準の決定木モデルがこのような問題の複雑性を調査するための有用な方法を提供しないことを示唆しています。