数列 - 区間更新 RMQ
概要
群 \(X\) 上の数列について次の2つが高速に計算可能:
- 区間取得
- 任意の区間の値の全ての積(和)を計算する
- 区間更新(代入操作)
- 任意の区間の値をある値で上書きする
/// Sequence - Lazy Segment Tree - Ranged RMQ
use crate::algebra::act_assign::*;
use crate::algebra::monoid_minmax::*;
use crate::sequence::tree::lazy_segment_tree::*;
pub type RangedRMaxQ<X> = LazySegmentTree<MaxInt<X>, Assign<MaxInt<X>>>;
pub type RangedRMinQ<X> = LazySegmentTree<MinInt<X>, Assign<MinInt<X>>>;
#[cfg(test)]
mod test_ratio {
use crate::sequence::tree::ranged_rmq::*;
#[test]
fn it_works() {
let v: Vec<i64> = vec![1, 2, 3, 4];
let mut rmq = RangedRMaxQ::from(v.iter().map(|&x| MaxInt::Val(x)).collect());
assert_eq!(rmq.product(1..3), MaxInt::Val(3));
rmq.update(1..3, Assign::Some(MaxInt::Val(1))); // [1,1,1,4]
assert_eq!(rmq.product(1..3), MaxInt::Val(1));
assert_eq!(rmq.product(2..4), MaxInt::Val(4));
}
}