tpl_disjoint_sparse_table.H File Reference

Disjoint 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_disjoint_sparse_table.H:

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

Go to the source code of this file.

Classes
class	Aleph::Gen_Disjoint_Sparse_Table< T, Op >
	Disjoint Sparse Table over an arbitrary associative binary operation. More...
struct	Aleph::Sum_Disjoint_Sparse_Table< T >
	Disjoint Sparse Table for range sum queries. More...
struct	Aleph::Product_Disjoint_Sparse_Table< T >
	Disjoint Sparse Table for range product queries. More...

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

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

Detailed Description

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

A Disjoint Sparse Table preprocesses a fixed array of n elements over an associative binary operation (not necessarily idempotent) and answers arbitrary range queries in O(1) time after an O(n log n) build phase.

Unlike the classical Sparse Table (which requires idempotency), the disjoint variant works for any associative operation: addition, multiplication, XOR, matrix multiplication, string concatenation, modular arithmetic, etc.

The technique decomposes the array into disjoint blocks at each level and stores prefix/suffix aggregates from each block's midpoint. Because the sub-ranges never overlap, no idempotency is needed.

Three class templates are provided:

• Gen_Disjoint_Sparse_Table<T, Op> — fully generic over any associative binary functor Op.
• Sum_Disjoint_Sparse_Table<T> — convenient specialisation for range sum queries using Aleph::plus<T>.
• Product_Disjoint_Sparse_Table<T> — convenient specialisation for range product queries using Aleph::multiplies<T>.

Complexity

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

Comparison with classical Sparse Table

Feature	Sparse Table	Disjoint Sparse Table
Operation requirement	Assoc. + idempotent	Associative only
Works for sum/product	No	Yes
Works for min/max	Yes	Yes
Query time	O(1)	O(1)
Build time	O(n log n)	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_sparse_table.H Classical sparse table (idempotent ops).

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

https://discuss.codechef.com/t/tutorial-disjoint-sparse-table/17404

Author

Leandro Rabindranath León

Definition in file tpl_disjoint_sparse_table.H.