chtholly_tree

About

• This repo implements the Chtholly Tree in Rust
• Chtholly Tree is a data structure originated from C. Willem, Chtholly and Seniorious, which could be used to update the values of intervals
• Note that the input data should be random for it to achieve a time complexity of O(nloglogn)

Cargo.toml

[dependencies]
chtholly_tree = "1.0.0"

Example

To demonstrate its usage, leetcode 699. Falling Squares is used as an example

#[cfg(test)]
mod tests {
    use super::*;

    /// Test Chtholly Tree using [leetcode 699. Falling Squares](https://leetcode.com/problems/falling-squares/).
    #[test]
    fn test_tree() {
        let positions = vec![vec![1, 2], vec![2, 3], vec![6, 1]];

        let mut results = Vec::<i32>::new();
        let mut max_height = 0;
        let mut ct_tree = ChthollyTree::new();
        ct_tree.assign(1_i32, 10i32.pow(8), 0_i32);
        for pos in positions {
            let itr = ct_tree.split(pos[0] + pos[1]);
            let itl = ct_tree.split(pos[0]);
            let mut height = 0;
            for i in itl..itr + 1 {
                height = height.max(ct_tree.nodes[i].value + pos[1]);
                max_height = max_height.max(height);
            }
            ct_tree.assign(pos[0], pos[0] + pos[1] - 1, height);
            results.push(max_height);
        }
        assert_eq!(results, vec![2, 5, 5]);
    }
}

Reference

This repo is inspired by

• Crate chtholly