Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.FenwickTree

Contents

Fenwick tree
Constructors
Adding
Accessors
Bisection methods

Description

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

Expand

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

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
sumMaybe :: (HasCallStack, PrimMonad m, Num a, Unbox a) => FenwickTree (PrimState m) a -> Int -> Int -> m (Maybe a)
maxRight :: (HasCallStack, PrimMonad m, Num a, Unbox a) => FenwickTree (PrimState m) a -> Int -> (a -> Bool) -> m Int
maxRightM :: forall m a. (HasCallStack, PrimMonad m, Num a, Unbox a) => FenwickTree (PrimState m) a -> Int -> (a -> m Bool) -> m Int
minLeft :: (HasCallStack, PrimMonad m, Num a, Unbox a) => FenwickTree (PrimState m) a -> Int -> (a -> Bool) -> m Int
minLeftM :: forall m a. (HasCallStack, PrimMonad m, Num a, Unbox a) => FenwickTree (PrimState m) a -> Int -> (a -> m Bool) -> m Int

Fenwick tree

data FenwickTree s a Source #

A Fenwick tree.

Since: 1.0.0.0

Constructors

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

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) Source #

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 () Source #

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

Constraints

\(0 \leq l \lt n\)

Complexity

\(O(\log n)\)

Since: 1.0.0.0

Accessors

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

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) Source #

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

Bisection methods

maxRight Source #

Arguments

:: (HasCallStack, PrimMonad m, Num a, Unbox a)
=> FenwickTree (PrimState m) a	The Fenwick tree
-> Int	\(l\)
-> (a -> Bool)	\(p\): user predicate
-> m Int	\(r\): \(p\) holds for \([l, r)\)

(Extra API) Applies a binary search on the Fenwick tree. It returns an index \(r\) that satisfies both of the following.

\(r = l\) or \(f(a[l] + a[l + 1] + ... + a[r - 1])\) returns True.
\(r = n\) or \(f(a[l] + a[l + 1] + ... + a[r]))\) returns False.

If \(f\) is monotone, this is the maximum \(r\) that satisfies \(f(a[l] + a[l + 1] + ... + a[r - 1])\).

Constraints

if \(f\) is called with the same argument, it returns the same value, i.e., \(f\) has no side effect.
\(f(0)\) returns True
\(0 \leq l \leq n\)

Complexity

\(O(\log n)\)

Since: 1.2.2.0

maxRightM Source #

Arguments

:: forall m a. (HasCallStack, PrimMonad m, Num a, Unbox a)
=> FenwickTree (PrimState m) a	The Fenwick tree
-> Int	\(l\)
-> (a -> m Bool)	\(p\): user predicate
-> m Int	\(r\): \(p\) holds for \([l, r)\)

(Extra API) Monadic variant of maxRight.

Constraints

if \(f\) is called with the same argument, it returns the same value, i.e., \(f\) has no side effect.
\(f(0)\) returns True
\(0 \leq l \leq n\)

Complexity

\(O(\log n)\)

Since: 1.2.2.0

minLeft Source #

Arguments

:: (HasCallStack, PrimMonad m, Num a, Unbox a)
=> FenwickTree (PrimState m) a	The Fenwick tree
-> Int	\(r\)
-> (a -> Bool)	\(p\): user prediate
-> m Int	\(l\): \(p\) holds for \([l, r)\)

Applies a binary search on the Fenwick tree. It returns an index \(l\) that satisfies both of the following.

\(l = r\) or \(f(a[l] + a[l + 1] + ... + a[r - 1])\) returns True.
\(l = 0\) or \(f(a[l - 1] + a[l] + ... + a[r - 1])\) returns False.

If \(f\) is monotone, this is the minimum \(l\) that satisfies \(f(a[l] + a[l + 1] + ... + a[r - 1])\).

Constraints

if \(f\) is called with the same argument, it returns the same value, i.e., \(f\) has no side effect.
\(f(0)\) returns True
\(0 \leq r \leq n\)

Complexity

\(O(\log n)\)

Since: 1.2.2.0

minLeftM Source #

Arguments

:: forall m a. (HasCallStack, PrimMonad m, Num a, Unbox a)
=> FenwickTree (PrimState m) a	The Fenwick tree
-> Int	\(r\)
-> (a -> m Bool)	\(p\): user prediate
-> m Int	\(l\): \(p\) holds for \([l, r)\)

(Extra API) Monadic variant of minLeft.

Constraints

if \(f\) is called with the same argument, it returns the same value, i.e., \(f\) has no side effect.
\(f(0)\) returns True
\(0 \leq l \leq n\)

Complexity

\(O(\log n)\)

Since: 1.2.2.0