class

NgLib::DynamicRangeSum(T)

Inherits Reference < Object

動的な数列 $a$ に対して累積和を求めます。

累積和クエリは $O(\log{N})$ で処理することができます。

実装は BIT (Fenwick Tree) です。

もし、区間加算 $1$ 点取得がしたい場合は、このライブラリといもす法を組み合わせると良いです。 長さ $n$ の数列に対して操作する場合、BIT の長さは $n + 1$ 必要なことに注意してください。

  • $[l, r)$ に $x$ を加算 : #add(l, x); add(r, -x)
  • $i$ 番目を取得 : #[..i]

Constructors

new(n : Int, val : T)

長さが $n$ で各要素が $val$ の数列 $a$ を構築します。

Source
new(elems : Enumerable(T))

長さが $n$ で $i$ 番目の要素が $elems_i$ の数列 $a$ を構築します。

Source
new(n : Int)

長さが $n$ で各要素が $0$ の数列 $a$ を構築します。

Source

Instance methods

[](l, r) : T

$[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
Source
[](range : Range(Int | Nil, Int | Nil)) : T

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
Source
[](i) : T

$a_i$ を $O(\log{N})$ で返します。

array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum[5] # => 8
Source
[]=(i : Int, x : T) : T

$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
Source
[]?(l, r) : T | Nil

$[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
Source
[]?(range : Range(Int | Nil, Int | Nil)) : T

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
Source
[]?(i) : T | 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
Source
add(i : Int, x : T)

$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
Source
get(l, r) : T

$[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
Source
get(range : Range(Int | Nil, Int | Nil)) : T

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
Source
get(i) : T

$a_i$ を $O(\log{N})$ で返します。

array = [1, 1, 2, 3, 5, 8, 13]
csum = DynamicRangeSum(Int32).new(array)
csum.get(5) # => 8
Source
get?(l, r) : T | Nil

$[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
Source
get?(range : Range(Int | Nil, Int | Nil)) : T

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
Source
get?(i) : T | 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
Source
set(i : Int, x : T)

$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
Source
size
Source