Skip to content

Latest commit

 

History

History
186 lines (119 loc) · 6.13 KB

segtree.md

File metadata and controls

186 lines (119 loc) · 6.13 KB
Raw

Segtree

セグメント木です。

特異メソッド

new(arg, e){ |x, y| ... } -> Segtree

new(arg, op, e) -> Segtree

seg = Segtree.new(arg, e) { |x, y| ... }

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

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

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

計算量 O(n)

モノイドの設定コード例

n   = 10**5
inf = (1 << 60) - 1

Segtree.new(n, 0) { |x, y| x.gcd y }       # gcd
Segtree.new(n, 1) { |x, y| x.lcm y }       # lcm
Segtree.new(n, -inf) { |x, y| [x, y].max } # max
Segtree.new(n,  inf) { |x, y| [x, y].min } # min
Segtree.new(n, 0) { |x, y| x | y }         # or
Segtree.new(n, 1) { |x, y| x * y }         # prod
Segtree.new(n, 0) { |x, y| x + y }         # sum

インスタンスメソッド

set(pos, x)

seg.set(pos, x)

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

計算量

  • O(logn)

get(pos)

seg.get(pos)

a[pos] を返します。

計算量

  • O(1)

prod(l, r)

seg.prod(l, r)

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

制約

  • 0 ≦ l ≦ r ≦ n

計算量

  • O(logn)

all_prod

seg.all_prod

op(a[0], ..., a[n - 1]) を返します。空のセグメントツリー、つまりサイズが0のとき、単位元eを返します。

計算量

  • O(1)

max_right(l, &f) -> Integer

seg.max_right(l, &f)

Segtree上でl <= r <= nの範囲で、f(prod(l, r))の結果を二分探索をして条件に当てはまるrを返します。

以下の条件を両方満たす r (l <= r <= n)を(いずれか一つ)返します。

  • r = l もしくは f(prod(l, r))がtrueとなるr
  • r = n もしくは f(prod(l, r + 1))がfalseとなるr

prod(l, r)は半開区間[l, r)であることに注意。

制約

  • fを同じ引数で呼んだとき、返り値は同じ。
  • f(e)がtrue
  • 0 ≦ l ≦ n

計算量

  • O(log n)

min_left(r, &f) -> Integer

seg.min_left(r, &f)

Segtree上で0 <= l <= rの範囲で、f(prod(l, r))の結果を二分探索をして条件に当てはまるlを返します。

以下の条件を両方満たす l (0 <= l <= r)を(いずれか一つ)返します。

  • l = r もしくは f(prod(l, r))がtrueとなるl
  • l = 0 もしくは f(prod(l - 1, r))がfalseとなるl

prod(l, r)は半開区間[l, r)であることに注意。

制約

  • fを同じ引数で呼んだとき、返り値は同じ。
  • f(e)がtrue
  • 0 ≦ l ≦ n

計算量

  • O(log n)

Verified

参考リンク

本家ライブラリとの違い等

基本的に、本家の実装に合わせています。

内部実装に関しても、変数@dの0番目の要素には必ず単位元@eが入ります。

変数名の違い

Rubyにはpメソッドがあるので、引数pについて、pではなくpositionのposを変数名として使いました。

同様に、本家の変数sizeを、わかりやすさからleaf_sizeとしています。

ceil_pow2ではなく、bit_length

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