3-3/

README

3-3: さまざまなデータ構造を操ろう

---

セグメント木

セグメント木の概念

• 区間を扱うのが得意なデータ構造
• 完全二分木で、各節点は区間を管理する
  • 根は区間全体を管理する
  • 各節点の子は親の区間を二等分した2つの区間の一方を管理する
• n個の要素があるとき、区間に対する操作を O(logn) で行えることが特徴
• 各節点に「どのようなデータをもたせるか」によって、いろいろな機能をもつセグメント木を作ることができる

自分用メモ

• O(logn) なのは木の高さ分だけの処理で済むから

セグメント木によるRMQの仕組み

次の2つの処理を O(logn) で実現することを目指す。

• s, t が与えられたとき、 [s, t] のAの要素の最小値を求める
• i, x が与えられたとき、 A[i] の値を x に変更する

配列による実装

実装に関して、要点を整理したのでまとめておく。 RMQ以外の場合はその都度学んでいく。

完全二分木に対する操作にも馴染むことになるため、よく理解しておきたい。

• 要素数nが2べきの数である場合、セグ木全体のノード数は 2n-1 になるため、配列長もそれだけ必要になる。
  • 各木の高さにおけるノード数は 2^h なので、 h ビット目のみが立っているビット列と考えられる。これらをすべて足すと、当然そうなる。
• セグ木上の k 番目の要素に該当する葉ノードへの移動方法は k += (n-1)
  • これは、葉ノード以外の根を含めた中間ノードの数が n/2 + n/4 + n/8 + ... + n/n = n-1 であるため！
• セグ木上の k 番目のノードから親ノードへの移動は (k-1)/2 でよい。
  • 確かめれば正しいことはわかるものの、理由を説明するのは難しい（自分はわからなかった）ので、とりあえずそういうものだと思っておく。
• セグ木上の k 番目のノードの2つの子ノードへの移動は、左の子ノードは 2k+1 右の子ノードは 2k+2 でよい。
  • 親と同じくそういうものだと思っておく。
  • 忘れてしまったら、高さ3ぐらいの小さなセグ木を書いてみて、実際に0-basedで番号を割り振ってみて調べてもいい気がする。
• query関数で登場する区間はすべて半開区間である点に注意！
  • 大本の最小値を知りたいクエリ区間は [a, b) だし、 k 番目の左端と右端によって示される区間も [l, r) のような形になる。
  • ここらへんは間違えやすそうなところなので、経験を積んで自分なりにベストプラクティスを見つけたい。

これらが整理できていると、RMQのupdateに関しては自然と理解できる。 queryの方も関数のシグニチャ（方針）がわかれば自然とわかるはず。

RMQセグメント木のverify

AOJのこの問題を素直にやるのがいいと思う。

RSQセグメント木のverify

RSQ: Range Sum Query

基本はRMQと同じ。

AOJのこの問題を素直にやるのがいいと思う。

※後述のBITのverifyにも勿論よい。

tsutajさんのブログ記事

このブログ記事は自分も考えたような内容が丁寧にトレースされておりとてもよかった。

Crane（蟻本のセグ木の例題）

正直、セグ木の例題として例示するには難しすぎると思う。。 与えられた解法とコードを理解するだけで精一杯、というところ。

とりあえず、解法やコードを理解するための注意点としては、以下のようなところ。

• 左子ノードを地面の基準として右子ノードの「回転角度」を取得する。
  • それを用いた回転の一次変換を右子ノードのベクトルに作用させて左子ノードのベクトルに加算する。
    • 解法のベースはこんなところ。一次変換を思い出せないと辛い。
• 入力で与えられる A[i] は、その角度に「セット」するものであることに注意。
  • セグ木の入力としてはどれくらい変化するかの「差分」が必要であるため、それは別途計算する仕組みが必要。

---

BIT(Binary Indexed Tree)

列 A[n] があったとき、以下の操作が高速（O(logN)）で可能。

• A[1:i] (1-based)を計算
  • 累積和の要領で、任意区間の和が高速に計算できる
    • 仮に sum(0) と呼び出しても 0 が返ってくるだけなので、区間和計算時に変に番兵を仕込ませたり例外処理的なことは考えなくて良い（はず）
• A[i] += x

ポイント

• i の最も下位の1のビットは i & (-i) で取得できる
  • これは「区間の長さ」を意味している
    • e.g. 0100 は区間の長さが4
  • 区間の長さを自身に足したり、自身から引いたりすることで、目的のノードの番号が得られる
• 値の更新（add）は、初期位置から自身の長さを「加算」することで、 += x する場所に次々と経由できる
  • add は長さの「加算」と覚えられる！
• 和の計算（sum）は、初期位置から自身の長さを「減算」することで、 s += bit[i] と答えに積み上げて行けば良い

例題: バブルソートの交換回数

普通にバブルソートをすると O(N^2) かかってしまうため、BITを使って交換回数を効率的に求める。

初見でちょっと悩んだため、考察過程をメモしておく。

• 求めるスワップ回数は i < j, A[i] > A[j] となるような (i, j) の組の個数。
  • このような組の数を「反転数（転倒数）」という。
  • 各 j(0, 1, ..., n-1) について、このような i を数えるアプローチを取る。
• 前から数字を見ていくことになるが、見たあとに、 その数値のBIT配列をインクリメントする。
  • この操作を前提とすることによって、 sum(i) は「これまで見てきた中で（＝j 番目の直前までで） i 以下の数の登場回数」を返すことになる。
  • これを j から引いたものが、注目中の j に対する反転数のペアの個数となる。

例題: A Simple Problem with Integers

遅延セグ木の例題（？）

加算クエリが範囲に対して与えられるため、普通にセグ木を使う方法ではだめ。

verifyはこちらで。

セグ木による解法

蟻本のものは遅延「評価」は行っていないような気がする。。

この書き方で他の応用が効くのかは不明。

遅延評価セグメントツリーについて

こちらについてもtsutajさんのブログ記事がとてもわかり易い。

蟻本の実装よりも汎用的でわかりやすそうなので、いっそ蟻本のほうは見ないほうがいいかも。。？

BITによる解法

このスライドがとても親切。

BIT解法だけでなく、蟻本の遅延評価セグメントツリーの解説の理解の助けにもなる（と思う）。

「累積和の増加分」のグラフとの結びつけは、 BITのSumメソッド bit.Sum(i) が初項からの累積和であることを強烈に認識する のがコツ。 （BITにもっと習熟すると、幾分自然に感じられるようになるかもしれない。）

肝心の解法自体は、グラフや数式を見つめると理解できるが、自分ひとりで導出できる気がしない。

累積和の関数の次数に関して一般化できるらしいが、初学の段階では応用できる気がしないので省略する。

おまけ: 区間更新＆区間最小値（RMQ and RUQ）

verify用問題

おまけ: 遅延評価セグメントツリーの計算量（独自解釈）

tsutajさんのブログ記事における実装について、 「こんなに eval メソッドをコールしちゃったら計算量大きくなりすぎるんじゃない？」と思ったので、自己解決の内容をメモ。

eval メソッドは子へと伝搬するが、一度に孫以下まで伝搬することはない点に注意！

add にしろ getSum にしろ、毎回自ノードについて eval がコールされるが、 クエリ範囲がノードの担当範囲を完全に包含している場合は、それ以上は eval はコールされない。

なぜなら、その時点での更新された値配列さえ手に入れば、それよりも下の階層の値配列は興味がないから。 （必要な部分の値配列が正しければ、それより下は見る必要がない。）

このように考えると、クエリ全体に対する計算量はちゃんと小さくなるように思える。 （ただし解析はそれほど簡単ではなさそう。）

---

バケット法と平方分割

バケット法（bucket method）

列や平面をバケットなる単位に分割して、 バケットごとにデータを管理する ことにより、効率的に計算や操作を行う手法。

平方分割（sqrt decomposition）

N個の要素からなる列を、 sqrt(N) 程度ごとのバケットにまとめて管理する手法の俗称。

※バケット法の特殊系。

特徴

• セグ木と同様に、どのようにデータをもたせるかによって、様々な機能を実現できる。
• RMQについてはかなり愚直に考えれば良いことがわかる。
  • 計算量も、更新・クエリともに O(sqrt(N)) というのも感じ取れる。

利点

• 実装がセグ木よりもシンプルなので、実行時間に余裕があれば、平方分割を選択するのもあり。
• セグ木では効率的に実現できないような機能でも、平方分割では実現できる場合がある。

例題: K-th Number

要点だけまとめておく。

最重要事項（典型思考）

数 x が k 番目ということは、以下の2つが成り立つこと。

• その区間に x 以下の数は k 個以上存在
• その区間に x 未満の数は k 個未満存在

数式にすると以下のような感じ。

(x未満) < k <= (x以下) <=> l < k <= r を満たすとき、 x は l+1 番目から r 番目の数値（※ x が複数存在する場合もケア）。

※当然、 r >= l+1 である。

解法

区間に存在する x 以下の数値の個数を効率的に数えることができれば、 x について二分探索を行って、 k 番目の数を求めることができる。

※平方分割でもセグ木でも、どちらの解法でもこのベースは同じ！

平方分割による解法

気持ちはRMQと似ている。 クエリがバケットをすべて含む場合は、ソート済みのバケットの中で二分探索。 はみ出した部分は愚直に見る。

全体の配列をソートして、その中から x を二分探索すればよい（条件は「自身以下の数の個数が k 個以上かどうか」）

[l, r] の範囲にない数値も探索対象になるが、正しく動作するのか？→ちゃんと動作することを以下で示す。

1. x が区間外だが、正解の数値の場合（＝ [l, r] にも存在する場合）

• x が答えとして選ばれて、何も問題はない

1. x が区間外だが、正解の数値より大きい場合

• より小さ、かつ条件を満たす正解の数値を求めて、二分探索が続く

1. x が区間が以下つ、正解の数値より小さい場合

• 正解の数値は条件を満たすギリギリの値（＝最小の値）であることに留意
• よってこのような x は条件を満たさない
• よってより大きい方向に x を動かして、二分探索が続く

以上の1, 2, 3の場合より、正しく動作することがわかる。

セグ木による解法

ノードに「ソート済み列」をもたせる点が面白いが、やはりベースは同じ。 再帰的に二分探索を行う。

以下は自分の課題。

• logN の見積もりを簡単にできるようにしておきたい。
• AOJのverify問題を探したい。

参考資料

しょらーさんのブログ記事がかなり良さそう。

とりあえず写経してみる。