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

Key	Shortcut
s	Open this search box
esc	Close this search box
↓,ctrl + j	Move down in search results
↑,ctrl + k	Move up in search results
↵	Go to active search result