範囲クエリ（コンピュータサイエンス）

Gagieら^{[ 12 ]}は範囲をサポートするデータ構造を提案した。$\displaystyle \tau }$-大多数のクエリは ${\displaystyle m\times n}$配列${\displaystyle A}$各クエリについて${\displaystyle \operatorname {Q} =(\operatorname {R} ,\tau )}$このデータ構造では、しきい値${\displaystyle 0<\tau <1}$長方形の範囲${\displaystyle \operatorname {R} }$が指定され、その矩形範囲内の相対頻度が 以上のすべての要素の集合は、$\displaystyle \tau }$出力として返されます。このデータ構造は、動的なしきい値（クエリ時に指定）と前処理しきい値をサポートしています。${\displaystyle \alpha }$これは、それに基づいて構築されます。前処理中に、垂直および水平の間隔のセットが構築されます。${\displaystyle m\times n}$配列。垂直方向と水平方向の区間が組み合わさってブロックを形成します。各ブロックは、それ自身の9倍の大きさのスーパーブロックの一部です（ブロックの水平方向の区間の3倍と垂直方向の区間の3倍）。各ブロックに対して、候補のセット（${\displaystyle {\frac {9}{\alpha }}}$少なくとも の相対頻度を持つ要素で構成される要素が格納されます。${\displaystyle {\frac {\alpha }{9}}}$（前述の前処理閾値）はそれぞれのスーパーブロックに格納されます。これらの要素は、その頻度に応じて非増加順に格納され、相対頻度が少なくとも 1 以上の要素は、${\displaystyle \alpha }$ブロック内には、その候補セットが表示される必要があります。$\displaystyle \tau }$- 多数決クエリは、まずクエリブロック、つまり指定されたクエリ矩形に含まれる最大のブロックを見つけることによって回答されます。${\displaystyle O(1)}$時間。取得したクエリブロックの場合、最初の${\displaystyle {\frac {9}{\tau }}}$候補者は（検証されずに）返されます${\displaystyle O(1/\tau )}$時間がかかるため、このプロセスでは偽陽性が返される可能性があります。他の多くのデータ構造（後述）では、各候補を定数時間で検証し、したがって${\displaystyle O(1/\tau )}$クエリ時間中に誤検出を返さないケース。クエリブロックが小さい場合${\displaystyle 1/\alpha }$保存によって処理されます${\displaystyle \log \left({\frac {1}{\alpha }}\right)}$以下の形式のデータ構造の異なるインスタンス：

${\displaystyle \beta =2^{-i},\;\;i\in \left\{1,\dots ,\log \left({\frac {1}{\alpha }}\right)\right\}}$

どこ${\displaystyle \beta }$前処理のしきい値は${\displaystyle i}$番目のインスタンス。したがって、クエリブロックが小さい場合、${\displaystyle 1/\alpha }$の${\displaystyle \lceil \log(1/\tau )\rceil }$番目のインスタンスがクエリされます。前述のとおり、このデータ構造はクエリ時間を持っています。 ${\displaystyle O(1/\tau )}$そして必要とする${\displaystyle O\left(mn(H+1)\log ^{2}\left({\frac {1}{\alpha }}\right)\right)}$ハフマン符号化されたコピーを保存することで、スペースのビットを節約できます（${\displaystyle \log({\frac {1}{\alpha }})}$因子（ハフマン符号化も参照）。

Chanら^{[ 13 ]}は、 1次元配列が与えられた場合のデータ構造を提案した。${\displaystyle A}$部分範囲${\displaystyle R}$の${\displaystyle A}$（クエリ時に指定）およびしきい値$\displaystyle \tau }$（クエリ時に指定）すべてのリストを返すことができます$\displaystyle \tau }$-大多数が${\displaystyle O(1/\tau )}$時間のかかる${\displaystyle O(n\log n)}$空間の単語。このような質問に答えるために、Chan ら^{[ 13 ]}は、範囲内で上位 k個の最も頻繁に出現する項目を返すことができるデータ構造が存在することを指摘することから始めます。${\displaystyle O(k)}$時間のかかる${\displaystyle O(n)}$空間の単語。一次元配列の場合${\displaystyle A[0,..,n-1]}$片側トップk範囲クエリを次の形式とする${\displaystyle A[0..i]{\text{ for }}0\leq i\leq n-1}$範囲の最大範囲については${\displaystyle A[0..i]{\text{ から }}A[0..j]}$異なる要素の周波数${\displaystyle e}$で${\displaystyle A}$変更されず（そして等しい）${\displaystyle f}$水平線分が構築される。${\displaystyle x}$この線分の区間は${\displaystyle [i,j]}$そしてそれは${\displaystyle y}$-値は${\displaystyle f}$各要素を追加して${\displaystyle A}$前述のプロセスは、正確に1つの異なる要素の周波数を変化させ、${\displaystyle O(n)}$線分。さらに、垂直線の場合${\displaystyle x=i}$それと交差するすべての水平線分は、その頻度に従ってソートされます。各水平線分は、${\displaystyle x}$-間隔${\displaystyle [\ell ,r]}$正確に1つの異なる要素に対応する${\displaystyle e}$で${\displaystyle A}$、したがって${\displaystyle A[\ell ]=e}$上位k件のクエリには、垂直光線を照射することで回答できる。${\displaystyle x=i}$そして最初の報告${\displaystyle k}$それと交差する水平線分（上記で述べたように、これらの線分はすでに頻度に応じてソートされている）${\displaystyle O(k)}$時間。

Chan ら^{[ 13 ]}は、まず、各分岐ノードが片側範囲トップ k クエリ用に上述のデータ構造のコピーを 1 つ格納し、各リーフが要素を表す範囲ツリーを構築します。${\displaystyle A}$各ノードにおけるトップkデータ構造は、そのノードのサブツリーに存在する値に基づいて構築され、片側範囲トップkクエリに応答することを目的としています。1次元配列の場合、${\displaystyle A}$範囲ツリーは分割することによって構築できます${\displaystyle A}$2つの半分に分割し、両方の半分で再帰処理を行う。したがって、結果として得られる範囲ツリーの各ノードは範囲を表す。また、この範囲ツリーは${\displaystyle O(n\log n)}$空間の言葉は、${\displaystyle O(\log n)}$レベルと各レベル${\displaystyle \ell }$もっている${\displaystyle 2^{\ell }}$ノード。さらに、各レベルで${\displaystyle \ell }$範囲ツリーのすべてのノードの合計は${\displaystyle n}$要素${\displaystyle A}$サブツリーには、${\displaystyle O(\log n)}$レベルごとに、この範囲ツリーの空間計算量は${\displaystyle O(n\log n)}$。

この構造を使用すると、範囲${\displaystyle \tau }$- 多数決クエリ${\displaystyle A[i..j]}$の上${\displaystyle A[0..n-1]}$と${\displaystyle 0\leq i\leq j\leq n}$答えは以下のとおりです。まず、葉ノードの最小共通祖先（LCA）${\displaystyle i}$そして${\displaystyle j}$定数時間で見つかります。必要なデータ構造が存在することに注意してください。${\displaystyle O(n)}$LCAクエリに答えることができる空間の断片${\displaystyle O(1)}$時間。^{[ 14 ]}${\displaystyle z}$LCA を表す${\displaystyle i}$そして${\displaystyle j}$使用${\displaystyle z}$そして範囲の分解可能性に応じて${\displaystyle \tau }$-多数決クエリ（上記および^{[ 11 ]}で説明されているとおり）、両側範囲クエリ${\displaystyle A[i..j]}$2 つの片側範囲トップ k クエリに変換できます (${\displaystyle z}$に${\displaystyle i}$そして${\displaystyle j}$) これらの 2 つの片側範囲トップ k クエリはトップ (${\displaystyle 1/\tau }$それぞれの範囲で最も頻繁に出現する要素${\displaystyle O(1/\tau )}$時間。これらの頻繁に出現する要素は、${\displaystyle \tau }$-大多数が${\displaystyle A[i..j]}$そこには${\displaystyle O(1/\tau )}$候補の中には偽陽性である可能性のあるものもある。各候補は、線形空間データ構造（^{[ 15 ]}の補題3で説明されている） を使用して定数時間で評価され、${\displaystyle O(1)}$配列の特定のサブレンジが${\displaystyle A}$少なくとも${\displaystyle q}$特定の要素のインスタンス${\displaystyle e}$。

Gagie ら^{[ 16 ]}は、 2 つのノードが与えられた場合にクエリをサポートするデータ構造を提案した。${\displaystyle u}$そして${\displaystyle v}$ツリーでは、相対頻度がより大きい要素のリストを報告できます${\displaystyle \tau }$道中${\displaystyle u}$に${\displaystyle v}$より正式には、${\displaystyle T}$各ノードがサイズのアルファベットからのラベルを持つラベル付き木とする${\displaystyle \sigma }$。 させて${\displaystyle label(u)\in [1,\dots ,\sigma ]}$ノードのラベルを示す${\displaystyle u}$で${\displaystyle T}$。 させて${\displaystyle P_{uv}}$から一意のパスを表します${\displaystyle u}$に${\displaystyle v}$で${\displaystyle T}$中間ノードは訪問された順にリストされます。${\displaystyle T}$、および固定（前処理中に指定）しきい値${\displaystyle 0<\tau <1}$クエリ${\displaystyle Q(u,v)}$複数回出現するすべてのラベルのセットを返す必要があります ${\displaystyle \tau |P_{uv}|}$回数${\displaystyle P_{uv}}$。

このデータ構造を構築するには、まず${\displaystyle {O}(\tau n)}$ノードはマークされます。これは、少なくとも距離を持つノードをマークすることによって実行できます。${\displaystyle \lceil 1/\tau \rceil }$3つの高さのうち一番下から、深さがで割り切れる${\displaystyle \lceil 1/\tau \rceil }$この操作を行うと、各ノードとその最も近いマークされた祖先との間の距離が以下であることが観察されます。${\displaystyle 2\lceil 1/\tau \rceil }$マークされたノードの場合${\displaystyle x}$、${\displaystyle \log(depth(x))}$異なるシーケンス（ルートへの経路）${\displaystyle P_{i}(x)}$保存されます、

${\displaystyle P_{i}(x)=\left\langle \operatorname {label} (x),\operatorname {par} (x),\operatorname {par} ^{2}(x),\ldots ,\operatorname {par} ^{2^{i}}(x)\right\rangle }$

のために${\displaystyle 0\leq i\leq \log(depth(x))}$どこ${\displaystyle \operatorname {par} (x)}$ノードの直接の親のラベルを返します${\displaystyle x}$言い換えれば、マークされた各ノードについて、ルートに向かう長さが2のべき乗（ノード自体の長さ1を加えた値）のすべてのパスのセットが格納されます。さらに、各${\displaystyle P_{i}(x)}$、すべての多数派候補の集合${\displaystyle C_{i}(x)}$保存されます。より具体的には、${\displaystyle C_{i}(x)}$すべてのセットが含まれています${\displaystyle (\tau /2)}$-大多数が${\displaystyle P_{i}(x)}$または、より多く表示されるラベル${\displaystyle (\tau /2).(2^{i}+1)}$回数${\displaystyle P_{i}(x)}$候補の集合は容易にわかる。${\displaystyle C_{i}(x)}$最大で${\displaystyle 2/\tau }$それぞれに固有のラベル${\displaystyle i}$Gagie ら^{[ 16 ]}は、すべての集合が${\displaystyle \tau }$-マークされたノードからのパス上の過半数${\displaystyle x}$その祖先の1つへ${\displaystyle z}$一部に含まれる${\displaystyle C_{i}(x)}$（^{[ 16 ]}の補題2 ）長さは${\displaystyle P_{i}(x)}$に等しい${\displaystyle (2^{i}+1)}$したがって、${\displaystyle P_{i}(x)}$のために${\displaystyle 0\leq i\leq \log(depth(x))}$長さが${\displaystyle d_{xz}{\text{ and }}2d_{xz}}$どこ${\displaystyle d_{xz}}$は x と z の間の距離です。このような存在は、${\displaystyle P_{i}(x)}$は、${\displaystyle \tau }$-経路の大半から${\displaystyle x}$に${\displaystyle z}$でなければならない${\displaystyle (\tau /2)}$-大多数が${\displaystyle P_{i}(x)}$、したがって、${\displaystyle C_{i}(x)}$このデータ構造では、${\displaystyle O(n\log n)}$空間の言葉、なぜなら、建設段階で上述したように${\displaystyle O(\tau n)}$ノードにはマークが付けられ、マークされた各ノードに対していくつかの候補セットが格納されます。定義により、マークされた各ノードに対して、${\displaystyle O(\log n)}$このようなセットにはストアがあり、それぞれには${\displaystyle O(1/\tau )}$候補者。したがって、このデータ構造には${\displaystyle O(\log n\times (1/\tau )\times \tau n)=O(n\log n)}$空間の単語。各ノードに注意してください。${\displaystyle x}$また店舗も${\displaystyle count(x)}$これは、${\displaystyle label(x)}$道中${\displaystyle x}$根源へ${\displaystyle T}$これは、ノードごとに一定数の単語を追加するだけなので、空間計算量を増加させません。

2つのノード間の各クエリ${\displaystyle u}$そして${\displaystyle v}$範囲の分解可能性特性（上記で説明したとおり）を使用することで回答できます。${\displaystyle \tau }$-大多数のクエリとクエリパスを分割することによって${\displaystyle u}$そして${\displaystyle v}$4 つのサブパスに分割します。${\displaystyle z}$最小共通祖先である${\displaystyle u}$そして${\displaystyle v}$、 と${\displaystyle x}$そして${\displaystyle y}$最も近い標識された祖先である${\displaystyle u}$そして${\displaystyle v}$それぞれ。${\displaystyle u}$に${\displaystyle v}$は、以下のパスに分解されます。${\displaystyle u}$そして${\displaystyle v}$に${\displaystyle x}$そして${\displaystyle y}$それぞれ（これらのパスのサイズは以下より小さい）${\displaystyle 2\lceil 1/\tau \rceil }$定義上、これらはすべて候補とみなされる）から、${\displaystyle x}$そして${\displaystyle y}$に${\displaystyle z}$（適切なものを見つけることによって）${\displaystyle C_{i}(x)}$上記の説明に従い、すべてのラベルを候補として考慮します。境界ノードは、これらのサブパスがすべて互いに素であり、それらすべてから一連の${\displaystyle O(1/\tau )}$候補が導出される。これらの候補はそれぞれ、${\displaystyle labelanc(x,\ell )}$ノードの最下位祖先を返すクエリ${\displaystyle x}$ラベルが付いている${\displaystyle \ell }$そして${\displaystyle count(x)}$各ノードのフィールド。${\displaystyle w}$-ビットRAMとサイズのアルファベット${\displaystyle \sigma }$、${\displaystyle labelanc(x,\ell )}$質問には以下のように回答できます${\displaystyle O\left(\log \log _{w}\sigma \right)}$線形空間要件を持ちながら時間。^{[ 17 ]}したがって、${\displaystyle O(1/\tau )}$候補者${\displaystyle O\left(\log \log _{w}\sigma \right)}$時間の結果${\displaystyle O\left((1/\tau )\log \log _{w}\sigma \right)}$すべてのセットを返すための合計クエリ時間${\displaystyle \tau }$-大多数が${\displaystyle u}$に${\displaystyle v}$。