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

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§

source§

impl<M> VecSegtree<M>where M: Monoid, M::Set: Clone,

source

pub fn new(len: usize) -> Selfwhere M: Default,

source

pub fn is_empty(&self) -> bool

source

pub fn len(&self) -> usize

Trait Implementations§

source§

impl<M> Clone for VecSegtree<M>where M: Monoid + Clone, M::Set: Clone + Clone,

source§

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

Returns a copy of the value. Read more
1.0.0 · source§

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

Performs copy-assignment from source. Read more
source§

impl<M> Debug for VecSegtree<M>where M: Monoid, M::Set: Clone + Debug,

source§

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

Formats the value using the given formatter. Read more
source§

impl<M> Default for VecSegtree<M>where M: Monoid + Default, M::Set: Clone,

source§

fn default() -> Self

Returns the “default value” for a type. Read more
source§

impl<M, B> Fold<B> for VecSegtree<M>where M: Monoid, M::Set: Clone, B: RangeBounds<usize>,

§

type Output = M

source§

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

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

impl<M> FoldBisect for VecSegtree<M>where M: Monoid, M::Set: Clone,

source§

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

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

impl<M> FoldBisectRev for VecSegtree<M>where M: Monoid, M::Set: Clone,

source§

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

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

impl<M> From<(Vec<<M as Magma>::Set, Global>, M)> for VecSegtree<M>where M: Monoid, M::Set: Clone,

source§

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

Converts to this type from the input type.
source§

impl<M> From<Vec<<M as Magma>::Set, Global>> for VecSegtree<M>where M: Monoid + Default, M::Set: Clone,

source§

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

Converts to this type from the input type.
source§

impl<M> From<VecSegtree<M>> for Vec<M::Set>where M: Monoid, M::Set: Clone,

source§

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

Converts to this type from the input type.
source§

impl<'a, M> GetMut<'a> for VecSegtree<M>where M: Monoid + 'a, M::Set: Clone,

§

type Output = GetMutIndex<'a, M>

source§

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

source§

impl<M> Index<usize> for VecSegtree<M>where M: Monoid, M::Set: Clone,

§

type Output = <M as Magma>::Set

The returned type after indexing.
source§

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

Performs the indexing (container[index]) operation. Read more
source§

impl<M> SetValue<usize> for VecSegtree<M>where M: Monoid, M::Set: Clone,

§

type Input = <M as Magma>::Set

代入される型。
source§

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

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

Auto Trait Implementations§

§

impl<M> RefUnwindSafe for VecSegtree<M>where M: RefUnwindSafe, <M as Magma>::Set: RefUnwindSafe,

§

impl<M> Send for VecSegtree<M>where M: Send, <M as Magma>::Set: Send,

§

impl<M> Sync for VecSegtree<M>where M: Sync, <M as Magma>::Set: Sync,

§

impl<M> Unpin for VecSegtree<M>where M: Unpin, <M as Magma>::Set: Unpin,

§

impl<M> UnwindSafe for VecSegtree<M>where M: UnwindSafe, <M as Magma>::Set: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T> ToOwned for Twhere T: Clone,

§

type Owned = T

The resulting type after obtaining ownership.
source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for Twhere V: MultiLane<T>,

§

fn vzip(self) -> V