Struct Persistent

pub struct Persistent<T: PersistentNode> { /* private fields */ }

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.

Implementations

impl<T> Persistent<T>

where T: PersistentNode + Clone,

pub fn build(values: &[T]) -> Self

Builds persistent segment tree from slice, each element of the slice will correspond to a leaf of the segment tree. It has time complexity of O(n*log(n)), assuming that combine has constant time complexity.

pub fn query(&self, version: usize, left: usize, right: usize) -> Option<T>

Returns the result from the range [left,right] from the version of the segment tree. It returns None if and only if range is empty. It will panic if left or right are not in [0,n), or if version is not in [0,versions). It has time complexity of O(log(n)), assuming that combine has constant time complexity.

pub fn update(&mut self, version: usize, p: usize, value: &<T as Node>::Value)

Creates a new segment tree version from version were the p-th element of the segment tree to value T and update the segment tree correspondingly. It will panic if p is not in [0,n), or if version is not in [0,versions). It has time complexity of O(log(n)), assuming that combine has constant time complexity.

pub fn versions(&self) -> usize

Return the amount of different versions the current segment tree has.

pub fn lower_bound<F, G>( &self, version: usize, predicate: F, g: G, value: <T as Node>::Value, ) -> usize

where F: Fn(&<T as Node>::Value, &<T as Node>::Value) -> bool, G: Fn(&<T as Node>::Value, <T as Node>::Value) -> <T as Node>::Value,

A method that finds the smallest prefix¹ u such that predicate(u.value(), value) is true. The following must be true:

• predicate is monotonic over prefixes².
• g will satisfy the following, given segments [i,j] and [i,k] with j<k we have that predicate([i,k].value(),value) implies predicate([j+1,k].value(),g([i,j].value(),value)).

These are two examples, the first is finding the smallest prefix which sums at least some value.

let predicate = |left_value:&usize, value:&usize|{*left_value>=*value}; // Is the sum greater or equal to value?
let g = |left_node:&usize,value:usize|{value-*left_node}; // Subtract the sum of the prefix.
let seg_tree = Persistent::build(&nodes); // [0,1,2,3,4,5,6,7,8,9] with Sum<usize> nodes
let index = seg_tree.lower_bound(0, predicate, g, 3); // Will return 2 as sum([0,1,2])>=3

The second is finding the position of the smallest value greater or equal to some value.

let predicate = |left_value:&usize, value:&usize|{*left_value>=*value}; // Is the maximum greater or equal to value?
let g = |_left_node:&usize,value:usize|{value}; // Do nothing
let seg_tree = Persistent::build(&nodes); // [0,1,2,3,4,5,6,7,8,9] with Max<usize> nodes
let index = seg_tree.lower_bound(0, predicate, g, 3); // Will return 3 as 3>=3

---

1. A prefix is a segment of the form [0,i]. ↩

2. Given two prefixes u and v if u is contained in v then predicate(u.value(), value) implies predicate(v.value(), value). ↩