[Rust原创] ST表-可以自定义比较函数

sgct

使用Rust实现的ST表(Sparse Table)

English Version
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

以上是使用方面的readme，接下来讲一下如何实现

pub struct SparseTable {
    pub dp: Vec<Vec<i32>>,
    op: fn(i32, i32) -> i32,
}
impl SparseTable {
    pub fn init(v: &Vec<i32>, op: fn(i32, i32) -> i32) -> Self {
        let len = v.len();
        let wid = (v.len() as f64).log2().ceil() as usize + 1;
        let mut dp = vec![vec![0; wid]; len];
        for i in 0..len {
            dp[i][0] = v[i];
        }
        for j in 1..wid {
            for i in 0..len {
                if i + (1 << j) - 1 < len {
                    dp[i][j] = op(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
                }
            }
        }
        SparseTable { dp, op }
    }
    pub fn query(&self, l: usize, r: usize) -> i32 {
        if l > r || l > self.dp.len() || r > self.dp.len() {
            panic!("Array Index Out Of Bounds Exception!!")
        }
        if l == r {
            self.dp[l][0]
        } else {
            let s = ((r - l + 1) as f64).log2().ceil() as usize - 1;
            (self.op)(self.dp[l][s], self.dp[r - (1 << s) + 1][s])
        }
    }
}

hrpzcf

论坛很少见写 Rust 的