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.