competitive::data_structure::dual_segment_tree

Struct DualSegmentTree

pub struct DualSegmentTree<M>where
    M: MonoidAct,{
    n: usize,
    keys: Vec<M::Key>,
    lazy: Vec<M::Act>,
}

Fields§

§n: usize§keys: Vec<M::Key>§lazy: Vec<M::Act>

Implementations§

Source §

impl<M> DualSegmentTree<M>
where M: MonoidAct<Key: Clone, Act: PartialEq>,

Source

pub fn new(len: usize, key: M::Key) -> Self

Source

pub fn from_keys(keys: impl ExactSizeIterator<Item = M::Key>) -> Self

Examples found in repository ?

crates/library_checker/src/data_structure/range_affine_point_get.rs (line 17)

14pub fn range_affine_point_get(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, a: [M; iter n]);
17    let mut seg = DualSegmentTree::<LinearAct<_>>::from_keys(a);
18    for _ in 0..q {
19        sc!(query: Query);
20        match query {
21            Query::Update { l, r, bc } => seg.update(l..r, bc),
22            Query::Get { i } => {
23                pp!(seg.get(i));
24            }
25        };
26    }
27}

Source

fn update_at(&mut self, k: usize, a: &M::Act)

Examples found in repository ?

crates/competitive/src/data_structure/dual_segment_tree.rs (line 74)

71    fn propagate_at(&mut self, k: usize) {
72        let a = replace(&mut self.lazy[k], M::unit());
73        if !M::ActMonoid::is_unit(&a) {
74            self.update_at(2 * k, &a);
75            self.update_at(2 * k + 1, &a);
76        }
77    }
78    pub fn update<R>(&mut self, range: R, a: M::Act)
79    where
80        R: RangeBounds<usize>,
81    {
82        let range = range
83            .to_range_bounded(0, self.keys.len())
84            .expect("invalid range");
85        if range.is_empty() || M::ActMonoid::is_unit(&a) {
86            return;
87        }
88        let mut l = range.start + self.n;
89        let mut r = range.end + self.n;
90        for i in (1..=self.n.trailing_zeros()).rev() {
91            if (l >> i) << i != l {
92                self.propagate_at(l >> i);
93            }
94            if (r >> i) << i != r && ((l >> i) << i == l || l >> i != (r - 1) >> i) {
95                self.propagate_at((r - 1) >> i);
96            }
97        }
98        while l < r {
99            if l & 1 != 0 {
100                self.update_at(l, &a);
101                l += 1;
102            }
103            if r & 1 != 0 {
104                r -= 1;
105                self.update_at(r, &a);
106            }
107            l >>= 1;
108            r >>= 1;
109        }
110    }

Source

fn propagate_at(&mut self, k: usize)

Examples found in repository ?

crates/competitive/src/data_structure/dual_segment_tree.rs (line 92)

78    pub fn update<R>(&mut self, range: R, a: M::Act)
79    where
80        R: RangeBounds<usize>,
81    {
82        let range = range
83            .to_range_bounded(0, self.keys.len())
84            .expect("invalid range");
85        if range.is_empty() || M::ActMonoid::is_unit(&a) {
86            return;
87        }
88        let mut l = range.start + self.n;
89        let mut r = range.end + self.n;
90        for i in (1..=self.n.trailing_zeros()).rev() {
91            if (l >> i) << i != l {
92                self.propagate_at(l >> i);
93            }
94            if (r >> i) << i != r && ((l >> i) << i == l || l >> i != (r - 1) >> i) {
95                self.propagate_at((r - 1) >> i);
96            }
97        }
98        while l < r {
99            if l & 1 != 0 {
100                self.update_at(l, &a);
101                l += 1;
102            }
103            if r & 1 != 0 {
104                r -= 1;
105                self.update_at(r, &a);
106            }
107            l >>= 1;
108            r >>= 1;
109        }
110    }
111    pub fn get(&self, k: usize) -> M::Key {
112        let mut value = self.keys[k].clone();
113        let mut k = (k + self.n) >> 1;
114        while k > 0 {
115            value = M::act(&value, &self.lazy[k]);
116            k >>= 1;
117        }
118        value
119    }
120    pub fn set(&mut self, k: usize, value: M::Key) {
121        assert!(k < self.keys.len());
122        let index = k + self.n;
123        for i in (1..=self.n.trailing_zeros()).rev() {
124            self.propagate_at(index >> i);
125        }
126        self.keys[k] = value;
127    }

Source

pub fn update<R>(&mut self, range: R, a: M::Act)
where R: RangeBounds<usize>,

Examples found in repository ?

crates/library_checker/src/data_structure/range_affine_point_get.rs (line 21)

14pub fn range_affine_point_get(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, a: [M; iter n]);
17    let mut seg = DualSegmentTree::<LinearAct<_>>::from_keys(a);
18    for _ in 0..q {
19        sc!(query: Query);
20        match query {
21            Query::Update { l, r, bc } => seg.update(l..r, bc),
22            Query::Get { i } => {
23                pp!(seg.get(i));
24            }
25        };
26    }
27}

Source

pub fn get(&self, k: usize) -> M::Key

Examples found in repository ?

crates/library_checker/src/data_structure/range_affine_point_get.rs (line 23)

14pub fn range_affine_point_get(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, a: [M; iter n]);
17    let mut seg = DualSegmentTree::<LinearAct<_>>::from_keys(a);
18    for _ in 0..q {
19        sc!(query: Query);
20        match query {
21            Query::Update { l, r, bc } => seg.update(l..r, bc),
22            Query::Get { i } => {
23                pp!(seg.get(i));
24            }
25        };
26    }
27}