AtCoder.Extra.WaveletMatrix2d

A 2D, static wavelet matrix with segment tree, that can handle point add and rectangle sum queries. Points cannot be added after construction, but monoid values in each point can be modified later.

Example

Create a WaveletMatrix2d with initial vertex values:

>>> import AtCoder.Extra.WaveletMatrix2d qualified as WM
>>> import Data.Semigroup (Sum (..))
>>> import Data.Vector.Unboxed qualified as VU
>>> -- 8  9 10 11
>>> -- 4  5  6  7
>>> -- 0  1  2  3
>>> wm <- WM.build negate $ VU.generate 12 $ \i -> let (!y, !x) = i `divMod` 4 in (x, y, Sum i)

Read the value at \(x = 2, y = 1\):

>>> WM.read wm (2, 1)
Sum {getSum = 6}

Other segment tree methods are also available, but in 2D:

>>> WM.allProd wm -- (0 + 11) * 12 / 2 = 66
Sum {getSum = 66}

>>> WM.prod wm {- x -} 1 3 {- y -} 0 3 -- 1 + 2 + 5 + 6 + 9 + 10
Sum {getSum = 33}

>>> WM.modify wm (+ 2) (1, 1)
>>> WM.prod wm {- x -} 1 3 {- y -} 0 3 -- 1 + 2 + 7 + 6 + 9 + 10
Sum {getSum = 35}

>>> WM.write wm (1, 1) $ Sum 0
>>> WM.prod wm {- x -} 1 3 {- y -} 0 3 -- 1 + 2 + 0 + 6 + 9 + 10
Sum {getSum = 28}

Wavelet matrix 2D

data WaveletMatrix2d s a

Segment Tree on Wavelet Matrix: points on a 2D plane and rectangle products.

Constructors

WaveletMatrix2d

Fields

• rawWmWm2d :: !RawWaveletMatrix

  The wavelet matrix that represents points on a 2D plane.

• xyDictWm2d :: !(Vector (Int, Int))

  (x, y) index compression dictionary.

• yDictWm2d :: !(Vector Int)

  y index compression dictionary.

• segTreesWm2d :: !(Vector (SegTree s a))

  The segment tree of the weights of the points in the order of xyDictWm2d.

• invWm2d :: !(a -> a)

  The inverse operator of the interested monoid.

Counstructor

new

Arguments

:: (PrimMonad m, Monoid a, Unbox a)

=> (a -> a)

Inverse operator of the monoid

-> Vector (Int, Int)

Input points

-> m (WaveletMatrix2d (PrimState m) a)

A 2D wavelet matrix

\(O(n \log n)\) Creates a WaveletMatrix2d with mempty as the initial monoid values for each point.

build

Arguments

:: (PrimMonad m, Monoid a, Unbox a)

=> (a -> a)

Inverse operator of the monoid

-> Vector (Int, Int, a)

Input points with initial values

-> m (WaveletMatrix2d (PrimState m) a)

A 2D wavelet matrix

\(O(n \log n)\) Creates a WaveletMatrix2d with wavelet matrix with segment tree with initial monoid values. Monoids on a duplicate point are accumulated with (<>).

Segment tree methods

read :: (HasCallStack, Unbox a, Monoid a, PrimMonad m) => WaveletMatrix2d (PrimState m) a -> (Int, Int) -> m a

\(O(1)\) Returns the monoid value at \((x, y)\).

write :: (HasCallStack, Monoid a, Unbox a, PrimMonad m) => WaveletMatrix2d (PrimState m) a -> (Int, Int) -> a -> m ()

\(O(\log^2 n)\) Writes the monoid value at \((x, y)\). Access to unknown points are undefined.

modify :: (HasCallStack, Monoid a, Unbox a, PrimMonad m) => WaveletMatrix2d (PrimState m) a -> (a -> a) -> (Int, Int) -> m ()

\(O(\log^2 n)\) Modifies the monoid value at \((x, y)\). Access to unknown points are undefined.

prod :: (HasCallStack, Unbox a, Monoid a, PrimMonad m) => WaveletMatrix2d (PrimState m) a -> Int -> Int -> Int -> Int -> m a

\(O(\log^2 n)\) Returns the monoid product in \([l, r) \times [y_1, y_2)\).

prodMaybe :: (Unbox a, Monoid a, PrimMonad m) => WaveletMatrix2d (PrimState m) a -> Int -> Int -> Int -> Int -> m (Maybe a)

\(O(\log^2 n)\) Returns the monoid product in \([l, r) \times [y_1, y_2)\). Returns Nothing for invalid intervals.

allProd :: (HasCallStack, Unbox a, Monoid a, PrimMonad m) => WaveletMatrix2d (PrimState m) a -> m a

\(O(\log^2 n)\) Return the monoid product of all of the points in the wavelet matrix.