【Rust日报】2022-01-25 Slas v0.2.0 —— 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;
        }
    }
}