Safe Haskell	Safe-Inferred
Language	GHC2021

AtCoder.FenwickTree

Contents

Fenwick tree
Constructors
Adding
Accessor

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)

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

Accessor

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

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