Segment tree を書く (2)

競プロ

前回の続きです。 今回はセグ木で必要になる配列の長さの話をします。

前提

前回の実装では

  • 長さは 2 の冪に切り上げ

としていました。完全二分木になるので見通しが良くなりますね。 このとき、最悪で*1長さ 4(N-1) の配列が必要になります（ \exists k \in \mathbf{N}\ \mathrm{s.t.}\ N=2^k+1 の場合）。

しかし、実は N が 2 の冪ではない場合でもセグ木で確保する配列の長さは 2N で十分なことが知られています。

どうやるか

  1. 前回の実装例で n を 2 の冪に切り上げた値を len に代入している部分を削除する
  2. len = n; を書く
  3. おわり
// 9 行目
-        for(len = 1; len < n; len <<= 1);
+        len = n;

N が 2 冪でなくとも 2 冪を仮定した場合と同じコードでうまく動いてくれます。嬉しいですね。

verify

問題は前回と同じです。

問題

提出コード れたと言える。算術符号の符号化には文字の出現頻度（出現回数）の計算と、その文字までの累積確率が必要である。そのため、区間和を効率的に計算可能なデータ構造の開発が必要であった。

フェニック木を使うことで、部分和を O ( log ⁡ n ) {\displaystyle O(\log n)} {\displaystyle O(\log n)} 回の演算で計算することを可能とした。また、最初の要素からの和である部分和 だけでなく、任意の区間の和である 区間和 も同様に O ( log ⁡ n ) {\displaystyle O(\log n)} {\displaystyle O(\log n)} で計算可能とした。

通ってますね。

どうして

あとで加筆します。ゆるして

方針

添字 N から 2N-1 に 0 番目から N-1 番目を割り当てる。このとき、上の方にどの区間にも対応付かない（＝何を入れても壊れない）やつが出ることに注意して動作を追うと分かる。

*1: N は十分大きいと思っている