1. 序章

スパーステーブルは、範囲最小クエリ問題などの範囲クエリ問題に時間内に答えることができるデータ構造です。

このチュートリアルでは、さまざまな範囲クエリの問題でスパーステーブルとそのアプリケーションを構築する方法を示します。

2. 問題の説明

範囲最小クエリ(RMQ)の問題から始めましょう。 数値の配列とwhereの形式のクエリのリストが与えられた場合、位置と両端の間の配列内の最小数で各クエリに回答します。 あれは、 。

3. ブルートフォアソリューション

最初に、範囲最小クエリ問題の2つのブルートフォースソリューションを検討します。 最初のものについては、スペースに間に合うようにクエリに答えることができます。 2つ目は、時間内にクエリに答えることができますが、スペースがいくらかあります。

3.1. 追加のスペースなしで各クエリに回答する

範囲の最小クエリごとに、場所との間のすべての配列要素を調べて、最小値を見つけることができます。

各クエリの要素にアクセスする可能性があるため、このアルゴリズムの合計時間計算量は、です。ここで、はクエリの数です。 このアルゴリズムのスペースの複雑さはです。

3.2. 前処理を使用した一定時間クエリ

上記のアルゴリズムの時間計算量は、クエリの数によって異なります。 大きい場合、すなわち のスケール以上では、に余分な値を掛けるため、実行時間は遅くなります。

最初のアルゴリズムでは、各クエリに答える時間が必要です。 各クエリに対してより高速な回答を得るために、可能なすべての範囲のクエリ結果を格納することにより、入力配列を前処理できます。

このアルゴリズムでは、最初に単一の要素を含む範囲の回答を作成します。 次に、動的計画法アプローチを使用して、再帰式に基づいてより広い範囲の回答を計算します。

考えられるすべての範囲の回答を含むテーブルができたら、範囲の最小クエリごとにテーブルを検索できます。

前処理には時間がかかります。 質問ごとに、時間内に答えることができます。 したがって、全体的な時間計算量はです。 スペースが複雑になるのは、前処理の結果を保存するために余分なスペースが必要になるためです。

前処理により、各クエリに時間内に回答できます。 したがって、クエリの数が多い場合、このアルゴリズムは最初のブルートフォースソリューションよりも効率的です。

4. スパーステーブル 解決

強引な前処理アルゴリズムでは、時間内に可能なすべての範囲のテーブルを作成して、時間内に範囲最小クエリに回答できるようにします。 スパーステーブルデータ構造を使用して、範囲の最小クエリをより効率的に事前計算し、それでも一定のクエリ時間を達成できます。

4.1. スパーステーブルのアイデア

2の累乗の数値は、の形式の整数です。ここで、は非負の整数です。 2の累乗の数値の合計として、任意の正の整数を2進数で一意に表すことができます。 例えば、 。

配列の範囲の長さは、位置とそれを含む間の配列要素の総数であり、です。 2の累乗の範囲は、長さが2の累乗の数値である範囲です。

範囲のサブ範囲は、。 範囲の長さは正の整数であるため、範囲を2の累乗のサブ範囲の和集合として表すこともできます。 例えば、 。 全範囲、、の長さは。です。 3つのサブ範囲の長さは、それぞれ、、、およびです。

一般に、任意の範囲は、長さが2の累乗の数値であるサブ範囲のセットで分割できます。

スパーステーブルの主なアイデアは、最初に2の累乗の範囲でクエリに対するすべての回答を計算することです。 の範囲クエリに答えるとき、最初にそれを2の累乗のサブ範囲に分割できます。 次に、事前に計算された回答を検索し、それらを組み合わせて最終的な回答にします。

4.2. スパーステーブルの漸化式

開始位置()ごとに、最大で2の累乗のサブ範囲があります:、、、、…、ここで、を作成する最大の数です。 したがって、2次元配列を使用してスパーステーブルを表すことができます。

各スパーステーブルエントリ(および)は、クエリ結果を範囲に格納します。 たとえば、クエリ結果を範囲に格納します。

の場合、長さ1の範囲のクエリ結果を保存します。

の場合、長さ範囲のクエリ結果を保存します。 以前に計算されたより小さな範囲から値を計算できます。

たとえば、範囲に対する回答をテーブルエントリに格納します。 その値は、範囲との答えから得られます。 それらのスパーステーブルエントリは、それぞれとです。

4.3. スパーステーブルの構築

強引なアプローチの前処理と同様に、動的計画法を使用してスパーステーブルを作成できます。

このアルゴリズムでは、最初にすべての長さ範囲のクエリ結果を計算します。 次に、ネストされたforループを使用して、範囲の長さを増やしてクエリ結果を計算します。 範囲の長さが長いクエリ結果は、範囲の長さが短いクエリ結果からのものです。

計算中に、2の累乗の値を計算する必要があります。 C ++やJavaなどの一部のプログラミング言語では、のようなビット演算でこれを実現できます。 それ以外の場合は、2の累乗の値をすべて事前に計算し、必要なときに値を検索できます。

スパーステーブル構造の時間とスペースの両方の複雑さはです。

4.4. 範囲最小クエリのスパーステーブル

範囲の最小数を計算する場合、範囲内の値を1回処理するか2回処理するかは関係ありません。 したがって、範囲を複数の重複しない範囲に分割する代わりに、同じ2の累乗の長さを持つ2つの重複する範囲のみに範囲を分割することもできます。

たとえば、範囲を3つの重複しない範囲、、、に分割できます。 次に、範囲の最小クエリは、サブ範囲の3つのクエリの最小値です。

また、同じ長さの2つの重複する範囲とに分割することもできます。 最小関数の場合、最終結果に影響を与えることなく、同じ数を複数回カウントできます。 したがって、も持つことができます。

範囲の範囲最小クエリの場合、最初にその最大2乗の長さを見つけることができます。 たとえば、範囲の2の累乗の最大長はです。 次に、2つの範囲とのスパーステーブルを検索します。 最後に、範囲に対する答えは、上記の2つの範囲クエリ結果の最小値です。

範囲の2の累乗の最大長を見つけるには、対数値を計算する必要があります。 高速処理のために、すべての対数値を事前に計算できます。

スパーステーブルの構築には時間がかかります。 質問ごとに、時間内に答えることができます。 したがって、全体的な時間計算量はです。 スペースの複雑さはスパーステーブル用です。

5. スパーステーブルアプリケーション

スパーステーブルを使用して、他のタイプの範囲クエリを解決することもできます。 たとえば、同じロジックを使用して、時間内に範囲クエリの最大数を見つけることができます。

一般に、数値のリストで結果値を計算する関数を定義できます。 たとえば、範囲最小クエリの最小値を計算します。

次の2つのプロパティがある場合、スパーステーブルを使用して、関数に基づいて範囲クエリに時間内に回答できます。

  • 連想的です:。 このプロパティを使用すると、範囲全体をサブ範囲に分割し、それらのサブ範囲に適用できます。
  • オーバーラップフレンドリーです:。 このプロパティを使用すると、2つの重複するサブ範囲を使用して、範囲全体の結果を計算できます。

たとえば、最大公約数(GCD)関数は。として結合します。 また、とのようにオーバーラップしやすいです。 したがって、同じロジックを使用して、2の累乗の範囲のGCD値を含むスパーステーブルを作成し、範囲のGCDクエリに時間内に応答できます。

6. スパーステーブルの制限

クエリ関数がオーバーラップフレンドリーでない場合、範囲クエリに時間内に答えることができません。 たとえば、sum関数は結合法則ですが、オーバーラップフレンドリーではありません。 範囲合計クエリに回答するには、範囲全体をいくつかの重複しないサブ範囲に分割する必要がありますが、これには時間がかかります。 ただし、より効率的な prefix sum アプローチを使用して、範囲合計クエリに答えることができます。

また、配列内のいずれかの要素が変更された場合、時間内にスパーステーブルを再計算する必要があります。 したがって、スパーステーブルは、不変配列の範囲クエリに適しています。 つまり、2つのクエリ間で配列データを変更することはできません。

7. 結論

この記事では、スパーステーブルを使用して範囲最小クエリの問題を解決する方法を示しました。 また、一般的な形式のスパーステーブルアプリケーションとスパーステーブルデータ構造の制限についても説明しました。