Struct SegmentTree 

pub struct SegmentTree<T, F> { /* private fields */ }

注意⚠ この実装は遅いので time limit の厳しい問題には代わりに ACL のセグメントツリーを使うこと。

セグメントツリーです。

Implementations

impl<T, F> SegmentTree<T, F>

where T: Clone, F: Fn(&T, &T) -> T,

pub fn new(n: usize, e: T, multiply: F) -> Self

長さ n の列を初期値 e で初期化します。

multiply は fold に使う二項演算です。

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

列の i 番目の要素を取得します。

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

列の i 番目の要素を x で更新します。

pub fn update<U>(&mut self, i: usize, f: U)

where U: FnOnce(&T) -> T,

列の i 番目の要素を f で更新します。

pub fn fold(&self, range: impl RangeBounds<usize>) -> T

range が l..r として、multiply(l番目の要素, multiply(..., multiply(r-2番目の要素, r-1番目の要素))) の値を返します。

pub fn max_right<P>(&self, l: usize, f: P) -> usize

where P: Fn(&T) -> bool,

f(fold(l..r)) = true となる最大の r を返します。

Panics

if f(e) = false

pub fn min_left<P>(&self, r: usize, f: P) -> usize

where P: Fn(&T) -> bool,

f(fold(l..r)) = true となる最小の l を返します。

Panics

if f(e) = false

Trait Implementations

impl<T: Clone, F: Clone> Clone for SegmentTree<T, F>

fn clone(&self) -> SegmentTree<T, F>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T, F> Debug for SegmentTree<T, F>

where T: Debug,

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

Formats the value using the given formatter.

impl<T, F> Index<usize> for SegmentTree<T, F>

where T: Clone, F: Fn(&T, &T) -> T,

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.