いもす法

いもす法とは

累積和の応用であり、ある区間に一定値を足す操作を複数回高速でするアルゴリズムである。

実装

let mut imos = vec![0; 2 * 10usize.pow(5) + 2];
for &(s, t, p) in &stp {
    imos[s] += p as isize;
    imos[t] -= p as isize;
}

let mut need = vec![];
for &i in &imos {
    need.push(need.last().unwrap_or(&0) + i);
}

色々と1次元以外にも応用が効くらしいです。