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}-\mathrm{and}$ としてデータ構造を構築します。

• .bitwise_or (elems : Enumerable(T))

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

• .gcd (elems : Enumerable(T))

  $\oplus =\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 の表す範囲の要素の総積 $\underset{i\in range}{⨁}{a}_i$ を返します。

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

  range の表す範囲の要素の総積 $\underset{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