dsalgo/
segment_tree_dual_with_static_monoid.rs

1use crate::bit_length_with_count_leading_zeros_usize::bit_length;
2
3pub trait Monoid {
4    type T;
5
6    fn op(
7        l: Self::T,
8        r: Self::T,
9    ) -> Self::T;
10
11    fn e() -> Self::T;
12}
13
14pub struct DualSegtree<G: Monoid> {
15    node: Vec<G::T>,
16    size: usize,
17}
18
19impl<G: Monoid> DualSegtree<G>
20where
21    G::T: Clone,
22{
23    pub fn new(size: usize) -> Self {
24        assert!(size > 0);
25
26        let n = size.next_power_of_two();
27
28        let node = vec![G::e(); n << 1];
29
30        Self { node, size }
31    }
32
33    pub fn size(&self) -> usize {
34        self.size
35    }
36
37    fn n(&self) -> usize {
38        self.node.len() >> 1
39    }
40
41    fn height(&self) -> usize {
42        bit_length(self.n())
43    }
44
45    fn operate_node(
46        &mut self,
47        i: usize,
48        x: G::T,
49    ) {
50        self.node[i] = G::op(self.node[i].clone(), x);
51    }
52
53    fn propagate(
54        &mut self,
55        i: usize,
56    ) {
57        self.operate_node(i << 1, self.node[i].clone());
58
59        self.operate_node(i << 1 | 1, self.node[i].clone());
60
61        self.node[i] = G::e();
62    }
63
64    fn pull(
65        &mut self,
66        i: usize,
67    ) {
68        for j in (1..self.height()).rev() {
69            self.propagate(i >> j);
70        }
71    }
72
73    pub fn get(
74        &mut self,
75        mut i: usize,
76    ) -> &mut G::T {
77        assert!(i < self.size());
78
79        i += self.n();
80
81        self.pull(i);
82
83        &mut self.node[i]
84    }
85
86    pub fn operate(
87        &mut self,
88        mut l: usize,
89        mut r: usize,
90        x: G::T,
91    ) {
92        assert!(l <= r && r <= self.size());
93
94        let n = self.n();
95
96        l += n;
97
98        r += n;
99
100        self.pull(l >> l.trailing_zeros());
101
102        self.pull((r >> r.trailing_zeros()) - 1);
103
104        while l < r {
105            if l & 1 == 1 {
106                self.operate_node(l, x.clone());
107
108                l += 1;
109            }
110
111            if r & 1 == 1 {
112                r -= 1;
113
114                self.operate_node(r, x.clone());
115            }
116
117            l >>= 1;
118
119            r >>= 1;
120        }
121    }
122}
dsalgo/segment_tree_dual_with_static_monoid.rs

dsalgo/
segment_tree_dual_with_static_monoid.rs
