Nim-ACL

Cumulative Sum 2D

CumulativeSum2D is a two-dimensional cumulative-sum helper for rectangle-sum queries.

Import

import atcoder/extra/dp/cumulative_sum_2d

Example

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

Starting from an empty grid

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)

Adds z to cell (x, y). Call it before build().

build

cs.build()

Builds the cumulative sum table.

[]

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

Returns the sum of the closed rectangle [x1, x2] × [y1, y2].

Complexity