Struct FenwickTreeAdd

pub struct FenwickTreeAdd<T> { /* private fields */ }

可換な加減算に特化したFenwickTree

Implementations

impl<T> FenwickTreeAdd<T>

where T: Copy + Zero + Add<Output = T> + Sub<Output = T>,

pub fn new(size: usize) -> Self

長さsizeのFenwickTreeAdd<T>を生成する。

pub fn sub(&mut self, i: usize, value: T)

i番目の値からvalueを引く。

Time complexity $O(\log n)$

pub fn add(&mut self, i: usize, value: T)

i番目の値にvalueを足す。

Time complexity $O(\log n)$

pub fn fold_to(&self, _: RangeTo<usize>) -> T

範囲0..rの総和を返す。

Time complexity $O(\log n)$

pub fn fold(&self, _: Range<usize>) -> T

範囲l..rの総和を返す。

Time complexity $O(\log n)$

impl<T> FenwickTreeAdd<T>

where T: Copy + Zero + Add<Output = T> + Sub<Output = T> + Ord,

pub fn lower_bound(&self, value: T) -> usize

列の接頭辞の総和が単調増加であるとき、接頭辞の総和がvalue以上となる位置を返す。