使用 Rust 实现的 ST 表 (稀疏表)

英文版本
ST 表是一种高效的数据结构，在利用 O(n*log2(n)) 的时间建立索引后，可以以 O(1) 的时间查询区间最大值/最小值/最大公约数等。这是一个非常高效的数据结构。

用法：

• 在 Cargo.toml 中添加依赖

sparse_table = "*"

示例：

use sparse_table::SparseTable;
use std::cmp::max;

fn main() {
    let spt = SparseTable::init(&vec![5, 3, 8, 10, 1], max);
    println!("{:?}", spt.dp);
    dbg!(spt.query(0, 4));
}

输出结果：

[[5, 5, 10, 0], [3, 8, 10, 0], [8, 10, 0, 0], [10, 10, 0, 0], [1, 0, 0, 0]]
[src\main.rs:7] spt.query(0, 4) = 10

如果输入的函数是 max，则 query 返回的就是区间最大值，如果输入的是 gcd，则返回的就是区间 gcd