Lib.rs

关于

• 本仓库实现了Rust中的Chtholly Tree
• Chtholly Tree是一种源自C. Willem, Chtholly and Seniorious的数据结构，可用于更新区间的值
• 注意，为了实现时间复杂度为O(nloglogn)，输入数据应该是随机的

Cargo.toml

[dependencies]
chtholly_tree = "1.0.0"

示例

为了展示其用法，使用了leetcode 699. Falling Squares作为示例

#[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]);
    }
}

参考

本仓库受到以下启发

• Crate chtholly