Nim-ACL

Cumulative Sum 2D

CumulativeSum2D は、二次元配列の矩形和を求めるための二次元累積和です。

import

import atcoder/extra/dp/cumulative_sum_2d

使用例

import atcoder/extra/dp/cumulative_sum_2dlet a = @[  @[1, 2, 3],  @[4, 5, 6],  @[7, 8, 9],]var cs = initCumulativeSum2D(a)doAssert cs[0 .. 1, 0 .. 1] == 12doAssert cs[1 .. 2, 1 .. 2] == 28doAssert cs[0 .. 2, 0 .. 2] == 45

空の状態から使う

var cs = initCumulativeSum2D[int](3, 3)cs.add(0, 0, 5)cs.add(2, 1, 7)cs.build()doAssert cs[0 .. 2, 0 .. 2] == 12doAssert cs[2 .. 2, 1 .. 1] == 7

API

initCumulativeSum2D

var cs = initCumulativeSum2D(a)
var cs2 = initCumulativeSum2D[int](W, H)

add

cs.add(x, y, z)

座標 (x, y) に z を加算します。build() の前に呼んでください。

build

cs.build()

累積和を構築します。

[]

cs[x1 .. x2, y1 .. y2]

閉矩形 [x1, x2] × [y1, y2] の和を返します。

半開矩形API

width と height は構築対象の大きさを返します。

sum(xLeft, xRight, yLeft, yRight) は半開矩形

[xLeft, xRight) × [yLeft, yRight)

の総和を返します。allSum は全領域の総和です。

doAssert cs.width == W
doAssert cs.height == H

let partial =
  cs.sum(
    xLeft,
    xRight,
    yLeft,
    yRight,
  )

let total = cs.allSum

従来の cs[rx, ry] は終端を含む Slice APIとして維持されます。

計算量