Expand description
This library provides simple and easy to use segment trees and some variations of them, by simply implementing certain traits. It also gives some already implemented nodes types, which serve can also serve as examples.
Modules
Structs
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.
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.