class AtCoder::LazySegTree(S, F)

• AtCoder::LazySegTree(S, F)
• Reference
• Object

Overview

Implements atcoder::lazy_segtree.

The identity element will be implicitly defined as nil, so you don't have to manually define it. In the other words, you cannot include nil into an element of the monoid.

Similarly, the identity map of F will be implicitly defined as nil, so you don't have to manually define it. In the other words, you cannot include nil into an element of the set F.

op = ->(a : Int32, b : Int32) { [a, b].min }
mapping = ->(f : Int32, x : Int32) { f }
composition = ->(a : Int32, b : Int32) { a }
tree = AtCoder::LazySegTree(Int32, Int32).new((0...100).to_a, op, mapping, composition)
tree[10...50] # => 10
tree[20...60] = 0
tree[50...80] # => 0

Defined in:

lazy_seg_tree.cr

Constructors

• .new(values : Array(S), operator : S, S -> S, application : F, S -> S, composition : F, F -> F)

Instance Method Summary

• #[](index : Int)

  Implements atcoder::lazy_segtree.get(index).

• #[](range : Range)

  Implements atcoder::lazy_segtree.prod(left, right).

• #[]=(index : Int, applicator : F)

  Implements atcoder::lazy_segtree.apply(index, applicator).

• #[]=(range : Range, applicator : F)

  Implements atcoder::lazy_segtree.apply(left, right, applicator).

• #all_prod

  Implements atcoder::lazy_segtree.all_prod().

• #max_right(left, e : S | Nil = nil, & : S -> Bool)

  Implements atcoder::lazy_segtree.max_right(left, g).

• #min_left(right, e : S | Nil = nil, & : S -> Bool)

  Implements atcoder::lazy_segtree.min_left(right, g).

• #set(index : Int, value : S)

  Implements atcoder::lazy_segtree.set(index, applicator).

Constructor Detail

Instance Method Detail