配列の区間 (範囲) に対するクエリを効率的に処理するためのデータ構造。特に、区間の最小値・最大値・和などを求める場合に適している。

RMQ(Range Maximum Queries)

データを動的に更新したり、区間の最小値・最大値・合計を求めるのに適している。

例題: 競技プログラミングの鉄則 演習問題集 A58

A58 - RMQ

必要な処理は以下の３つ。

1. セグメントツリーを作ること
2. セグメントツリーを更新すること
3. セグメントツリーの区間を読み取っていくこと

順に見ていく。

セグメントツリーを作る

セグメントツリーは2kで表現する必要があるため、N < 2k となるkを求めたうえで2kの箱を作る。そのうえでセグメントごとの最大値を保存する箱が必要になるため、2k*2個の配列を用意する。

以下のようなイメージになる。

ここで数列Aの各要素の位置posは、0=8, 1=9, 2=10...となるため、数列Aのインデックス=i+2^kで求めることができる。初期値は0のため、最初は以下のようになる。

セグメントツリーを更新する

更新対象の位置は上記の通り、数列Aのインデックス=i+2kで求まる。また木構造のためセルcの一つ上のセルposはu//2で計算できる。

以上からposが1になるまで2で割ることで一つ上のせるの位置を計算しつづけ、2つの最大値を取れば良い。A3を16に更新した結果は以下のようになる。

• 更新対象の位置 = 3+8-1 = 10
• 一つ上 = 10//2 = 5
• 10と11を比較したいので、102, 102+1の要素のmaxを取る
• さらに一つ上 = 5//2 = 2
• 4と5を比較したいので、22, 22+1の要素のmaxを取る
• さらに一つ上 = 2//2 = 1
• 2と3を比較したいので、12, 12+1の要素のmaxを取る
• 1になったのでおしまい

以上から更新にかかる計算量は一つ上の木へ行くたび1/2になるので、段数と同じくO(logN)となる。

セグメントツリーの探索

例えばi=3,4,5の区間の最大値を求めたいとする。インデックスがややこしいので、最下段に番号を振った。

このときどこまで見れば最大値を答えられるかというと、5と12のセルを見つければよい。

そのためには、すべての区間を半分ずつ狭めていきながら、答えとなる区間がその狭まった範囲に存在しているか？を左右に分かれて探索し続けていけば良い。

そして、最終的に見つかった左右の最大値をmaxすることで答えが決まる。

つまり答えとなる区間の最小値と最大値(=今回は3と5=以降はl,rとする)の範囲の中に探索する区間が収まるか？を探せばよいのだ。

まず最初は0-8の区間を見ることになる。

残念ながら0-8は3-5に収まらないので答えにはなれない。なので左右に探索を進める。左から順に見ていくとこうなる。

ここで左半分の探索が終わり、16がひとつの候補になる。同じく右を見ていくと、12の部分が3-5に収まるので、答えになりうる。以上で16と0という候補が見つかり、答えは16となる。

実装

以上がセグメントツリーのアルゴリズムだ。実装については、公式解答に譲ることにする。

github.com