class

NgLib::StaticRangeSum(T)

Inherits Reference < Object

不変な数列 $A$ に対して、$\sum_{i=l}^{r-1} A_i$ を前計算 $O(N)$ クエリ $O(1)$ で求めます。

Constructors

new(array : Array(T))

配列 array に対して累積和を構築します。

array = [1, 1, 2, 3, 5, 8, 13]
csum = StaticRangeSum(Int32).new(array)

Source

Instance methods

[](l, r) : T

get(l : Int, r : Int) へのエイリアスです。

Source

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

get(range : Range(Int?, Int?)) へのエイリアスです。

Source

[]?(l, r) : T | Nil

get(l : Int, r : Int) へのエイリアスです。

Source

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

get?(range : Range(Int?, Int?)) へのエイリアスです。

Source

csum

Source

get(l, r) : T

$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。

array = [1, 1, 2, 3, 5, 8, 13]
csum = StaticRangeSum(Int32).new(array)
csum.get(0...5) # => 1 + 1 + 2 + 3 + 5 = 12

Source

get(range : Range(Int | Nil, Int | Nil)) : T

$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。

array = [1, 1, 2, 3, 5, 8, 13]
csum = StaticRangeSum(Int32).new(array)
csum.get(0...5) # => 1 + 1 + 2 + 3 + 5 = 12

Source

get!(l, r) : T

$\sum_{i=1}^{r - 1} a_i - \sum_{i=1}^{l} a_i$ を $O(1)$ で返します。

Source

get!(range : Range(Int | Nil, Int | Nil)) : T

$\sum_{i=1}^{r - 1} a_i - \sum_{i=1}^{l} a_i$ を $O(1)$ で返します。

Source

get?(l, r) : T | Nil

$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。

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

array = [1, 1, 2, 3, 5, 8, 13]
csum = StaticRangeSum(Int32).new(array)
csum.get?(0...5) # => 1 + 1 + 2 + 3 + 5 = 12
csum.get?(7...5) # => nil

Source

get?(range : Range(Int | Nil, Int | Nil)) : T | Nil

$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。

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

array = [1, 1, 2, 3, 5, 8, 13]
csum = StaticRangeSum(Int32).new(array)
csum.get?(0...5) # => 1 + 1 + 2 + 3 + 5 = 12
csum.get?(7...5) # => nil

Source

lower_bound(x)

self[0...r] >= x を満たす最小の self[0...r]

Source

lower_bound_index(x)

self[0...r] >= x を満たす最小の r を返します。

Source

size

Source

upper_bound(x)

self[0...r] > x を満たす最小の self[0...r]

Source

upper_bound_index(x)

self[0...r] > x を満たす最小の r を返します。

Source