完全二分木への添字付けであってセグメント木ではないものを考える
この記事を読むのに必要な知識: セグメント木に対する基本的な理解。モノイドや作用素モノイドを用いた抽象化に関する理解もあればよい
導入
セグメント木の上にモノイドや作用素モノイドが乗る 1 ことはよく知られている。 しかしこれらはセグメント木の用途のひとつの説明に過ぎない。 これらは赤黒木や treap などの任意の二分木の上でも同様に成り立つ一般的な性質であり、それがただセグメント木にも適用できるというだけである。 となると「セグメント木の上にモノイドや作用素モノイドが乗る」という事実は、セグメント木についてはほとんど何も説明していないと言えるだろう。 それどころかこの事実は「木で列を管理する一般的なテク」 2 として「セグメント木」とは明確に区別されるべきものである。
ではその具体的な用途ではなく木それ自体に注目したとき、セグメント木はどのように説明されるべきだろうか。 これはたとえば「セグメント木とは、完全二分木の頂点を操作しやすい形で添字付ける方法、あるいはそれを使って配列上に表現された木のことである」のようなものであるべきだろう。
このような説明からは自然に「完全二分木の頂点を操作しやすい形で添字付ける方法は、セグメント木の他にも存在するか」や「セグメント木と異なる方法が存在するならば、それらはセグメント木とはどのように異なるか」という問いが生まれる。 セグメント木を理解する (そして可能ならば改良する) ためには、これらの問いに答えることは必要だろう。 以下ではこれを行う。
可能な方法の列挙
セグメント木 (BFS 順)
まずセグメント木について確認しよう。 高さ \(N = 3\) のセグメント木は次のようなものとなる。 添字を \(1\) から始めたのはその性質の表記が綺麗になるからである。
その性質を列挙すると以下のようになる。これらはとても扱いやすいと言える。
- 根の添字は \(1\)
- 添字 \(i\) の頂点の親の添字は \(\mathrm{floor}(i / 2)\)
- 添字 \(i\) の頂点の左の子の添字は \(2i\)
- 添字 \(i\) の頂点の右の子の添字は \(2i + 1\)
- 左から \(j \ge 0\) 番目の葉の添字は \(2^N + j\)
- 添字 \(i\) の頂点が葉であるかの判定は \(i \ge 2^N\)
- 添字 \(i\) の頂点の深さ \(d = \mathrm{floor}(\log_2(i))\)
これは (次以降で見る対案と比較して) BFS 順の添字付けであると呼ぶことができる。
対案1: DFS 行きがけ順
まず最も単純なものとして素直に思い付くのがこれだろう。
その性質は以下のようになる。添字が与えられたのみではその親の添字を求めることすら難しいなど、とても扱いにくい。
- 根の添字は \(1\)
- 添字 \(i\) の頂点の左の子の添字は \(i + 1\)
- 添字 \(i\) の頂点の右の子の添字は、葉からの高さを \(h\) として \(i + 2^{h + 1}\)
- 右から \(j \ge 0\) 番目の葉の添字は \(2^{N + 1} - 1 - j - \mathrm{popcount}(j)\)。ただし \(\mathrm{popcount}(j)\) は \(j\) の \(2\) 進数展開に含まれる \(1\) の数を表す
対案2: DFS 通りがけ順 (binary indexed tree)
DFS 行きがけ順を確認したならば、次に確認すべきはこれだろう。 これはそう悪くなく、実は binary indexed tree が採用しているものとほとんど一致する。
性質は以下のようになる。操作は少し面倒だが、他と比べれば十分に扱える範囲だと言える。
- 根の添字は \(2^N\)
- 添字 \(i\) の頂点の親の添字は、葉からの高さを \(h \ge 0\) として \(i\) の下から \(h\) bit 目を \(0\) にして下から \(h + 1\) bit 目を \(1\) にした数
- 添字 \(i\) の頂点の左の子の添字は、葉からの高さを \(h\) として \(2i - 2^{h - 1}\)
- 添字 \(i\) の頂点の右の子の添字は、葉からの高さを \(h\) として \(2i + 2^{h - 1}\)
- 左から \(j \ge 0\) 番目の葉の添字は \(2i + 1\)
- 添字 \(i\) の頂点が葉であるかの判定は \(i \equiv 1 \pmod{2}\)
- 添字 \(i\) の頂点の高さは \(\mathrm{ctz}(i)\)。ただし \(\mathrm{ctz}(i)\) は \(i\) の \(2\) 進数展開の下位側からいくつ \(0\) が連続するかを表す
対案3: DFS 帰りがけ順
これは DFS 行きがけ順とほぼ同様で、とても扱いにくい。
- 根の添字は \(2^{N + 1} - 2\)
- 添字 \(i\) の頂点の左の子の添字は、葉からの高さを \(h\) として \(i - 2^{h + 1}\)
- 添字 \(i\) の頂点の右の子の添字は \(i + 1\)
- 左から \(j \ge 0\) 番目の葉の添字は \(j + \mathrm{popcount}(j) + 1\) (https://oeis.org/A101925)
対案4: BFS 逆順
性質は以下のようになる。 添字の操作は直接には扱いにくい。 セグメント木の添字との対応が明らかであるので、この対応を経由してであれば扱うことはできる。
- 根の添字は \(2^{N + 1} - 1\)
- 左から \(j \ge 0\) 番目の葉の添字は \(i + 1\)
- 添字 \(i\) の頂点が葉であるかの判定は \(i \le 2^N\)
木が拡張される方向について
ところで、根の添字が \(0\) となる方式とそうでない方式があった。 これを観察すると、この違いは高さ \(N\) の木と高さ \(N + 1\) の木の関係に影響することが分かる。
- BFS 順: 高さ \(N + 1\) の木は高さ \(N\) の木に葉を付け加えたようなものである
- DFS 行きがけ順: 特に関係は存在しない
- DFS 通りがけ順: 高さ \(N + 1\) の木は高さ \(N\) の木を根の左の子として持つ
- DFS 帰りがけ順: 高さ \(N + 1\) の木は高さ \(N\) の木を根の左の子として持つ
- BFS 逆順: 特に関係は存在しない
DFS 通りがけ順の木が持つような関係は木の高さの拡張を容易にする。 つまり、何らか要素の列を葉に乗せて管理しているとき、配列の拡張のみで (すでに格納されているデータの移動なしに) 木の高さを変更できる。 これは面白い性質ではあるが、しかし計算量の改善には役立たない。 かなり特殊な設定においての定数倍高速化あるいは永続データ構造の実現に使える程度だろう。
binary indexed tree
まとめ
「木で列を管理する一般的なテク」と区別される意味での「セグメント木」について観察した。 セグメント木はその他の完全二分木への添字付けの方法より格段に扱いやすいことが確認できた。 加えて、セグメント木と BFS 順の添字付けとの、 binary indexed tree と DFS 通り掛け順の添字付けとの関係が発見できた。 ただしこれらの知見がなにか具体的な問題を解くために直接的に役に立つことはない。