Struct VecSegtree 

pub struct VecSegtree<M>
where
    M: Monoid,
    M::Set: Clone,
{ /* private fields */ }

Vec ベースのセグ木。

非再帰実装かつ配列サイズを $2n$ とするセグ木。 モノイドを対象として要素の取得・更新および任意区間のモノイド積を処理する。 加えて、モノイド積を引数とする述語に対して、それが真となる区間の境界を求められる。

Complexity

演算	時間計算量
new, from	$\Theta(n)$
index	$\Theta(1)$
set_value	$\Theta(\log(n))$
区間 $[l, r)$ の fold	$\Theta(\log(r-l))$
fold_bisect, fold_bisect_rev	$O(\log(n))$

Examples

use nekolib::ds::VecSegtree;
use nekolib::traits::{Fold, FoldBisect, FoldBisectRev, GetMut};
use nekolib::utils::OpAdd;

let mut vs: VecSegtree<OpAdd<i32>> = vec![2, 4, 7, 3, 5].into();
assert_eq!(vs.fold(1..3), 11);
assert_eq!(vs.fold(..), 21);

*vs.get_mut(2).unwrap() = 1; // [2, 4, 1, 3, 5]
assert_eq!(vs.fold(1..3), 5);
assert_eq!(vs.fold(1..=3), 8);
assert_eq!(vs.fold_bisect(1, |&x| x < 4), (1_usize, 0));
assert_eq!(vs.fold_bisect(1, |&x| x <= 4), (2_usize, 4));
assert_eq!(vs.fold_bisect(1, |&x| x < 13), (4_usize, 8));
assert_eq!(vs.fold_bisect(1, |&x| x <= 13), (5_usize, 13));

assert_eq!(vs.fold(..), 15);
assert_eq!(vs.fold_bisect_rev(5, |&x| x <= 0), (5_usize, 0));
assert_eq!(vs.fold_bisect_rev(5, |&x| x < 15), (1_usize, 13));
assert_eq!(vs.fold_bisect_rev(5, |&x| x <= 15), (0_usize, 15));

let l = 1;
let pred = |&x: &i32| x <= 12;
let (r, x) = vs.fold_bisect(l, pred);
assert_eq!(vs.fold(l..r), x);
assert!(pred(&x));
assert!(r == vs.len() || !pred(&vs.fold(l..r + 1)));

let r = 5;
let pred = |&x: &i32| x <= 12;
let (l, x) = vs.fold_bisect_rev(r, pred);
assert_eq!(vs.fold(l..r), x);
assert!(pred(&x));
assert!(l == 0 || !pred(&vs.fold(l - 1..r)));

Implementations

impl<M> VecSegtree<M>

where M: Monoid, M::Set: Clone,

pub fn new(len: usize) -> Self

where M: Default,

pub fn is_empty(&self) -> bool

pub fn len(&self) -> usize

Trait Implementations

impl<M> Clone for VecSegtree<M>

where M: Monoid + Clone, M::Set: Clone + Clone,

fn clone(&self) -> VecSegtree<M>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<M> Debug for VecSegtree<M>

where M: Monoid, M::Set: Clone + Debug,

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

Formats the value using the given formatter.

impl<M> Default for VecSegtree<M>

where M: Monoid + Default, M::Set: Clone,

fn default() -> Self

Returns the “default value” for a type.

impl<M, B> Fold<B> for VecSegtree<M>

where M: Monoid, M::Set: Clone, B: RangeBounds<usize>,

type Output = M

fn fold(&self, b: B) -> M::Set

r で指定される区間の和を返す。

impl<M> FoldBisect for VecSegtree<M>

where M: Monoid, M::Set: Clone,

fn fold_bisect<F>(&self, l: usize, pred: F) -> (usize, M::Set)

where F: Fn(&M::Set) -> bool,

添字 l と述語 pred を引数に取り、次の条件を満たす r を返す。 ただし、区間長を n とする。

impl<M> FoldBisectRev for VecSegtree<M>

where M: Monoid, M::Set: Clone,

fn fold_bisect_rev<F>(&self, r: usize, pred: F) -> (usize, M::Set)

where F: Fn(&M::Set) -> bool,

添字 r と述語 pred を引数に取り、次の条件を満たす l を返す。

impl<M> From<(Vec<<M as Magma>::Set>, M)> for VecSegtree<M>

where M: Monoid, M::Set: Clone,

fn from((v, monoid): (Vec<M::Set>, M)) -> Self

Converts to this type from the input type.

impl<M> From<Vec<<M as Magma>::Set>> for VecSegtree<M>

where M: Monoid + Default, M::Set: Clone,

fn from(v: Vec<M::Set>) -> Self

Converts to this type from the input type.

impl<M> From<VecSegtree<M>> for Vec<M::Set>

where M: Monoid, M::Set: Clone,

fn from(v: VecSegtree<M>) -> Self

Converts to this type from the input type.

impl<'a, M> GetMut<'a> for VecSegtree<M>

where M: Monoid + 'a, M::Set: Clone,

type Output = GetMutIndex<'a, M>

fn get_mut(&'a mut self, index: usize) -> Option<GetMutIndex<'a, M>>

impl<M> Index<usize> for VecSegtree<M>

where M: Monoid, M::Set: Clone,

type Output = <M as Magma>::Set

The returned type after indexing.

fn index(&self, i: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<M> SetValue<usize> for VecSegtree<M>

where M: Monoid, M::Set: Clone,

type Input = <M as Magma>::Set

代入される型。

fn set_value(&mut self, i: usize, x: Self::Input)

i で指定される要素に x を代入する。