Struct CartesianTree

pub struct CartesianTree<T> {
    pub n: usize,
    pub root: usize,
    pub parent: Vec<Option<usize>>,
    pub left: Vec<Option<usize>>,
    pub right: Vec<Option<usize>>,
    /* private fields */
}

CartesianTree

inorder が元配列の順になる（二分木としての中順走査が 0..n-1）

build_max は max-heap（親の値 (\ge) 子の値）． build_min は min-heap（親の値 (\le) 子の値）．

Fields

n: usize

root: usize

parent: Vec<Option<usize>>

left: Vec<Option<usize>>

right: Vec<Option<usize>>

Implementations

impl<T: Ord> CartesianTree<T>

pub fn build_by<F>(arr: &[T], should_pop: F) -> Self

where F: FnMut(&T, &T) -> bool,

共通実装．

should_pop(top, cur) が true の間，スタックを pop する．

pub fn build_max(arr: &[T]) -> Self

max-heap の Cartesian Tree を構築する（同値は右側優先）．

すなわち，区間の最大値（同値なら最右）を根にして再帰分割した木になる．

pub fn build_min(arr: &[T]) -> Self

min-heap の Cartesian Tree を構築する（同値は右側優先）．

すなわち，区間の最小値（同値なら最右）を根にして再帰分割した木になる．

Trait Implementations

impl<T: Clone> Clone for CartesianTree<T>

fn clone(&self) -> CartesianTree<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for CartesianTree<T>

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

Formats the value using the given formatter.