Safe Haskell | None |
---|---|
Language | GHC2021 |
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
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
- data FenwickTree s a
- new :: (HasCallStack, PrimMonad m, Num a, Unbox a) => Int -> m (FenwickTree (PrimState m) a)
- build :: (PrimMonad m, Num a, Unbox a) => Vector a -> m (FenwickTree (PrimState m) a)
- add :: (HasCallStack, PrimMonad m, Num a, Unbox a) => FenwickTree (PrimState m) a -> Int -> a -> m ()
- sum :: (HasCallStack, PrimMonad m, Num a, Unbox a) => FenwickTree (PrimState m) a -> Int -> Int -> m a
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
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