class

NgLib::SparseTable(T)

Inherits Reference < Object

不変な数列 $A$ について、以下の条件を満たす演算を、区間クエリとして処理します。

前計算は $O(N \log{N})$ かかりますが、区間クエリには $O(1)$ で答えられます。

Constructors

new(elems : Enumerable(T), op : T, T -> T)

$\oplus = op$ としてデータ構造を構築します。

bitwise_and(elems : Enumerable(T))

$\oplus = \mathrm{bitwise-and}$ としてデータ構造を構築します。

bitwise_or(elems : Enumerable(T))

$\oplus = \mathrm{bitwise-or}$ としてデータ構造を構築します。

gcd(elems : Enumerable(T))

$\oplus = \mathrm{gcd}$ としてデータ構造を構築します。

max(elems : Enumerable(T))

$\oplus = \max$ としてデータ構造を構築します。

min(elems : Enumerable(T))

$\oplus = \min$ としてデータ構造を構築します。

[](range : Range(Int | Nil, Int | Nil))

prod へのエイリアスです。

[](i)

$a_i$ を返します。

[]?(range : Range(Int | Nil, Int | Nil))

prod? へのエイリアスです。

[]?(i)

$a_i$ を返します。

添字が範囲外のとき、nil を返します。

prod(range : Range(Int | Nil, Int | Nil))

range の表す範囲の要素の総積 $\bigoplus_{i \in range} a_i$ を返します。

rmq = SparseTable(Int32).min([2, 7, 1, 8, 1])
rmq.prod(0...3) # => 1

prod?(range : Range(Int | Nil, Int | Nil))

range の表す範囲の要素の総積 $\bigoplus_{i \in range} a_i$ を返します。

$0 \leq l \leq r \leq n$ を満たさないとき、nil を返します。

rmq = SparseTable(Int32).min([2, 7, 1, 8, 1])
rmq.prod(0...3) # => 1

size