第 5 章 準動的区間最小 ( 最大 ) 値問い合わせ 30
5.3 提案手法
Fischerの提案アルゴリズムで用いる動的LCAのアルゴリズムは実装が容易ではない．
本節では，同等の計算量で動作する，実装が容易な準動的RMQのアルゴリズムを提案 する．提案アルゴリズムは2次元最小ヒープとBenderとFarach-Colton [1]が提案した
±1RMQ問題に対するアルゴリズムを用いる．
定義 12 (±1RMQ問題 [1]). すべての1≤ i <|A|に対してA[i+ 1]−A[i] = ±1を満た すような表Aと，A中の位置1 ≤ i1 ≤i2 ≤ |A|に対して，±1RMQ問題はrmqA(i1, i2) を求める．
Hを表Aの2次元最小ヒープとする．E′とD′をそれぞれHを根から行きがけ順 (pre-order)に辿って得られるオイラー巡回路(Euler tour)上の節点とその深さ，sをHの最 右路上の辺の数とし，EとDをそれぞれE′[:|E′| −s]，D′[:|D′| −s]とする．また，そ れぞれの1≤i≤ |A|に対してB[i] = min{1≤j ≤ |E|:E[j] =i}とする．このとき，明 らかに次の命題が成り立つ．
命題 3. すべての1≤i <|D|に対して，D[i+ 1]−D[i] =±1が成り立つ．
命題 4. |D|=|E|=O(|A|)，|B|=|A|が成り立つ．
表A中の位置1≤i1 < i2 ≤ |A|に対して，lca(i1, i2)をH中の節点i1, i2のLCAとす る．命題3より，表Dに対して±1RMQが適用できる．BenderとFarach-Colton [1]が示 したLCAとRMQの関係を2次元最小ヒープHに適用することにより次の補題を得る．
補題 16 ([1]). 表A中の位置1 ≤ i1 ≤ i2 ≤ |A|に対して，u = lca(i1, i2)とすると，
u=E[rmqD(B[i1], B[i2])]が成り立つ．
また，LCAとRMQの関係について次の観察が成り立つ．
観察 3. 表A中の位置1≤i1 ≤i2 ≤ |A|に対して，u=lca(i1, i2)とする．uの子かつi2 の先祖である節点をvとすると，rmqが最右の最小値となる位置を返すことに注意して v =E[rmqD(B[i1], B[i2]) + 1]が成り立つ．
補題 12, 16と観察 3より，次式を得る．
rmqA(i1, i2) =
E[rmqD(B[i1], B[i2])] （E[rmqD(B[i1], B[i2])] =i1のとき）
E[rmqD(B[i1], B[i2]) + 1] （E[rmqD(B[i1], B[i2])]̸=i1のとき）. (5.1)
図 5.1に準動的RMQの計算例を示す．表Aの末尾に要素を追加したとき，定義より 表B,E, Dは末尾に要素が追加されるように更新される．そのため，表A, B,E, Dへの 要素の追加操作は命題 4より，事前に追加要素数が与えられるかもしくは動的配列 [12]
で保持すれば償却定数時間で行える．よって，式 (5.1)より，表Dの±1RMQが準動的 に，すなわち表の末尾に要素を追加する操作に償却定数時間で対応する最悪定数問い合 わせ時間のアルゴリズムを示せばよい．
補題 17. 表の末尾もしくは先頭どちらか一方のみに要素を追加する操作を許した準動的
±1RMQ問題は，線形領域で償却定数追加時間と最悪定数問い合わせ時間で解ける．
補題 17の証明は後述する．補題 17と式(5.1)より，次の補題を得る．
補題 18. 準動的RMQ問題は，線形領域で償却定数追加時間と最悪定数問い合わせ時間 で解ける．
5.4 ± 1RMQ の既存手法
補題 17を証明するために，BenderとFarach-Colton [1]が提案した±1RMQの既存手 法を応用する．本節では彼らの既存手法を詳述する．彼らのアルゴリズムではRMQのア ルゴリズムであるスパーステーブル（sparse table）アルゴリズムと表引き（table lookup）
アルゴリズムを組み合わせる．
5.4.1 スパーステーブルアルゴリズム
スパーステーブルアルゴリズムは，長さnの表Aに対してO(nlogn)時間の前処理を 行い，RMQに対して定数問い合わせ時間を実現するアルゴリズムである．それぞれの 0≤j ≤ ⌊log2n⌋, 1 ≤i≤n−2j+ 1に対して，STA[i, j] =rmqA(i,2j)とすると，次の漸 化式が成り立つ．
STA[i, j] =
i （j = 0のとき）
STA[i, j−1] （A[STA[i, j−1]]< A[STA[i+ 2j−1, j−1]]のとき）
STA[i+ 2j−1, j−1] （それ以外のとき）．
(5.2) 式 (5.2)に基づいた動的計画法により，表STAはO(nlogn)時間で計算することができ る．表A中の位置1 ≤i1 ≤i2 ≤ nに対してrmqA(i1, i2)は，l =⌊log2(i2−i1+ 1)⌋とす ると次式より定数時間で計算できる．
rmqA(i1, i2) =
STA[i1, l] （A[STA[i1, l]]< A[STA[i2−2l+ 1, l]]のとき）
STA[i2−2l+ 1, l] （A[STA[i1, l]]≥A[STA[i2−2l+ 1, l]]のとき）．
(5.3)
5.4.2 表引きアルゴリズム
表引きアルゴリズムは，長さnの表Aに対してO(n2)時間の前処理を行い，RMQに 対して定数問い合わせ時間を実現するアルゴリズムである．それぞれの1≤i≤j ≤nに 対してTLA[i, j] =rmqA(i, j)とすると次の漸化式が成り立つ．
TLA[i, j] =
i （i=jのとき）
TLA[i, j−1] （A[TLA[i, j−1]]< A[j]のとき）
j （それ以外のとき）．
(5.4)
式 (5.4)に基づいた動的計画法により，表TLはO(n2)時間で計算することができる．
0 1 2 3
1 1 2 4 4
2 2 2 4 4
3 3 4 4 4
4 4 4 4 4
5 5 5 7 7
6 6 7 7
7 7 7 7
8 8 9 10 9 9 10 10 10 10 10 11 11 11 12 12
図 5.2: A = (3,1,4,1,5,9,2,6,5,3,5,8)に対する表STAの例．A[12] = 8に対応する要 素を灰色で示す．
1 2 3 4 5
1 1 2 3 3 3
2 2 3 3 3
3 3 3 3
4 4 4
5 5
図 5.3: A= (2,1,0,1,2)に対する表TLAの例．
5.4.3 ±1RMQアルゴリズム
すべての1 ≤ i < nに対してA[i+ 1]−A[i] =±1を満たすような長さnの表Aに対 して，O(n)時間の前処理を行い±1RMQに対して定数問い合わせ時間を実現するアルゴ リズムを示す．表Aを重なり無く長さs = ⌈(log2n)/2⌉のブロックに分割する．簡単化 のために，n >1かつnがsで割り切れると仮定する．nがsで割り切れない場合，Aの 末尾に±1の制約を満たすようにnがsで割り切れるまでダミーデータを追加すればよ い．このとき，Aには高々⌈(log2n)/2⌉ −1個しか要素が追加されないため計算量には影 響を与えない．mをブロック数，すなわちm =n/s=n/⌈(log2n)/2⌉とする．表Aのi 番目のブロックA⟨s(i−1) + 1,+s⟩をAiと表記する．それぞれの1 ≤ i≤ mに対して，
A′[i]をAiの最小値とする．表A′に対するスパーステーブルSTA′ は，|A′|=mなので，
O(mlogm) = O(n)時間で構築できる．
表Aの各ブロックに対して表引きアルゴリズムを用いる．すなわち，それぞれの1≤ i ≤ mに対して表TLAiを計算する．ただし，素朴に式 (5.4)に基づきTLAiを計算する と合計O(n2)時間必要なので，表Aが±1の制約を満たしていることに注目した工夫を する．それぞれの1≤i≤mに対してAiの正規化ブロックNiを，それぞれの1≤j ≤s に対してNi[j] =Ai[j]−Ai[1]と定義する．表Aのすべてのブロックの正規化ブロックの 集合をN ={Ni : 1≤ i≤m}とする．なお，集合の定義より|N| ≤ mが成り立つこと に注意する．ここで次の命題が成り立つ．
命題 5 ([1]). 長さsの表T1,T2に対して，それぞれの1≤i≤sと定数cに対してT2[i] = T1[i] +cが成り立っているならば，任意の1≤i≤j ≤sに対してrmqT2(i, j) =rmqT1(i, j) が成り立つ．
命題 6 ([1]). |N|=O(√
n)が成り立つ．
証明. 表Aは±1の制約を満たし，ブロックの大きさがs=⌈(log2n)/2⌉であることに注 目すれば，正規化ブロックは2⌈(log2n)/2⌉−1 =O(√
n)通り存在する． 2 すべてのN ∈N に対してTLN を計算するとO(√
n×((log2n)/2)2) =O(n)時間かか る．計算済みのTLN と命題 5を用いることにより，すべての1≤ i≤ mに対してTLAi を線形時間で計算することができる．
すべてのTLAiと，表A′に対するスパーステーブルSTA′が計算されたとすると，rmqA(i1, i2) は高々A′に対するスパーステーブルによるRMQを1回とi1とi2が所属するブロックの 表引きアルゴリズムによるRMQを2回計算することにより，定数時間で計算できる．