モノイド \((X, \times)\) とその上のモノイド(右)作用 \(M\) があるとする.
\[\ast \colon X \times M \to X\]ただし次の準同型を要請する.
このとき \(X\) 上の数列
\[(x_1, \ldots, x_N \mid x_i \in X)\]について, 次の操作がそれぞれ \(O(\log N)\) で出来る.
セグメントツリー では一点に対する代入だったものを, 区間すべての要素に対するモノイド作用に一般化されてある.
/// Sequence - Lazy Segment Tree
use crate::algebra::act::*;
use crate::algebra::monoid::*;
#[derive(Debug, Clone)]
pub struct LazySegmentTree<X, M> {
length: usize, // of leaves
length_upper: usize, // power of 2
size: usize, // of nodes
data: Vec<X>,
act: Vec<M>,
}
impl<X: Copy + Monoid, M: Copy + Monoid + Act<X>> LazySegmentTree<X, M> {
pub fn new(length: usize) -> Self {
let mut length_upper = 1;
while length_upper < length {
length_upper *= 2;
}
let size = length_upper * 2 - 1;
let data = vec![X::one(); size];
let act = vec![M::one(); size];
LazySegmentTree {
length,
length_upper,
size,
data,
act,
}
}
pub fn from(xs: Vec<X>) -> Self {
let mut tree = Self::new(xs.len());
for i in 0..xs.len() {
tree.data[tree.size / 2 + i] = xs[i];
}
for i in (0..tree.size / 2).rev() {
tree.data[i] = tree.data[2 * i + 1] * tree.data[2 * i + 2];
}
tree
}
fn propagation(&mut self, idx: usize) {
if idx < self.size / 2 {
self.act[idx * 2 + 1] = self.act[idx * 2 + 1] * self.act[idx];
self.act[idx * 2 + 2] = self.act[idx * 2 + 2] * self.act[idx];
}
self.data[idx] = self.act[idx].act(self.data[idx]);
self.act[idx] = M::one();
}
fn update_sub(
&mut self,
range: std::ops::Range<usize>,
m: M,
idx: usize,
focus: std::ops::Range<usize>,
) {
self.propagation(idx);
if focus.end <= range.start || range.end <= focus.start {
return;
}
if range.start <= focus.start && focus.end <= range.end {
self.act[idx] = self.act[idx] * m;
self.propagation(idx);
} else if idx < self.data.len() / 2 {
let mid = (focus.start + focus.end) / 2;
self.update_sub(range.clone(), m, idx * 2 + 1, focus.start..mid);
self.update_sub(range.clone(), m, idx * 2 + 2, mid..focus.end);
self.data[idx] = self.data[idx * 2 + 1] * self.data[idx * 2 + 2];
}
}
pub fn update(&mut self, range: std::ops::Range<usize>, m: M) {
self.update_sub(range, m, 0, 0..self.length_upper);
}
fn product_sub(
&mut self,
range: std::ops::Range<usize>,
idx: usize,
focus: std::ops::Range<usize>,
) -> X {
self.propagation(idx);
if focus.end <= range.start || range.end <= focus.start {
X::one()
} else if range.start <= focus.start && focus.end <= range.end {
self.data[idx]
} else {
let mid = (focus.start + focus.end) / 2;
let a = self.product_sub(range.clone(), idx * 2 + 1, focus.start..mid);
let b = self.product_sub(range.clone(), idx * 2 + 2, mid..focus.end);
a * b
}
}
pub fn product(&mut self, range: std::ops::Range<usize>) -> X {
self.product_sub(range, 0, 0..self.length_upper)
}
pub fn index(&mut self, i: usize) -> X {
self.product(i..i + 1)
}
pub fn to_vec(&mut self) -> Vec<X> {
(0..self.length).map(|i| self.index(i)).collect()
}
}
impl<X: std::fmt::Debug, M: std::fmt::Debug> LazySegmentTree<X, M> {
pub fn debug(&self) {
#[cfg(debug_assertions)]
for i in 0..self.size {
if i > 0 && (i + 1).count_ones() == 1 {
eprintln!();
}
eprint!("{:?} / {:?}; ", &self.data[i], &self.act[i]);
}
eprintln!();
}
}