class

NgLib::DualSegTree(T)

Inherits Indexable::Mutable < Indexable < Enumerable < Iterable < Indexable < Enumerable < Iterable < Reference < Object

区間作用・$1$ 点取得ができるセグメント木です。

作用素 $f$ は、要素 $x$ と同じ型である必要があります。

Constructors

new(values : Array(T), &application : T, T -> T)

作用素を $f$ とした、$i$ 番目の要素が values[i] の双対セグメント木を作ります。

seg = NgLib::DualSegTree(Int32).new([*(1..5)]) { |f, x| x + f }
seg # => [1, 2, 3, 4, 5]
Source
new(size : Int, &application : T, T -> T)

作用素を $f$ とした、要素数 $n$ の双対セグメント木を作ります。

各要素は単位元を表す nil で初期化されます。

seg = NgLib::DualSegTree(Int32).new(5) { |f, x| x + f }
seg # => [nil, nil, nil, nil, nil]
Source

Class methods

range_add(values : Array(T))

作用素 $f(x) = x + f$ とした双対セグメント木を作ります。

Source
range_add(size : Int)

作用素 $f(x) = x + f$ とした双対セグメント木を作ります。

Source
range_chmax(values : Array(T))

作用素 $f(x) = \max(f, x)$ とした双対セグメント木を作ります。

Source
range_chmax(size : Int)

作用素 $f(x) = \max(f, x)$ とした双対セグメント木を作ります。

Source
range_chmin(values : Array(T))

作用素 $f(x) = \min(f, x)$ とした双対セグメント木を作ります。

Source
range_chmin(size : Int)

作用素 $f(x) = \min(f, x)$ とした双対セグメント木を作ります。

Source
range_update(values : Array(T))

作用素 $f(x) = f$ とした双対セグメント木を作ります。

Source
range_update(size : Int)

作用素 $f(x) = f$ とした双対セグメント木を作ります。

Source

Instance methods

[]=(start : Int, count : Int, applicator : T)

#apply へのエイリアスです。

seg = NgLib::DualSegTree(Int32).new([*(1..5)]) { |f, x| x + f }
seg # => [1, 2, 3, 4, 5]
seg[0, 2] = 10
seg # => [11, 12, 3, 4, 5]
Source
[]=(range : Range(Int | Nil, Int | Nil), applicator : T)

#apply へのエイリアスです。

seg = NgLib::DualSegTree(Int32).new([*(1..5)]) { |f, x| x + f }
seg # => [1, 2, 3, 4, 5]
seg[0...2] = 10
seg # => [11, 12, 3, 4, 5]
Source
apply(start : Int, count : Int, application : T)

start 番目から count 個までの各要素に applicator を作用させます。

seg = NgLib::DualSegTree(Int32).new([*(1..5)]) { |f, x| x + f }
seg # => [1, 2, 3, 4, 5]
seg.apply(0, 2, 10)
seg # => [11, 12, 3, 4, 5]
Source
apply(range : Range(Int | Nil, Int | Nil), applicator : T)

range の表す区間に applicator を作用させます。

seg = NgLib::DualSegTree(Int32).new([*(1..5)]) { |f, x| x + f }
seg # => [1, 2, 3, 4, 5]
seg.apply(0...2, 10)
seg # => [11, 12, 3, 4, 5]
Source
apply_all(applicator : T)

すべての要素に application を作用させます。

seg = NgLib::DualSegTree(Int32).new([*(1..5)]) { |f, x| x + f }
seg # => [1, 2, 3, 4, 5]
seg.all_apply(10)
seg # => [11, 12, 13, 14, 15]
Source
size

Returns the number of elements in this container.

Source
to_s(io : IO)

Appends a short String representation of this object which includes its class name and its object address.

class Person
  def initialize(@name : String, @age : Int32)
  end
end

Person.new("John", 32).to_s # => #<Person:0x10a199f20>
Source
unsafe_fetch(index : Int)

Returns the element at the given index, without doing any bounds check.

Indexable makes sure to invoke this method with index in 0...size, so converting negative indices to positive ones is not needed here.

Clients never invoke this method directly. Instead, they access elements with #[](index) and #[]?(index).

This method should only be directly invoked if you are absolutely sure the index is in bounds, to avoid a bounds check for a small boost of performance.

Source
unsafe_put(index : Int, value : T)

Sets the element at the given index to value, without doing any bounds check.

Indexable::Mutable makes sure to invoke this method with index in 0...size, so converting negative indices to positive ones is not needed here.

Clients never invoke this method directly. Instead, they modify elements with #[]=(index, value).

This method should only be directly invoked if you are absolutely sure the index is in bounds, to avoid a bounds check for a small boost of performance.

Source

Nested types