chtholly_tree 0.1.0

Rust bindings for Chtholly Tree
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

## About 

- This repo implements the `Chtholly Tree` in Rust 
- `Chtholly Tree` is a data structure originated from [C. Willem, Chtholly and Seniorious](https://codeforces.com/problemset/problem/896/C?mobile=true), 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 = "0.1.0"
```

## Example

To demonstrate its usage, [leetcode 699. Falling Squares](https://leetcode.com/problems/falling-squares/) is used as an example 

```rust
#[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 developed based on 
- [Crate chtholly](https://docs.rs/chtholly/latest/chtholly/)