Struct cp_library_rs::data_structure::bit::BIT

pub struct BIT<T: Monoid> {
    pub size: usize,
    /* private fields */
}

BinaryIndexedTree

• 0-indexedなインターフェースを持つBIT

Fields

size: usize

Implementations

impl<T: Monoid> BIT<T>

pub fn new(n: usize) -> Self

BITの初期化を行う

• n: 列の長さ

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

一点加算を行う

• i: 加算を行うインデックス（0-indexed）
• x: 加算する値

pub fn prefix_sum(&self, i: usize) -> T::Val

先頭からの和を求める

• i: 区間[0,i)に対しての総和（0-indexed）

impl<T: Group> BIT<T>

pub fn sum<R: RangeBounds<usize>>(&self, range: R) -> T::Val

任意の区間の和を求める

• range: 区間を表すRangeオブジェクト

impl<T: OrderedMonoid> BIT<T>

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

a_0 + a_1 + ... + a_i >= wとなる最小のiを求める

pub fn upper_bound(&self, w: T::Val) -> usize

a_0 + a_1 + ... + a_i > wとなる最小のiを求める

Trait Implementations

impl<T> Debug for BIT<T>where T: Group, T::Val: Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Monoid> From<&Vec<<T as Monoid>::Val, Global>> for BIT<T>

fn from(src: &Vec<T::Val>) -> Self

ベクターの参照からBITを作成