Nim-ACL

Dual Cumulative Sum 2D

DualCumulativeSum2D は、二次元の矩形加算・一点取得を行う imos 構造です。

import

import atcoder/extra/dp/dual_cumulative_sum_2d

使用例

import atcoder/extra/dp/dual_cumulative_sum_2dvar ds = initDualCumulativeSum2D[int](4, 4)ds.add(1 .. 2, 0 .. 1, 10)ds.add(0 .. 3, 3 .. 3, 5)ds.add(2, 2, -4)ds.build()doAssert ds[1, 0] == 10doAssert ds[2, 1] == 10doAssert ds[2, 2] == -4doAssert ds[3, 3] == 5

API

initDualCumulativeSum2D

var ds = initDualCumulativeSum2D[int](W, H)

add

ds.add(x1 .. x2, y1 .. y2, z)ds.add(x, y, z)

閉矩形 [x1, x2] × [y1, y2] に z を加算します。
ds.add(x, y, z) は一点加算です。

build

ds.build()

imos の累積を反映します。

[]

ds[x, y]

座標 (x, y) の値を返します。

半開矩形API

5整数版の add は半開矩形へ値を加算します。

ds.add(
  xLeft,
  xRight,
  yLeft,
  yRight,
  value,
)

対象領域は次の通りです。

[xLeft, xRight) × [yLeft, yRight)

get(x, y) は ds[x, y] と同じ点取得です。

従来の add(rx, ry, value) は終端を含む Slice APIとして維持されます。

計算量