概要

セグメント木を図示する方法を、有名なものを中心にマイナーバリエーションをいくつかご紹介します。ほとんど大喜利のような記事ですが暖かい目でぜひです。

以下、特に断りが無い限りすべて $n = 11$ の場合の図です。

方法１　$2$ 冪の枠に当てはめる。

節点 $i$ を第 $⌊\lg(i)⌋$（bit length）段に置くという方法ですね。$n$ が $2$ 冪でないときにはかなり見づらいと思うのでおすすめはしませんし、最近ではあまり使われていないのではないかと思われます。

またこれは独自性というほどではないかもですけれども、すべての節点（セル）のアスペクト比を 1:2 に固定すると正方形に収まりますし、そうめんみたいに細いセルが生まれなくて好きです。（もちろんサイズ自体が大きくなるわけではないため、そうめんの代わりに米粒やメロンになるだけですけれども）

方法２　葉を一列に並べる

節点 $i$ を、下から数えて第 $⌊\lg((2n - 1)/i)⌋$ 段に置く方法ですね。これが一番人気で実用的だと思います。方法１の図の右半分（濃い赤色の部分）の縮尺を半分にして、左側にくっつけたものと見ることができますね。方法１と違ってやや横長になりますから、そこも親しみやすいポイントかもでしょうかね。

方法３　全部一列に並べる

意外とこれも頭にあります。

方法４　縮尺 $2$ 倍で無限に並べる

方法１の図を次のように縮尺を $2$ 倍ずつ変えて左右に無限にくっつけると、「$2$ 冪の壁」（方法１の図同士の境界）を跨ぐように 方法２の図が現れます。またすべての段が方法３で見た一直線と一致していますね。つまりこの方法はこれまでの方法をすべて悪魔合体した方法でると思えるわけです。

さらにいわゆる「異常値の入る」セル（ここでは $1, 2, 5$ です）は「$n$ の壁」（方法2の図同士の境界）にあらわれているのがわかります。この図を見ると「異常値が入る」セルである必要十分条件が $n$ の bit prefix であって $n$ よりも pop count が真に小さいもこと、言い換えると $n = 2 ^ p (2k + 1)$ と表したときの $k, ⌊k/2⌋, ⌊k/4⌋, \dots, 1$ のどれかであることと同値であることも納得しやすいと思います。

この図自体を手で書くことはない（必要になときに方法２の周りに書き足していけば良い）のですが、念頭にさえ置いておくと、

「境界を跨いだ」節点（$\bar{a} _ 1, \bar{a} _ 2, \bar{a} _ 5$）に何が入っているのか
そもそも「境界を跨いだ」節点（$\bar{a} _ 1, \bar{a} _ 2, \bar{a} _ 5$）である条件はんなのか
二分探索の実装を誤ったりなどして範囲を超えて「行き過ぎてしまった」（$\bar{a} _ 1, \bar{a} _ 2, \bar{a} _ 5$ などを算入してしまった）場合にどういう値になるのか

などセグメント木の細かい理解につながると思われます。

特にセグメント木の「本体」の左右にくっついている「境界を跨いだ」節点は、なんとなく頭の中で思い描いていると良いと思います。