Crate seg_tree

  

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

nodes

Node traits.

utils

Provided node implementations.

Structs

Iterative

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.

LazyPersistent

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.

LazyRecursive

Lazy segment tree with range queries and range updates. It uses O(n) space, assuming that each node uses O(1) space.

Persistent

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.

Recursive

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.