class NgLib::StaticRectangleSum(T)

• NgLib::StaticRectangleSum(T)
• Reference
• Object

Overview

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

Defined in:

Constructors

• .new(grid : Array(Array(T)))

Instance Method Summary

• #[](y_range : Range(Int | Nil, Int | Nil), x_range : Range(Int | Nil, Int | Nil)) : T
• #[]?(y_range : Range(Int | Nil, Int | Nil), x_range : Range(Int | Nil, Int | Nil)) : T | Nil
• #csum : Array(Array(T))
• #get(y_begin : Int, y_end : Int, x_begin : Int, x_end : Int) : T

  累積和を返します。

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

  累積和を取得します。

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

  累積和を返します。

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

  累積和を返します。

• #height : Int32
• #width : Int32

Constructor Detail

Instance Method Detail

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

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