class NgLib::StaticRangeSum(T)
- NgLib::StaticRangeSum(T)
- Reference
- Object
Overview
不変な数列 $A$ に対して、$\sum_{i=l}^{r-1} A_i$ を前計算 $O(N)$ クエリ $O(1)$ で求めます。
Defined in:
nglib/data_structure/static_range_sum.crConstructors
-
.new(array : Array(T))
配列
arrayに対して累積和を構築します。
Instance Method Summary
-
#[](l, r) : T
#get(l : Int, r : Int)へのエイリアスです。 -
#[](range : Range(Int | Nil, Int | Nil)) : T
#get(range : Range(Int?, Int?))へのエイリアスです。 -
#[]?(l, r) : T | Nil
#get(l : Int, r : Int)へのエイリアスです。 -
#[]?(range : Range(Int | Nil, Int | Nil)) : T | Nil
#get?(range : Range(Int?, Int?))へのエイリアスです。 - #csum : Array(T)
-
#get(l, r) : T
$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。
-
#get(range : Range(Int | Nil, Int | Nil)) : T
$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。
-
#get!(l, r) : T
$\sum_{i=1}^{r - 1} a_i - \sum_{i=1}^{l} a_i$ を $O(1)$ で返します。
-
#get!(range : Range(Int | Nil, Int | Nil)) : T
$\sum_{i=1}^{r - 1} a_i - \sum_{i=1}^{l} a_i$ を $O(1)$ で返します。
-
#get?(l, r) : T | Nil
$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。
-
#get?(range : Range(Int | Nil, Int | Nil)) : T | Nil
$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(1)$ で返します。
-
#lower_bound(x)
self[0...r] >= x を満たす最小の self[0...r]
-
#lower_bound_index(x)
self[0...r] >= x を満たす最小の r を返します。
- #size : Int64
-
#upper_bound(x)
self[0...r] > x を満たす最小の self[0...r]
-
#upper_bound_index(x)
self[0...r] > x を満たす最小の r を返します。
Constructor Detail
配列 array に対して累積和を構築します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = StaticRangeSum(Int32).new(array)Instance Method Detail
#get(range : Range(Int?, Int?)) へのエイリアスです。
#get?(range : Range(Int?, Int?)) へのエイリアスです。
$[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$[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$\sum_{i=1}^{r - 1} a_i - \sum_{i=1}^{l} a_i$ を $O(1)$ で返します。
$[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$[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