class
NgLib::
- 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
$[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$[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