Skip to content

Latest commit

 

History

History
179 lines (115 loc) · 6.81 KB

lazy_segtree.md

File metadata and controls

179 lines (115 loc) · 6.81 KB
Raw

LazySegtree

遅延評価セグメントツリーです。

この命名には批判があって、遅延伝播セグメントツリーの方が良いという意見も根強いです。

宗教戦争を避けるために、遅延セグ木と呼ぶのがいいかもしれません。

特異メソッド

new(v, e, id){ }

seg = LazySegtree.new(v, e, id)

第1引数は、IntegerまたはArrayです。

  • 第1引数がIntegerのnのとき、長さn・初期値eのセグメント木を作ります。
  • 第1引数が長さnのArrayのaのとき、aをもとにセグメント木を作ります。

第2引数eは、単位元です。ブロックで二項演算op(x, y)を定義することで、モノイドを定義する必要があります。

また、インスタンス作成後に、LazySegtree#set_mapping{ }とLazySegment#set_composition{ }を用い、適切にインスタンス変数にprocを設定する必要があります。

計算量 O(n)

new(v, op, e, mapping, composition, id)

new(v, e, id, op, mapping, composition)

seg = LazySegtree.new(v, op, e, mapping, compositon, id)
seg = LazySegtree.new(v, e, id, op, mapping, compositon)

前者は、本家ライブラリに合わせた引数の順番。
後者は、procを後ろにまとめた引数の順番で、これは非推奨。
内部で、第2引数がprocかどうかで、場合分けしています。

インスタンスメソッド

set(pos, x)

seg.set(pos, x)

a[pos]にxを代入します。

計算量 O(logn)

get(pos) -> 単位元eと同じクラス

seg.get(pos)

a[pos]を返します。

計算量 O(1)

prod(l, r) -> 単位元eと同じクラス

seg.prod(l, r)

op(a[l], ..., a[r - 1]) を返します。引数は半開区間です。l == rのとき、単位元eを返します。

制約 0 ≦ l ≦ r ≦ n

計算量 O(logn)

all_prod -> 単位元eと同じクラス

seg.all_prod

op(a[0], ..., a[n - 1]) を返します。サイズが0のときは、単位元eを返します。

計算量 O(1)

apply(pos, val)

apply(s, r, val)

seg.apply(pos, val)
seg.apply(l, r, val)
  1. a[p] = f(a[p])
  2. 半開区間i = l..rについてa[i] = f(a[i])

制約

  1. 0 ≦ pos < n
  2. 0 ≦ l ≦ r ≦ n

計算量 O(log n)

range_apply(l, r, val)

seg.range_apply(l, r, val)

3引数のapplyを呼んだときに、内部で呼ばれるメソッド。
直接、range_applyを呼ぶこともできる。

制約 0 ≦ l ≦ r ≦ n

計算量 O(log n)

max_right(l){ } -> Integer

LazySegtree上で、二分探索をします。

制約 0 ≦ l ≦ n

計算量 O(log n)

min_left(r){ } -> Integer

LazySegtree上で、二分探索をします。

制約 0 ≦ r ≦ n

計算量 O(log n)

Verified

問題のリンクです。Verified済みです。解答はテストコードをご参考ください。

以下の問題は、Rubyでは実行時間が厳しくTLEになりACできてないです。

下記は、ジャッジにだしてないが、サンプルに正解。max_right, min_leftを使う問題。

参考リンク

本家ライブラリとの違い

ceil_pow2ではなく、bit_length

本家C++ライブラリは独自定義のinternal::ceil_pow2関数を用いてますが、本ライブラリではRuby既存のメソッドInteger#bit_lengthを用いています。そちらの方が計測した結果、高速でした。

問題点

ミュータブルな単位元

本家ACL同様に、初期化の際に配列でも数値でもいいとなっている。
しかし、数値で要素数を指定した際に、ミュータブルなクラスでも同一オブジェクトで要素を作ってしまっている。