ac-library-hs-0.1.0.0: Data structures and algorithms
Safe HaskellNone
LanguageGHC2021

AtCoder.FenwickTree

Description

Fenwick tree, also known as binary index 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

Expand

You can 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

You can 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

Synopsis

Fenwick tree

data FenwickTree s a #

Fenwick tree.

Since: 1.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

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

Modifying the Fenwick tree

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

Accessor

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

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

Constraints

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

Complexity

  • \(O(\log n)\)

Since: 1.0.0