class NgLib:: SparseTable(T)

• NgLib::SparseTable(T)
• Reference
• Object

Overview

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

• 結合則 : $(x \oplus y) \oplus z = x \oplus (y \oplus z)$
• 冪等性 : $x \oplus x = x$

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

Defined in:

Constructors

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

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

Class Method Summary

• .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$ としてデータ構造を構築します。

Instance Method Summary

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

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

• #[] (i)

  $a_i$ を返します。

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

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

• #[]? (i)

  $a_i$ を返します。

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

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

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

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

• #size : Int32

Constructor Detail

Class Method Detail

Instance Method Detail

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

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