【Rust日报】2022-01-25 —— （基础）精美图表详解线段树！

< 返回版块

【Rust日报】2022-01-25 —— （基础）精美图表详解线段树！

odd-cat 发表于 2022-01-26 12:23

Tags：rust,日报,segtree,thalo.rs,mail-builder,slas,blas

（基础）精美图表详解线段树！

(Basic) Segment Trees with beautiful diagrams!

给定一个长度为N的数组arr，如果有以下操作：

查询区间[l,r]之间的最大值/最小值；
更新给定下标i的对应的值arr[i]；

则可以使用线段树来高效解决上述场景的查询和更新需求；

线段树的时空复杂度：

时间复杂度：O(logN)
空间复杂度：O(N)

Rust实现：

// SegTree segment tree
fn main() {
    let arr = [4i32, 3, 2, 8, 5, 1, 2, 1];
    let max = |i, j| <i32>::max(i, j);

    let mut seg_tree = SegTree::new(&arr, max);
    println!("max(arr): {}", seg_tree.query((0, 7)));

    seg_tree.update(2, 10);
    println!("max(arr): {}", seg_tree.query((0, 7)));
}

struct SegTree<T, F, const N: usize>
    where
        [T; N]: Sized,
        F: Fn(T, T) -> T,
{
    buf: Vec<T>,
    f: F,
}

impl<T, F, const N: usize> SegTree<T, F, N>
    where
        T: Ord + Default + Copy,
        [T; N]: Sized,
        F: Fn(T, T) -> T,
{
    pub fn new(arr: &[T; N], f: F) -> Self {
        let mut buf = vec![T::default(); 2 * N];
        buf[N..2 * N].copy_from_slice(arr);
        for i in (1..N).rev() {
            buf[i] = f(buf[2 * i], buf[(2 * i + 1)]);
        }
        SegTree { buf, f }
    }

    pub fn query(&self, (mut l, mut r): (usize, usize)) -> T {
        l += N - 1;
        r += N - 1;
        let mut ans = self.buf[l];
        while l <= r {
            if l % 2 == 1 {
                ans = (self.f)(ans, self.buf[l]);
                l += 1;
            }
            if r % 2 == 0 {
                ans = (self.f)(ans, self.buf[r]);
                r -= 1;
            }
            l /= 2;
            r /= 2;
        }
        ans
    }

    pub fn update(&mut self, mut idx: usize, val: T) {
        idx += N - 1;
        self.buf[idx] = val;
        idx /= 2;

        while idx != 1 {
            self.buf[idx] = (self.f)(self.buf[2 * idx], self.buf[2 * idx + 1]);
            idx /= 2;
        }
    }
}

参考链接：

Thalo.rs —— Rust中的事件溯源库

Thalo.rs - Event Sourcing in Rust

Thalo是一个基于以下模式构建大型系统的事件溯源框架：

事件溯源
CQRS
事件驱动
事务发件箱
DDD

它的设计是模块化的，带有实现大多数功能的额外库。

官方提供的库：

核心库
- thalo: 核心框架
- thalo-testing: thalo的测试组件；
- thalo-macros: 实现trait的宏（可以通过macro特性开关在核心库中打开此功能）；
事件存储
- thalo-postgres: 为Postgres实现EventStore trait；
- thalo-inmemory: 内存实现EventStore；
- thalo-filestore: 为filestore实现EventStore；
事件流
- thalo-kafka:为kafka实现EventStream；