AtCoder.FenwickTree

A Fenwick tree, also known as binary indexed tree. Given an array of length \(n\), it processes the following queries in \(O(\log n)\) time.

• Updating an element
• Calculating the sum of the elements of an interval

Example

Create a FenwickTree with new:

>>> import AtCoder.FenwickTree qualified as FT
>>> ft <- FT.new @_ @Int 4 -- [0, 0, 0, 0]
>>> FT.nFt ft
4

It can perform point add and range sum in \(O(\log n)\) time:

>>> FT.add ft 0 3          -- [3, 0, 0, 0]
>>> FT.sum ft 0 3
3

>>> FT.add ft 2 3          -- [3, 0, 3, 0]
>>> FT.sum ft 0 3
6

Create a FenwickTree with initial values using build:

>>> ft <- FT.build @_ @Int $ VU.fromList [3, 0, 3, 0]
>>> FT.add ft 1 2          -- [3, 2, 3, 0]
>>> FT.sum ft 0 3
8

Since: 1.0.0.0

Fenwick tree

data FenwickTree s a

A Fenwick tree.

Since: 1.0.0.0

Constructors

new :: (HasCallStack, PrimMonad m, Num a, Unbox a) => Int -> m (FenwickTree (PrimState m) a)

Creates an array \([a_0, a_1, \cdots, a_{n-1}]\) of length \(n\). All the elements are initialized to \(0\).

Constraints

• \(0 \leq n\)

Complexity

• \(O(n)\)

Since: 1.0.0.0

build :: (PrimMonad m, Num a, Unbox a) => Vector a -> m (FenwickTree (PrimState m) a)

Creates FenwickTree with initial values.

Complexity

• \(O(n)\)

Since: 1.0.0.0

Adding

add :: (HasCallStack, PrimMonad m, Num a, Unbox a) => FenwickTree (PrimState m) a -> Int -> a -> m ()

Adds \(x\) to \(p\)-th value of the array.

Constraints

• \(0 \leq l \lt n\)

Complexity

• \(O(\log n)\)

Since: 1.0.0.0

Accessor

sum :: (HasCallStack, PrimMonad m, Num a, Unbox a) => FenwickTree (PrimState m) a -> Int -> Int -> m a

Calculates the sum in a half-open interval \([l, r)\).

Constraints

• \(0 \leq l \leq r \leq n\)

Complexity

• \(O(\log n)\)

Since: 1.0.0.0

sumMaybe :: (HasCallStack, PrimMonad m, Num a, Unbox a) => FenwickTree (PrimState m) a -> Int -> Int -> m (Maybe a)

Total variant of sum. Calculates the sum in a half-open interval \([l, r)\). It returns Nothing if the interval is invalid.

Complexity

• \(O(\log n)\)

Since: 1.0.0.0