Struct SegmentTree 

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

モノイド (T, op, identity) 上のセグメント木です。

添字は 0-indexed、区間は半開区間 [left, right) です。op は結合則を満たし、 identity はその単位元である必要があります。op が非可換でも、区間内の左から右の 順序で集約します。構築は O(N)、点更新・区間取得・ 二分探索は O(log N) です。

Examples

use atcoder::data_structure::segment_tree::SegmentTree;

let mut tree = SegmentTree::from_vec([1, 2, 3, 4], |a, b| a + b, 0);
assert_eq!(tree.get(1, 4), 9);
tree.set(2, 10);
assert_eq!(tree.get(0, 3), 13);

Implementations

impl<T: Copy, F: Fn(T, T) -> T> SegmentTree<T, F>

pub fn new(op: F, len: usize, identity: T) -> Self

長さ len、各要素が identity の木を作ります。計算量・メモリ量は O(N) です。

op は結合則を満たし、identity は左右両方の単位元である必要があります。

pub fn from_vec(values: impl Into<Vec<T>>, op: F, identity: T) -> Self

values の配列から木を構築します。計算量・メモリ量は O(N) です。

op は結合則を満たし、identity は左右両方の単位元である必要があります。

pub fn from(op: F, values: Vec<T>, identity: T) -> Self

from_vec と同じです。values の配列から木を構築します。

pub const fn len(&self) -> usize

要素数を返します。

pub const fn is_empty(&self) -> bool

要素がなければ true を返します。

pub fn set(&mut self, index: usize, value: T)

0 始まりの index 番目を value に更新します。計算量は O(log N) です。

index >= len の場合は panic します。

pub fn update(&mut self, index: usize, f: impl FnOnce(T) -> T)

0 始まりの index 番目の現在値を f に渡し、戻り値で更新します。

f は1回だけ呼び出し、更新後は祖先の集約値も再計算します。 計算量は f の実行時間を除いて O(log N) です。index >= len なら f を呼び出す前に panic します。

use atcoder::data_structure::segment_tree::SegmentTree;

let mut seg = SegmentTree::from_vec([1, 2, 3], |a, b| a + b, 0);
seg.update(1, |v| v + 5);
seg.update(2, |v| v.max(10));
assert_eq!(seg.at(1), 7);
assert_eq!(seg.get(0, 3), 18);

pub fn at(&self, index: usize) -> T

0 始まりの index 番目の値を返します。index >= len なら panic します。 計算量は O(1) です。

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

半開区間 [left, right) の集約値を返します。

添字は 0 始まりです。left > right または right > len の場合は panic します。 空区間には単位元を返します。計算量は O(log N) です。

pub fn max_right<P>(&self, left: usize, predicate: P) -> usize

where P: Fn(T) -> bool,

predicate(get(left, right)) が真である最大の right を返します。

predicate(identity) は真で、右端を伸ばしたとき述語が真から偽へ高々一度だけ 変化する必要があります。集約は op の左から右の順で行います。 返り値は left..right が条件を満たす最大の right です。left > len なら panic します。

pub fn min_left<P>(&self, right: usize, predicate: P) -> usize

where P: Fn(T) -> bool,

predicate(get(left, right)) が真である最小の left を返します。

predicate(identity) は真で、左端を左へ動かしたとき述語が真から偽へ高々一度だけ 変化する必要があります。集約は op の左から右の順で行います。 返り値は left..right が条件を満たす最小の left です。right > len なら panic します。

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

pub fn debug_values(&self)

葉のうち、元配列に対応する要素だけをデバッグ出力します。 出力先や書式は crate::debug! マクロの設定に従います。

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> Index<usize> for SegmentTree<T, F>

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.