Struct libpuri::SegTree

pub struct SegTree<M: Monoid>(_);

A segment tree that supports range query.

A segment tree is used when you want to query on properties of interval. For instance, you have a list of numbers and you want to get a minimum value of certain interval. If you compute it on the fly, it would require (m - 1) comparisons for the length m interval. We can use a segment tree to efficiently compute the minimum element.

Each node of a segment tree represents a union of intervals of their child nodes and each leaf node means an interval containing only one element. Following is an example segment tree of elements [1, 42, 16, 3, 5].

                         +-----+
                         |  1  |
                         +-----+
                         [0, 8)
                    /               \
                   /                 \
           +---+                         +---+
           | 1 |                         | 5 |
           +---+                         +---+  
           [0, 4)                        [4, 8)  
          /     \                       /     \
         /       \                     /       \
     +---+       +---+             +---+       +----+  
     | 1 |       | 3 |             | 5 |       | id |   
     +---+       +---+             +---+       +----+   
     [0, 2)      [2, 4)            [4, 6)      [6, 8)  
    /    |       |    \           /    |       |    \
   /     |       |     \         /     |       |     \
+---+  +----+  +----+  +---+  +---+  +----+  +----+  +----+
| 1 |  | 42 |  | 16 |  | 3 |  | 5 |  | id |  | id |  | id |
+---+  +----+  +----+  +---+  +---+  +----+  +----+  +----+
[0, 1) [1, 2)  [2, 3)  [3, 4) [4, 5) [5, 6)  [6, 7)  [7, 8)

When you update an element, it propagates from the leaf to the top. If we update 16 to 2, then the parent node would be updated to 3 -> 2, but the [0, 4) and root node won't be updated as 1 is less than 2.

When querying, it visits non-overlapping nodes within the inteval and computes the minimum among the nodes. For example if we query minimum element in an interval [1, 4), it first visits [1, 2) node and then it visits [2, 4). Then it computes min(42, 3) which is 3. Note that it only visits two nodes at each height of the tree hence the time complexity O(log(n)).

Use a segment tree when:

• You only update one element at a time.
• You want to efficiently query on a property of interval.
• The interval property is computed by associative operations on the elements in the interval.

To be precise, a segment tree requires the elements to implement the Monoid trait.

Performance

Given n elements, it computes the interval property in O(log(n)) at the expense of O(log(n)) update time.

If we were to store the elements with Vec, it would take O(m) for length m interval query and O(1) to update.

Examples

use libpuri::{Monoid, SegTree};

// We'll use the segment tree to compute interval sum.
#[derive(Clone, Debug, PartialEq, Eq)]
struct Sum(i64);

impl Monoid for Sum {
    const ID: Self = Sum(0);
    fn op(&self, rhs: &Self) -> Self { Sum(self.0 + rhs.0) }
}

// Segment tree can be initialized from an iterator of the monoid
let mut seg_tree: SegTree<Sum> = [1, 2, 3, 4, 5].iter().map(|&n| Sum(n)).collect();

// Add elements within range 0..=3
assert_eq!(seg_tree.get(0..=3), Sum(10));

// Update element at 2 to 42
seg_tree.set(2, Sum(42));
assert_eq!(seg_tree.get(0..=3), Sum(49));

Implementations

impl<M: Monoid> SegTree<M>

pub fn new(size: usize) -> Self

Constructs a new segment tree with at least given number of intervals can be stored.

The segment tree will be initialized with the identity elements.

Complexity

O(n).

If you know the initial elements in advance, collect() should be preferred over new().

Initializing with the identity elements and updating n elements will tax you O(nlog(n)), whereas collect() implementation is O(n) by computing the interval properties only once.

Examples

use libpuri::{Monoid, SegTree};

#[derive(Clone, Debug, PartialEq, Eq)]
struct MinMax(i64, i64);

impl Monoid for MinMax {
    const ID: Self = Self(i64::MAX, i64::MIN);
    fn op(&self, rhs: &Self) -> Self { Self(self.0.min(rhs.0), self.1.max(rhs.1)) }
}

let mut seg_tree: SegTree<MinMax> = SegTree::new(4);

seg_tree.set(0, MinMax(1, 1));
assert_eq!(seg_tree.get(0..4), MinMax(1, 1));

seg_tree.set(3, MinMax(4, 4));
assert_eq!(seg_tree.get(0..2), MinMax(1, 1));
assert_eq!(seg_tree.get(2..4), MinMax(4, 4));

seg_tree.set(2, MinMax(3, 3));
assert_eq!(seg_tree.get(0..3), MinMax(1, 3));
assert_eq!(seg_tree.get(0..4), MinMax(1, 4));

pub fn get<R>(&self, range: R) -> M where
    R: IntoIndex, 

Queries on the given interval.

Note that any RangeBounds can be used including .., a.., ..b, ..=c, d..e, or f..=g. You can just seg_tree.get(..) to get the interval property of the entire elements and seg_tree.get(a) to get a specific element.

Examples

let mut seg_tree: SegTree<MinMax> = SegTree::new(4);

assert_eq!(seg_tree.get(..), MinMax::ID);

seg_tree.set(0, MinMax(42, 42));

assert_eq!(seg_tree.get(..), MinMax(42, 42));
assert_eq!(seg_tree.get(1..), MinMax::ID);
assert_eq!(seg_tree.get(0), MinMax(42, 42));

pub fn set(&mut self, i: usize, m: M)

Sets an element with index i to a value m. It propagates its update to its parent.

It takes O(log(n)) to propagate the update as the height of the tree is log(n).

Examples

let mut seg_tree: SegTree<MinMax> = SegTree::new(4);

seg_tree.set(0, MinMax(4, 4));

Trait Implementations

impl<M: Debug + Monoid> Debug for SegTree<M>

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<M: Monoid> FromIterator<M> for SegTree<M>

You can collect into a segment tree.

pub fn from_iter<I: IntoIterator<Item = M>>(iter: I) -> Self

Creates a value from an iterator.