class

NgLib::StaticRectangleSum(T)

Inherits Reference < Object

不変な二次元配列 $A$ に対して、$\sum_{i=l_i}^{r_i-1} \sum_{j=l_j}^{r_j-1} A_i$ を前計算 $O(N)$ クエリ $O(1)$ で求めます。

Constructors

new(grid : Array(Array(T)))

[](y_range : Range(Int | Nil, Int | Nil), x_range : Range(Int | Nil, Int | Nil)) : T

csum

get(y_begin : Int, y_end : Int, x_begin : Int, x_end : Int) : T

累積和を返します。

[y_begin, y_end), [x_begin, x_end) で指定します。

NOTE: このAPIは非推奨です。Rangeで指定することが推奨されます。

get(y_range : Range(Int | Nil, Int | Nil), x_range : Range(Int | Nil, Int | Nil)) : T

累積和を取得します。

Range(y_begin, y_end), Range(x_begin, x_end) で指定します。

csum = StaticRectangleSum.new(a)
csum.get(0...h, j..j + 2) # => 28

get?(y_begin : Int, y_end : Int, x_begin : Int, x_end : Int) : T | Nil

累積和を返します。

[y_begin, y_end), [x_begin, x_end) で指定します。

範囲内に要素が存在しない場合 nil を返します。

NOTE: このAPIは非推奨です。Rangeで指定することが推奨されます。

累積和を返します。

[y_begin, y_end), [x_begin, x_end) で指定します。

範囲内に要素が存在しない場合 nil を返します。

csum = StaticRectangleSum.new(a)
csum.get?(0...h, j..j + 2)     # => 28
csum.get?(0...100*h, j..j + 2) # => nil

height

width