class NgLib:: SlideMinmax(T)

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

Overview

データ列 $a$ に対して、$\min(a_i, a_{i + 1}, \dots, a_{i + \mathrm{length} - 1})$ を、 前計算 $O(N)$ クエリが $O(1)$ 求めるためのデータ構造です。

セグメント木やSparseTableと異なり、区間長が固定の範囲でしかクエリに答えられませんが高速です。

#query(i) で $[i, i + \mathrm{length})$ が配列の範囲を超えたとき、$[i, \mathrm{a.size})$ だと思って計算します。

もし、 #query(i) で $[i - \mathrm{length}, i)$ が求まってほしい場合は、 a = ([eins] * length) + a としておけば良いです。 範囲外の場合は $[0, i)$ だと思って計算されます。

なお、$[0, 0)$ の場合は単位元が返ります。

もし、query(i) で $[i - \mathrm{length}, i]$ が求まってほしい場合は、 a = ([eins] * (length - 1)) + a としておけば良いです。 範囲外の場合は $[0, i]$ だと思って計算されます。

Defined in:

Constructors

• .new (a : Array(T), length : Int, eins : T, &cmp : T, T -> Bool)

  データ列 $a$ に対して、$cmp(a_i, a_{i + 1}, \dots, a_{i + \mathrm{length} - 1})$ を求めるためのデータ構造を構築します。

Class Method Summary

• .max (a : Array(T), length : Int)

  データ列 $a$ に対して、$\max(a_i, a_{i + 1}, \dots, a_{i + \mathrm{length} - 1})$ を求めるためのデータ構造を構築します。

• .min (a : Array(T), length : Int)

  データ列 $a$ に対して、$\min(a_i, a_{i + 1}, \dots, a_{i + \mathrm{length} - 1})$ を求めるためのデータ構造を構築します。

Instance Method Summary

• #query (i : Int) : T

  $[i, i + \mathrm{length})$ の範囲の総積 $cmp(a_i, a_{i + 1}, \dots, a_{i + \mathrm{length} - 1})$ を求めます。

• #query? (i : Int) : T | Nil

  $[i, i + \mathrm{length})$ の範囲の総積 $cmp(a_i, a_{i + 1}, \dots, a_{i + \mathrm{length} - 1})$ を求めます。

Constructor Detail

rmq = SlideMinmax(Int32).new([2, 7, 3, 4, 6], 3) { |a, b| a <= b } # => min query

Class Method Detail

rmq = SlideMinmax(Int32).max([2, 7, 3, 4, 6], 3)

rmq = SlideMinmax(Int32).min([2, 7, 3, 4, 6], 3)

Instance Method Detail

rmq = SlideMinmax(Int32).min([2, 7, 3, 4, 6], 3)
rmq.query(0) # => 2
rmq.query(1) # => 3
rmq.query(2) # => 3
rmq.query(3) # => 4
rmq.query(4) # => 6

rmq = SlideMinmax(Int32).min([2, 7, 3, 4, 6], 3)
rmq.query?(0)   # => 2
rmq.query?(1)   # => 3
rmq.query?(2)   # => 3
rmq.query?(3)   # => 4
rmq.query?(4)   # => 6
rmq.query?(100) # => nil