Aleph::Fenwick_Tree< T > Struct Template Reference

Fenwick tree for arithmetic types with find_kth support. More...

#include <tpl_fenwick_tree.H>

Inheritance diagram for Aleph::Fenwick_Tree< T >:

Collaboration diagram for Aleph::Fenwick_Tree< T >:

Public Types
using	Base = Gen_Fenwick_Tree< T, Aleph::plus< T >, Aleph::minus< T > >
Public Types inherited from Aleph::Gen_Fenwick_Tree< T, Aleph::plus< T >, Aleph::minus< T > >
using	Item_Type = T
	The type of element stored in the tree.

Public Member Functions
size_t	find_kth (T k) const
	Find the smallest 0-based index i such that prefix(i) >= k.
Public Member Functions inherited from Aleph::Gen_Fenwick_Tree< T, Aleph::plus< T >, Aleph::minus< T > >
	Gen_Fenwick_Tree (const size_t num, Aleph::plus< T > pop=Aleph::plus< T >(), Aleph::minus< T > mop=Aleph::minus< T >())
	Construct a tree with num elements, all equal to the identity T().
	Gen_Fenwick_Tree (std::initializer_list< T > il, Aleph::plus< T > pop=Aleph::plus< T >(), Aleph::minus< T > mop=Aleph::minus< T >())
	Construct from an initializer list in O(n) time.
	Gen_Fenwick_Tree (const Array< T > &values, Aleph::plus< T > pop=Aleph::plus< T >(), Aleph::minus< T > mop=Aleph::minus< T >())
	Construct from an Array<T> in O(n) time.
	Gen_Fenwick_Tree (const std::vector< T > &values, Aleph::plus< T > pop=Aleph::plus< T >(), Aleph::minus< T > mop=Aleph::minus< T >())
	Construct from a std::vector<T> in O(n) time.
	Gen_Fenwick_Tree (const DynList< T > &values, Aleph::plus< T > pop=Aleph::plus< T >(), Aleph::minus< T > mop=Aleph::minus< T >())
	Construct from a DynList<T> in O(n) time.
	Gen_Fenwick_Tree (const Gen_Fenwick_Tree &)=default
	Gen_Fenwick_Tree (Gen_Fenwick_Tree &&) noexcept=default
Gen_Fenwick_Tree &	operator= (const Gen_Fenwick_Tree &)=default
Gen_Fenwick_Tree &	operator= (Gen_Fenwick_Tree &&) noexcept=default
void	update (size_t i, const T &delta)
	Point update: a[i] = Plus(a[i], delta).
T	prefix (size_t i) const
	Prefix query: Plus(a[0], a[1], ..., a[i]).
T	query (const size_t l, const size_t r) const
	Range query: Plus(a[l], a[l+1], ..., a[r]).
T	get (const size_t i) const
	Retrieve the logical value a[i].
void	set (const size_t i, const T &value)
	Set a[i] = value.
constexpr size_t	size () const noexcept
	Number of logical elements.
constexpr bool	is_empty () const noexcept
	True if the tree contains no elements.
Array< T >	values () const
	Reconstruct all original values into an Array.
void	swap (Gen_Fenwick_Tree &other) noexcept
	Swap this tree with other in O(1).

Additional Inherited Members
Protected Member Functions inherited from Aleph::Gen_Fenwick_Tree< T, Aleph::plus< T >, Aleph::minus< T > >
void	build ()
	O(n) bottom-up construction of the tree array from raw values already placed in tree[1..n].
void	fill_from_indexed (F getter)
	Fill the internal storage from a 0-based indexed getter and build.
void	fill_from_std_iter (StdIt first, StdIt last)
	Fill the internal storage from a standard iterator range and build.
void	fill_from_aleph_it (AlephIt it)
	Fill the internal storage from an Aleph-style iterator (get_it()) and build.
Static Protected Member Functions inherited from Aleph::Gen_Fenwick_Tree< T, Aleph::plus< T >, Aleph::minus< T > >
static constexpr size_t	lowbit (size_t x) noexcept
	Return the least significant set bit of x (as a mask).
Protected Attributes inherited from Aleph::Gen_Fenwick_Tree< T, Aleph::plus< T >, Aleph::minus< T > >
Array< T >	tree
size_t	n
Aleph::plus< T >	plus_op
Aleph::minus< T >	minus_op

Detailed Description

template<FenwickArithmetic T>
struct Aleph::Fenwick_Tree< T >

Fenwick tree for arithmetic types with find_kth support.

Inherits every operation from Gen_Fenwick_Tree using the standard operator+ / operator- and adds find_kth, which finds the smallest 0-based index whose prefix sum reaches a given target.

Template Parameters

T	arithmetic element type.

Example

Fenwick_Tree<int> ft(10);
ft.update(2, 3);
ft.update(5, 7);
ft.update(8, 1);
size_t idx = ft.find_kth(4);  // smallest i with prefix(i) >= 4

Definition at line 411 of file tpl_fenwick_tree.H.

Member Typedef Documentation

Base

template<FenwickArithmetic T>

using Aleph::Fenwick_Tree< T >::Base = Gen_Fenwick_Tree<T, Aleph::plus<T>, Aleph::minus<T> >

Definition at line 414 of file tpl_fenwick_tree.H.

Member Function Documentation

find_kth()

template<FenwickArithmetic T>

size_t Aleph::Fenwick_Tree< T >::find_kth ( T  k ) const

inline

Find the smallest 0-based index i such that prefix(i) >= k.

Precondition: all stored values must be non-negative so that prefix sums are monotonically non-decreasing.

Performs a single O(log n) descent through the tree structure (no binary search).

This operation is available only for integral T.

Parameters

k	target cumulative value.

Returns

0-based index, or size() if the total sum is less than k.

Definition at line 432 of file tpl_fenwick_tree.H.

References Aleph::maps(), Aleph::Gen_Fenwick_Tree< T, Aleph::plus< T >, Aleph::minus< T > >::n, Aleph::next(), and Aleph::Gen_Fenwick_Tree< T, Aleph::plus< T >, Aleph::minus< T > >::tree.

---

The documentation for this struct was generated from the following file:

• tpl_fenwick_tree.H