Struct DualSegmentTree 

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

半開区間への作用と一点取得を扱う双対セグメント木です。

添字は 0-indexed、区間は [left, right) です。compose(old, new) は古い作用の後に 新しい作用を適用した合成を返し、結合則と単位元 identity を満たす必要があります。 作用が非可換でも、この順序を守れば扱えます。更新と取得はいずれも O(log N) です。

Examples

use atcoder::data_structure::dual_segment_tree::DualSegmentTree;

let mut tree = DualSegmentTree::new(|a, b| a + b, 4, 0);
tree.apply(1, 4, 3);
tree.apply(2, 3, 2);
assert_eq!(tree.get(2), 5);

Implementations

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

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

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

compose(old, new) は、点に蓄積済みの作用 old の後に新しい作用 new を 適用した合成を返す関数です。identity はこの関数の単位元である必要があります。

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

各点の初期値を指定して木を構築します。計算量・メモリ量は O(N) です。

values[i] が添字 i の初期値になります。compose と identity の条件は new と同じです。

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

from_vec と同じです。各点の初期値を values で指定します。

pub fn apply(&mut self, left: usize, right: usize, value: T)

半開区間 [left, right) の各点に value を適用します。

添字は 0 始まりです。範囲が 0..=len を外れる、または left > right の場合は panic します。空区間なら何もしません。各点では既存の作用の後に value を適用します。 計算量は O(log N) です。

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

index 番目の値を返します。添字は 0 始まりで、index >= len なら panic します。 蓄積された作用を古いものから新しいものの順に合成します。計算量は O(log N) です。

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

index 番目の値を返します。添字は 0 始まりです。

get と同じで、index >= len なら panic します。計算量は O(log N) です。

Trait Implementations

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

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.