Module seg_tree::segment_tree
source · [−]Expand description
Segment trees.
Structs
Lazy persistent segment tree, it saves every version of itself, it has range queries and range updates.
It uses O(n+q*log(n)) space, where q is the amount of updates, and assuming that each node uses O(1) space.
Lazy segment tree with range queries and range updates.
It uses O(n) space, assuming that each node uses O(1) space.
Persistent segment tree, it saves every version of itself, it has range queries and point updates.
It uses O(n+q*log(n)) space, where q is the amount of updates, and assuming that each node uses O(1) space.
Segment tree with range queries and point updates.
It uses O(n) space, assuming that each node uses O(1) space.
Note if you don’t need to use lower_bound, just use the SegmentTree it uses half the memory and it’s more performant.
Segment tree with range queries and point updates.
It uses O(n) space, assuming that each node uses O(1) space.
Note if you need to use lower_bound, just use the RecursiveSegmentTree it uses double the memory though and it’s less performant.