tpl_sparse_table.H File Reference

Sparse Table for static range queries in O(1). More...

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

Include dependency graph for tpl_sparse_table.H:

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

Go to the source code of this file.

Classes
struct	Aleph::Min_Op< T >
	Functor returning the minimum of two values. More...
struct	Aleph::Max_Op< T >
	Functor returning the maximum of two values. More...
class	Aleph::Gen_Sparse_Table< T, Op >
	Sparse Table over an arbitrary associative and idempotent binary operation. More...
struct	Aleph::Sparse_Table< T >
	Sparse Table for range minimum queries. More...
struct	Aleph::Max_Sparse_Table< T >
	Sparse Table for range maximum queries. More...

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

Concepts
concept	Aleph::SparseTableOp
	Binary operation compatible with Sparse Table queries.

Detailed Description

Sparse Table for static range queries in O(1).

A Sparse Table preprocesses a fixed array of n elements over an associative and idempotent binary operation (one satisfying Op(Op(a, b), c) == Op(a, Op(b, c)) and Op(a, a) == a, such as min, max, gcd, bitwise AND/OR) and answers arbitrary range queries in O(1) time after an O(n log n) build phase.

Three class templates are provided:

• Gen_Sparse_Table<T, Op> — fully generic over any associative and idempotent binary functor Op.
• Sparse_Table<T> — convenient specialisation for range minimum queries using the Min_Op functor.
• Max_Sparse_Table<T> — convenient specialisation for range maximum queries using the Max_Op functor.

Complexity

Operation	Time
Construction	O(n log n)
query	O(1)
get	O(1)
Space	O(n log n)

Note

The underlying array is immutable after construction. If point updates are needed, use a Segment Tree or Fenwick Tree instead.

See also

tpl_fenwick_tree.H Fenwick tree (dynamic, prefix queries).

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

Author

Leandro Rabindranath León

Definition in file tpl_sparse_table.H.