セグ木ってなんだろう...？（小学生）

こんにちは。
今回はセグ木について少しまとめようと思います。

最近トゥイッターでセグ木はもちろん、HL分解？や全方位木DP？という難単語が流行っているようです（顰蹙を買いそう...）。
全方位木DPはこないだのABCのFで出題されたことが発端ですが、、、

僕はこれらのデータ構造やアルゴリズムに興味があるので、トゥイッターで見かけるたびに調べたりしています。
しかし、これらの「使いどころ」を学ぶことはアルゴリズムのさらなる面白さを味わうために必要な気がしてきました。

ですが、実際僕が今までに解いた問題を見ると、これらのアルゴリズムが必要であった問題は非常に少ないです。
（全方位木DP...2問、セグ木...2問）

一方でアルゴリズムやデータ構造は種類がたくさんあるので、様々なアルゴリズムを使いこなすにはたくさん問題を解く必要がありそうです。

結局は問題を解くことになるのですが、僕としては「名前だけ知っているアルゴリズム・データ構造」があるのは何だか気持ち悪いです。
なので、これらのアルゴリズムを使ってできることくらいは整理しておきたいなと思った次第です。

◇セグ木って何？
まず、セグ木は区間を扱うのが得意なデータ構造のようです。
完全二分木で、根は区間全体を管理し、各節点の子は親の区間を二等分した2つの区間の一方を管理しています。（下図）

n個の要素があるとき、区間に対する操作をO(log n)で行えるそうです。

でも、区間に対する操作って何でしょうね？笑

◇セグ木で出来る事
セグ木で出来るのは、
・区間（または一点）の更新（これが可換で出来るかどうか、という問題もあるみたい）
・区間（または一点）取得
のようですね。
例えばRMQ(Range Minimum Query)という次のような問題
「数列A0, A1, ... , An-1があるとき、
①Aiの値をxに変更する
②As, ... , Atの最小値を求める」
セグ木ならば解けるようですね（①区間の更新　②区間の取得）。

◇セグ木にのるって言われているモノイドって何？
ぶっちゃけ、ここが一番書きたかったところです。

...続きはこれから書きます。待てない人は次の方々のブログ読んで欲しい。
びーとさん
beet-aizu.hatenablog.com

いたたこのたこつぼさん
ikatakos.com

うさぎ小屋さん
kimiyuki.net