class
NgLib::
- NgLib::DynamicRangeSum(T)
- Reference
- Object
Overview
動的な数列 $a$ に対して累積和を求めます。
累積和クエリは $O(\log{N})$ で処理することができます。
実装は BIT (Fenwick Tree) です。
もし、区間加算 $1$ 点取得がしたい場合は、このライブラリといもす法を組み合わせると良いです。 長さ $n$ の数列に対して操作する場合、BIT の長さは $n + 1$ 必要なことに注意してください。
-
$[l, r)$ に $x$ を加算 :
#add(l, x) ; add(r, -x) -
$i$ 番目を取得 :
#[..i]
Defined in:
nglib/data_structure/dynamic_range_sum.crConstructors
-
.new
(n : Int, val : T)
長さが $n$ で各要素が $val$ の数列 $a$ を構築します。
-
.new
(elems : Enumerable(T))
長さが $n$ で $i$ 番目の要素が $elems_i$ の数列 $a$ を構築します。
-
.new
(n : Int)
長さが $n$ で各要素が $0$ の数列 $a$ を構築します。
Instance Method Summary
-
#[]
(l, r) : T
$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(\log{N})$ で返します。
-
#[]
(range : Range(Int | Nil, Int | Nil)) : T
rangeの表す範囲の要素の総和 $\sum_{i \in range} a_i$ を $O(\log{N})$ で返します。 -
#[]
(i) : T
$a_i$ を $O(\log{N})$ で返します。
-
#[]=
(i : Int, x : T) : T
$a_i$ の値を $x$ に更新します。
-
#[]?
(l, r) : T | Nil
$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(\log{N})$ で返します。
-
#[]?
(range : Range(Int | Nil, Int | Nil)) : T
rangeの表す範囲の要素の総和 $\sum_{i \in range} a_i$ を $O(\log{N})$ で返します。 -
#[]?
(i) : T | Nil
$a_i$ を $O(\log{N})$ で返します。
-
#add
(i : Int, x : T)
$a_i$ に $x$ を加算します。
-
#get
(l, r) : T
$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(\log{N})$ で返します。
-
#get
(range : Range(Int | Nil, Int | Nil)) : T
rangeの表す範囲の要素の総和 $\sum_{i \in range} a_i$ を $O(\log{N})$ で返します。 -
#get
(i) : T
$a_i$ を $O(\log{N})$ で返します。
-
#get?
(l, r) : T | Nil
$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(\log{N})$ で返します。
-
#get?
(range : Range(Int | Nil, Int | Nil)) : T
rangeの表す範囲の要素の総和 $\sum_{i \in range} a_i$ を $O(\log{N})$ で返します。 -
#get?
(i) : T | Nil
$a_i$ を $O(\log{N})$ で返します。
-
#set
(i : Int, x : T)
$a_i$ の値を $x$ に更新します。
- #size : Int32
Constructor Detail
長さが $n$ で $i$ 番目の要素が $elems_i$ の数列 $a$ を構築します。
Instance Method Detail
$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(\log{N})$ で返します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum[0, 5] # => 1 + 1 + 2 + 3 + 5 = 12
range
の表す範囲の要素の総和 $\sum_{i \in range} a_i$ を $O(\log{N})$ で返します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum[0...5] # => 1 + 1 + 2 + 3 + 5 = 12$a_i$ を $O(\log{N})$ で返します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum[5] # => 8$a_i$ の値を $x$ に更新します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum.get?(0...5) # => 1 + 1 + 2 + 3 + 5 = 12
csum[0] = 100
csum.get?(0...5) # => 100 + 1 + 2 + 3 + 5 = 111$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(\log{N})$ で返します。
$0 \leq l \leq r \leq n$ を満たさないとき、
nil
を返します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum[0, 5]? # => 1 + 1 + 2 + 3 + 5 = 12
csum[7, 3]? # => nil
range
の表す範囲の要素の総和 $\sum_{i \in range} a_i$ を $O(\log{N})$ で返します。
$0 \leq l \leq r \leq n$ を満たさないとき、
nil
を返します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum[0...5]? # => 1 + 1 + 2 + 3 + 5 = 12
csum[7...3]? # => nil$a_i$ を $O(\log{N})$ で返します。
$0 \leq i \lt n$ を満たさないとき、
nil
を返します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum[5] # => 8
csum[10]? # => nil$a_i$ に $x$ を加算します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum.get?(0...5) # => 1 + 1 + 2 + 3 + 5 = 12
csum.add(0, 99)
csum.get?(0...5) # => 100 + 1 + 2 + 3 + 5 = 111$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(\log{N})$ で返します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum.get(0, 5) # => 1 + 1 + 2 + 3 + 5 = 12
range
の表す範囲の要素の総和 $\sum_{i \in range} a_i$ を $O(\log{N})$ で返します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum.get(0...5) # => 1 + 1 + 2 + 3 + 5 = 12$a_i$ を $O(\log{N})$ で返します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum.get(5) # => 8$[l, r)$ 番目までの要素の総和 $\sum_{i=l}^{r-1} a_i$ を $O(\log{N})$ で返します。
$0 \leq l \leq r \leq n$ を満たさないとき、
nil
を返します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum.get?(0, 5) # => 1 + 1 + 2 + 3 + 5 = 12
csum.get?(7, 3) # => nil
range
の表す範囲の要素の総和 $\sum_{i \in range} a_i$ を $O(\log{N})$ で返します。
$0 \leq l \leq r \leq n$ を満たさないとき、
nil
を返します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum.get?(0...5) # => 1 + 1 + 2 + 3 + 5 = 12
csum.get?(7...3) # => nil$a_i$ を $O(\log{N})$ で返します。
$0 \leq i \lt n$ を満たさないとき、
nil
を返します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum.get?(5) # => 8
csum.get?(10)? # => nil$a_i$ の値を $x$ に更新します。
array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum.get?(0...5) # => 1 + 1 + 2 + 3 + 5 = 12
csum.set(0, 100)
csum.get?(0...5) # => 100 + 1 + 2 + 3 + 5 = 111