[Rust原创] ST表-可以自定义比较函数
# 使用Rust实现的ST表(Sparse Table)(./ReadMe_en.md)
ST表是一类高效的数组结构，在利用O(n*log2(n))的时间建完索引后，就可以使用O(1)的时间查询区间最大值/最小值/最大公约数等。是一个非常高效的数据结构。
用法：
- 在`Cargo.toml`里添加依赖
```toml
sparse_table = "*"
```
例子：
```rust
use sparse_table::SparseTable;
use std::cmp::max;
fn main() {
let spt = SparseTable::init(&vec!, max);
println!("{:?}", spt.dp);
dbg!(spt.query(0, 4));
}
```
输出结果：
```text
[, , , , ]
spt.query(0, 4) = 10
```
如果给入的函数是max，则query返回的就是区间最大值，如果给入的是gcd，返回的就是区间gcd
以上是使用方面的readme，接下来讲一下如何实现
```rust
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!; len];
for i in 0..len {
dp = v;
}
for j in 1..wid {
for i in 0..len {
if i + (1 << j) - 1 < len {
dp = op(dp, dp);
}
}
}
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
} else {
let s = ((r - l + 1) as f64).log2().ceil() as usize - 1;
(self.op)(self.dp, self.dp)
}
}
}
``` 论坛很少见写 Rust 的:lol
页:
[1]