tpl_segment_tree.H File Reference

Segment trees for dynamic range queries with lazy propagation. More...

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

Include dependency graph for tpl_segment_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_Segment_Tree< T, Op >
	Segment tree over an arbitrary associative binary operation. More...
struct	Aleph::Sum_Segment_Tree< T >
	Sum Segment Tree for range sum queries with point updates. More...
struct	Aleph::Min_Segment_Tree< T >
	Min Segment Tree for range minimum queries with point updates. More...
struct	Aleph::Max_Segment_Tree< T >
	Max Segment Tree for range maximum queries with point updates. More...
struct	Aleph::Add_Sum_Policy< T >
	Range add + range sum policy. More...
struct	Aleph::Add_Min_Policy< T >
	Range add + range min policy. More...
struct	Aleph::Add_Max_Policy< T >
	Range add + range max policy. More...
struct	Aleph::Assign_Sum_Policy< T >
	Range assign + range sum policy. More...
class	Aleph::Gen_Lazy_Segment_Tree< Policy >
	Lazy segment tree with range update and range query. More...
struct	Aleph::Lazy_Sum_Segment_Tree< T >
	Lazy segment tree for range add + range sum. More...
struct	Aleph::Lazy_Min_Segment_Tree< T >
	Lazy segment tree for range add + range min. More...
struct	Aleph::Lazy_Max_Segment_Tree< T >
	Lazy segment tree for range add + range max. More...
class	Aleph::Segment_Tree_Beats< T >
	Ji Driver's Segment Tree (Segment Tree Beats). More...
struct	Aleph::Segment_Tree_Beats< T >::Node

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

Concepts
concept	Aleph::SegmentTreeOp
	Binary operation compatible with Segment Tree queries.
concept	Aleph::SegmentTreePolicy
	Policy concept for lazy segment tree.

Detailed Description

Segment trees for dynamic range queries with lazy propagation.

This file provides three segment tree variants:

• Gen_Segment_Tree<T, Op> — Point update + range query over an arbitrary associative binary operation (monoid). Does not require idempotency or invertibility.
• Gen_Lazy_Segment_Tree<Policy> — Range update + range query with lazy propagation, parameterised by a policy that bundles value type, lazy type, combine, apply, and compose operations.
• Segment_Tree_Beats<T> — Ji Driver's Segment Tree supporting range chmin/chmax with sum/min/max queries.

Complexity

Operation	Gen_Segment_Tree	Gen_Lazy_Segment_Tree	Segment_Tree_Beats
Build	O(n)	O(n)	O(n)
Point update	O(log n)	O(log n)	O(log n)
Range update	—	O(log n)	O(log n) amort.
Query	O(log n)	O(log n)	O(log n)
Space	O(n)	O(n)	O(n)

See also

tpl_sparse_table.H Static O(1) range queries (idempotent ops).

tpl_fenwick_tree.H Prefix-based range queries (invertible ops).

Author

Leandro Rabindranath León

Definition in file tpl_segment_tree.H.