セグメントツリー入門

▲「お兄ちゃん、セグ木って何？」

■「セグ木は、セグメントツリー（セグメント木）の略だね」

▲「それって何ができるの？」

■「一番基本的なセグメントツリーだと、数列の区間に関するクエリ（質問）に O(log N) で答える、とかかな」

▲「区間に関する質問って？」

■「結合法則が成り立つ演算なんだけど、例えば Range Minimum Query (RMQ) と呼ばれる、 “指定区間の最小値を得る” クエリが有名だね」

▲「へー。確かに、最小値だと累積和みたいに引き算できないもんね」

■「あ、そうそう、セグメントツリーだと一点更新もできるよ」

▲「一点更新？」

■「数列の 2 番目を 5 に変える、みたいな処理のこと。この処理にも O(log N) かかる」

▲「1箇所の変更なのに O(1) じゃないの？」

■「区間クエリに O(log N) で答えるための準備がいるんだよ。この一点更新機能があるから、 “指定した区間の和を得る” というクエリにも使えるんだ」

▲「累積和だと、1箇所の値を変更したら、累積和の配列を作り直さないといけなくなるから O(N) かかって遅いってことだね」

■「そう。とりあえず今回は、区間min のセグメントツリーを作ってみようか」

▲「やってみよー！」

Range Query – Range Minimum Query (RMQ)

■「AOJのこの問題（↑）を題材にしよう」

▲「うげ、英語じゃん」

■「問題がシンプルだから大丈夫だよ。題意はこう」

数列 A={a_0, a_1, …, a_n} について、以下の処理を行え。

• find(s, t): a_s, a_{s+1}, …, a_t の最小値を出力する
• update(i, x): a_i の値を x に変える

始め、数列の全ての値は 2^31-1 で初期化されている。処理は q 回要求される。

1 ≦ n ≦ 100000, 1 ≦ q ≦ 100000

▲「区間クエリと一点更新ってやつだね」

■「もちろん、O(nq) では間に合わない。セグメントツリーを使うと、これが O(q log n) になる」

▲「セグメントツリーの解説をお願いします！」

■「ところで、classって分かる？」

▲「クラス？　わかんない」

■「そうか、じゃあ今回はグローバル変数でやろう。class 化についてはまた今度教えるよ」

セグメントツリーの基本構造

■「セグメントツリーは、完全二分木の形をしている」

▲「完全二分木？」

■「根ノードが 1 つあって、根から 2 つの子ノードが生えていて、それぞれの子ノードからも2つの子ノードが生えていて……という木構造のこと。どこかで子ノードが無いノード（葉ノード）が現れるけど、全ての葉ノードの深さが同じような二分木のことを完全二分木という。また、子が 1 つしか無いノードは存在しない。葉は子が 0 個で、葉以外は全て子が 2 個」

▲「うーん。よくわかんない」

■「図にするとこんな感じ。葉の数は必ず2の累乗になる」

▲「四角いのがノード（頂点）ってことだよね。一番上の横長なのが根ってこと？」

■「うん。ノードの左上に書いてある数は、そのノードの番号。こうやって番号を振ると、配列で扱えるから楽になる」

▲「実際は配列なんだけど、木のつもりで扱うってことね」

■「実際に扱う配列、今回でいう A={a_1, …, a_n} は、葉に入ることになる。上の図だと、3, 4, 5, 6 のノードが葉だね。上の図は、n=4 の場合の形ということになる」

▲「じゃあ葉以外のノードには何の値が入るの？」

■「葉以外には、そのノードが担当する範囲の最小値が入る」

▲「担当する範囲って？」

■「左右の子の担当範囲を合わせた区間が、そのノードの担当範囲になる。葉ノードの担当範囲は、自分の場所の添字だけになる」

▲「上の図でノード 1 の担当範囲は、ノード 3 の担当範囲 {0} とノード 4 の担当範囲 {1} を合わせた {0, 1} になるってこと？」

■「そう。ただ、担当範囲は半開区間で考えておくと便利。ノード1の担当範囲は [0, 2) 。ノード 0 の担当範囲は [0, 4) になる」

▲「じゃあ、例えば数列が  2, 1, 3, 0 だったら、こうなるの？」

■「そう。実際にはこういう、ただの配列になってるよ」

▲「実態は木じゃないんだね」

■「ここで大事なのが、あるノードの持つ値（担当範囲の最小値）は、左右の子ノードの持つ値の最小値になるということ。この性質があるから、あるノードの値を計算するときに、担当範囲全部を見る必要が無い。子の方から順に埋めていけば、子を見るだけで計算できる」

▲「ノード 0 の値を計算するために、数列の a[0] から a[3] まで見なくても、ノード 1 とノード 2 の値だけ見ればいいってことだね」

■「ちなみに、ノード i の子ノードの番号は、 i*2+1, i*2+2 で得られるよ」

▲「ほんとだ。これは便利だね」

■「同じように、ノード i の親ノードの番号は、 (i-1)/2（端数切り捨て）で得られる」

▲「端数切り捨てのおかげで右の子か左の子かを意識しなくていいんだね！」

■「また、図からも分かるように、配列の添字とセグメントツリーのノード番号はずれる。配列の a[i] にアクセスしたいときは、セグメントツリーのノード i+N-1 にアクセスする必要がある。N は葉の数（今回は4）だよ」

▲「ってことは、葉以外のノードは N-1 個あるってことだよね」

■「うん。N が 2 の累乗のとき、1+2+…+N/2 は N-1 になる」

▲「じゃあ、区間クエリと一点更新について教えて！」

一点更新クエリ

■「まず、update(i, x) について話そうかな」

▲「配列の a[i] の値を x に変更するんだよね」

■「うん。だから、まずは a[i] にあたる、ノード i+N-1 の値を x に変える。例えば、update(1, 4) が来たら、1+4-1=4 のノードの値を、4に変更する」

▲「でもこれだけだとダメだよね」

■「ここから途中のノードについて修正していくんだけど、ノード 2（0 が入っている）とかは、a[1] とは無関係だから修正しなくて大丈夫。修正すべきなのは、今変更した箇所の先祖たち」

▲「先祖っていうのは、親とその親と……っていうこと？」

■「そうそう。今回の場合は、ノード 1 とノード 0 だね。これらを、子の方から順に更新していく」

▲「最初は、今変更したノード 4 の親のノード 1 ？」

■「うん。ノード 1 の子であるノード 3, 4 の値の最小値をノード 1 の値とする。今回は 2 に変更されるね」

▲「つぎはその親のノード 0 だね！　でもこっちは更新されないね」

■「そうだね。子であるノード 1, 2 の最小値は 0 のままだ」

▲「一点更新はこれだけ？」

■「うん。これで終わり。セグメントツリーの値を保持する配列を value として、葉の数を N とすると、update のコードはこんな形になる。根ノードであるノード 0 まで修正したら処理を終える」

▲「簡単だね。次は区間クエリだね！」

区間最小値クエリ

■「find(s, t) について考えよう。これは区間 [s, t] の範囲の a[i] の最小値を得るクエリだけど、分かりやすくするために、[s, t) の半開区間の最小値を得るクエリを考えよう」

▲「[s, t) っていうのは、 s ≦ i < t の範囲ってことだよね」

■「そう。例として、さっきのセグメントツリーに対して [0, 3) の最小値を得るクエリを考えてみる」

▲「a[0], a[1], a[2] の最小値ってことだよね。今回は 2, 4, 3 だから、2 が答えだよね」

■「うん。これを高速に求める。こっちのクエリは、根ノードから処理していく」

▲「ふむふむ」

■「まず、根ノード 0 に『 [0, 3) の最小値は何ですか？』と聞く。でも、根ノードの担当範囲は [0, 4) なので、答えられない」

▲「なんで答えられないの？」

■「根ノードの担当範囲は、クエリの区間からはみ出している。だから、根ノードが持つ 0 という値が、[0,3) の範囲の値なのか、その外の a[3] の値なのか、ノード 0 は知らない」

▲「確かに、今回の最小値は 0 じゃないもんね」

■「だから、ノード 0 は左右の子ノードに質問する。『 [0, 3) の最小値は何ですか？』と」

▲「それぞれどう答えるの？」

■「まず、左のノード 1 を見よう。このノードの担当範囲は [0, 2) で、今回のクエリの範囲 [0, 3) に完全に含まれている。だから、『私の担当範囲での最小値は 2 ですよ』と答えられる」

▲「てことは、ノード 1 は子に質問する必要はないってこと？」

■「うん。ノード 3, 4 の値は見なくてもいい」

▲「じゃあ、右のノード 2 はどう答えるの？」

■「ノード2の担当範囲は、[2, 4) で、クエリの範囲 [0, 3) からはみ出ている。だから、さらに左右の子に『 [0, 3) の最小値は何ですか？』と聞くしか無い」

▲「じゃあ今度はこうなるんだね」

■「ノード5はどう答える？」

▲「えっと、ノード 5 の担当範囲は [2, 3) で、クエリの範囲 [0, 3) に完全に含まれてるから、自分が持ってる値を返せばいいんだよね。だから 3 かな」

■「そう。ノード 6 は、担当範囲が [3, 4) で、クエリの範囲 [0, 3) とはまったく被らない。こういうときは、単位元を返すのが良い」

▲「単位元？」

■「今回は min を扱うわけだけど、単位元というのはどんな x についても min(x, e) = x となるような値のこと。値を変えないということだね。足し算だと 0 、掛け算だと 1 になるんだけど、min の場合はどうなるか分かる？」

▲「どんな x についても min(x, e) = x になるような e ってことは、すっごく大きい数ってこと？　無限大か！」

■「そう。min の単位元は無限大。でも、今回は扱う数が 2^31-1 以下なので、2^31-1 がその条件を満たす」

▲「なるほど。じゃあ今回は ∞=2^31-1 だね」

■「数学的には変だけど、まあそんな感じだね」

▲「で、なんで単位元を返すの？」

■「ノード 6 は、今回の質問には無関係なノードだから、何も値を返したくない」

▲「うん」

■「だけど、値を返さないのは実装できないから、絶対に無視される値を返す」

▲「それが無限大なんだね。質問の返事はこうなるのかな」

■「そう。次は、2つの子から返事を受け取ったノード 2 の動きを考えよう」

▲「ノード 2 は、クエリ範囲と中途半端に重なってるから、子に委託したんだよね」

■「そう。そして、それぞれの子が『自分の担当範囲内での答えはこうですよ』と返した。それが 3 と ∞」

▲「でも、∞は無視されるために返したんだから、ノード 2 は 3 を返すんだよね？」

■「うん。ノード 2 は、クエリ範囲 [0, 3) と自分の担当範囲 [2, 4) の共通部分における最小値として、min(3, ∞) = 3 を返す」

▲「なるほど、クエリの範囲と担当範囲の共通部分について答えてるんだね」

■「最後に、左右の子から返事を受け取った根ノード 0 が質問に答える」

▲「これも同じように、左右の子からの返事 2, 3 の min を取るの？」

■「うん。クエリ区間を左右に分けて、左側の最小値が 2、右側の最小値が 3 になったのだから、全体の答えは min(2, 3) = 2 になる」

▲「この計算量が O(log N) になるの？」

■「うん。もっと葉が多い複雑な例を考えても、各高さで最大でも 4 つのノードにしかアクセスしないんだ。高さは log_2 N + 1 だから、アクセスするノードの数は O(log N) になる。1回のアクセスでは区間の被り判定と 2 つの値の min を計算するだけだから、O(1)。だから全体の計算量は O(log N) になる」

▲「じゃあ、あとは実装だけだね」

■「実装するときの注意点だけど、クエリ関数の引数は（クエリ区間の左、クエリ区間の右、注目するノード番号、注目するノードの担当範囲の左、注目するノードの担当範囲の右）とするとやりやすいよ」

▲「 5 つもあるの？　”注目するノードの担当範囲” って、ノード番号から分かるんじゃないの？」

■「もちろんノード番号と担当範囲は一対一に対応するけど、毎回計算して求めるのは面倒なんだ」

▲「ふーん。まあ楽に書けるならそうしよっか」

■「担当範囲が [l, r) であるようなノードの子ノードの担当範囲は、真ん中を m = (l+r)/2 として、[l, m) と [m, r) になる」

▲「[0, 4) のノードの子は [0, 2) と [2, 4) ってことだね」

■「うん。実装はこんなふうになる」

 

▲「∞ を INF って名前の定数にしてるんだね。範囲が被らなかったら INF を返すと」

■「そう。担当範囲 [l, r) がクエリ区間 [a, b) に完全に含まれるなら、自分が持っている値 value[k] を返す」

▲「どっちでも無かったら、子に投げるんだね」

■「そして子が返した値の min を取って返す」

▲「元々の質問の答えはどうなるの？」

■「[s, t) の最小値を得るには、query(s, t, 0, 0, N) を実行する。つまり、根ノード 0 （担当範囲は [0, N) ）に聞くということ」

▲「根ノードは数列全体を担当してるから、根ノードが返す値が全体の答えってことだね」

■「うん。じゃあ、もとの問題の答えを完成させよう」

セグメントツリーの初期化

▲「そういえば、数列のサイズ n が 2 の累乗じゃない場合はどうするの？」

■「その場合は、 n 以上の最小の 2 の累乗数を計算して、それを使う。余った部分は単位元で埋めておけばいい」

▲「こんかいの問題では、最初は数列が全部 2^31-1 だから、初期化はこう？」

■「そうだね。 2^31-1 はギリギリ int に収まるから、これで大丈夫。でも、(1<<31)-1 とコードに書くと、(1<<31) の時点でオーバーフローするから、注意が必要。面倒なら、全部 long long で扱って、 (1LL<<31)-1 とすればいい。1LL は long long 型の 1 を表す表現」

▲「あれ、でも (1<<31)-1 でもちゃんと 2147483647 になったよ。変な警告が出てるけど」

■「確かに、今回は負のオーバーフローの関係で辻褄が合っちゃうんだけど、良い方法では無いからね……」

▲「後はクエリに答えれば大丈夫だね。まず整数を受け取って、それが 0 なら update 、1 なら find だね」

■「そう。こうなるね」

 

▲「find で t+1 にしてるのは、半開区間とかの関係？」

■「うん。問題としては [s, t] の最小値を得るんだけど、query 関数は半開区間の最小値を返すから、クエリ区間を [s, t+1) としてクエリを実行する」

▲「コード全体はこうだね」

■「これで大丈夫なはず」

▲「このコードを提出して……　やった、Accepted！」

■「セグメントツリー始めの一歩は成功だね」

▲「これであたしもセグメントツリーマスターだね！」

■「AOJ には、セグメントツリーで区間和を計算する問題があるから、マスターになるならこっちも考えてみる必要があるよ。また、セグメントツリーを複数使うときのために class 化しておくべきだし、GCD みたいな、結合法則が成り立つけど逆元が無いような演算も使えるようになると良いかも。タコヤキオイシクナールは特殊なモノイドをセグ木に乗せる問題の代表だし、汎用性を高めるためにも抽象化をしておくと良いかも。Young Maids みたいな問題のために最小要素の添え字を返す形も作っておいた方が良いね。それから遅延伝播セグメントツリーというのもあって……」

▲「えー！　セグメントツリー、やること多すぎ！！」