Dual Cumulative Sum

DualCumulativeSum is a one-dimensional imos helper supporting range additions and point queries.

Import

import atcoder/extra/dp/dual_cumulative_sum

Example

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

API

initDualCumulativeSum

var ds = initDualCumulativeSum[int](n)

add

ds.add(l .. r, x)ds.add(i, x)

Adds x to the closed interval [l, r]. ds.add(i, x) is a point addition.

[]

ds[i]

Returns the value at position i.

Complexity

• add: O(1)
• ds[i]: propagated lazily; total amortized O(n)