tpl_fenwick_tree.H File Reference

Fenwick tree (Binary Indexed Tree) for prefix queries. More...

#include <bit>
#include <cassert>
#include <concepts>
#include <initializer_list>
#include <type_traits>
#include <vector>
#include <utility>
#include <tpl_array.H>
#include <tpl_dynList.H>
#include <ahFunction.H>
#include <ah-errors.H>

Include dependency graph for tpl_fenwick_tree.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Gen_Fenwick_Tree< T, Plus, Minus >
	Fenwick tree over an arbitrary abelian group. More...
struct	Aleph::Fenwick_Tree< T >
	Fenwick tree for arithmetic types with find_kth support. More...
class	Aleph::Range_Fenwick_Tree< T >
	Fenwick tree supporting range updates and range queries. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Concepts
concept	Aleph::FenwickArithmetic
	Arithmetic domain accepted by Fenwick specializations.
concept	Aleph::FenwickBinaryOp
	Binary operation compatible with Fenwick tree group functors.

Detailed Description

Fenwick tree (Binary Indexed Tree) for prefix queries.

A Fenwick tree maintains an implicit array of n elements over an abelian group (an associative, commutative, invertible binary operation with identity) and supports prefix and range queries and point updates in O(log n) time.

Three class templates are provided:

• Gen_Fenwick_Tree<T, Plus, Minus> — fully generic over any abelian group given by the binary functors Plus and Minus.
• Fenwick_Tree<T> — convenient specialisation for signed arithmetic types (uses operator+ / operator-). Adds the find_kth order-statistic query that exploits the internal bit layout in O(log n).
• Range_Fenwick_Tree<T> — signed arithmetic variant that supports range updates and range queries in O(log n).

Complexity

Operation	Time
Construction	O(n)
update	O(log n)
prefix	O(log n)
query	O(log n)
find_kth	O(log n)
get / set	O(log n)
Space	O(n)

See also

https://en.wikipedia.org/wiki/Fenwick_tree

Author

Leandro Rabindranath León

Definition in file tpl_fenwick_tree.H.