7K12 blog

猫でも分かるアルゴリズム解説

遅延評価セグメント木ライブラリ

f:id:tkr987:20200201134655p:plain

http://9871225.blog.fc2.com/blog-entry-307.html

 ライブラリの94行目にLazyUpdate(v);を追加してバグ修正した。

会津大学のテストケースで動作確認した。

 

質問「配列N個の要素に値を追加するのに計算量いくつかかりますか」普通は O(N)しかないやろ~と思うところだが、驚くべきことに遅延評価セグメント木で実装すると O(log{N})で処理が終わってしまう。遅延セグ木は「配列8個に値xを加算する」のは「木構造1番上のノードに値xを加算して8倍するのと同じ」という発想が基本になる。配列半分の要素に値xを加算するなら木構造の上から2番目のノードに値xを加算する。これを考えた人は天才かと思った。木構造にすることで O(log{N})に計算量を落とす工夫はアルゴリズムでは頻繁に見られる。

 

遅延評価セグ木を実装しようとしたとき気づいた、初心者が知ってると役に立つことについて。

  1. 遅延評価の更新は何回やっても構わない。
  2. 最低限必要な遅延評価更新のタイミングは2つあって「ノードに訪れたとき」と「遅延評価値を弄ったとき」

どちらもセグ木を実装するのに必須な知識だと思うが、意外とぐぐっても出てこなかったりするので気づくのに無限の時間かかった (´Д`) 遅延評価の更新は少なければ少ないほど良いが、じつは無駄に更新したとしても定数倍が遅くなるだけで別に答えには影響しなかったりする。

 

なお、遅延評価セグ木は定数倍が結構重いというのは有名だが、自分のライブラリは相当定数倍が重い感じする。定数倍改善の工夫があれば教えてほしい。