Skip to main content

PersistentSegmentTree

competitive::data_structure::persistent_segment_tree

Struct PersistentSegmentTree 

Source 
pub struct PersistentSegmentTree<M>
where
    M: Monoid,
{
    len: usize,
    version_roots: Vec<Option<NonNull<Node<M::T>>>>,
    allocator: MemoryPool<Node<M::T>>,
}

Fields§

§len: usize§version_roots: Vec<Option<NonNull<Node<M::T>>>>§allocator: MemoryPool<Node<M::T>>

Implementations§

Source§

impl<M> PersistentSegmentTree<M>
where M: Monoid,

Source

pub fn new(len: usize) -> Self

Source

pub fn base(&self) -> PersistentSegmentTreeVersion

Source

pub fn len(&self) -> usize

Source

pub fn is_empty(&self) -> bool

Source

fn version_root( &self, version: PersistentSegmentTreeVersion, ) -> Option<NonNull<Node<M::T>>>

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 229)
222    pub fn set(
223        &mut self,
224        version: PersistentSegmentTreeVersion,
225        index: usize,
226        value: M::T,
227    ) -> PersistentSegmentTreeVersion {
228        assert!(index < self.len);
229        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
230        self.push_version_root(root)
231    }
232
233    pub fn update(
234        &mut self,
235        version: PersistentSegmentTreeVersion,
236        index: usize,
237        value: M::T,
238    ) -> PersistentSegmentTreeVersion {
239        assert!(index < self.len);
240        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
241        self.push_version_root(root)
242    }
243
244    #[must_use]
245    pub fn get(&self, version: PersistentSegmentTreeVersion, index: usize) -> M::T {
246        assert!(index < self.len);
247        Self::point_get_dfs(self.version_root(version), 0, self.len, index)
248    }
249
250    #[must_use]
251    pub fn fold<R>(&self, version: PersistentSegmentTreeVersion, range: R) -> M::T
252    where
253        R: RangeBounds<usize>,
254    {
255        let range = range.to_range_bounded(0, self.len).expect("invalid range");
256        if range.is_empty() {
257            M::unit()
258        } else {
259            Self::fold_dfs(self.version_root(version), 0, self.len, &range)
260        }
261    }
262
263    #[must_use]
264    pub fn fold_all(&self, version: PersistentSegmentTreeVersion) -> M::T {
265        Self::subtree_value(self.version_root(version))
266    }
Source

fn push_version_root( &mut self, root: Option<NonNull<Node<M::T>>>, ) -> PersistentSegmentTreeVersion

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 219)
212    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
213        assert_eq!(v.len(), self.len);
214        let root = if self.len == 0 {
215            None
216        } else {
217            self.build_dfs(0, self.len, &v)
218        };
219        self.push_version_root(root)
220    }
221
222    pub fn set(
223        &mut self,
224        version: PersistentSegmentTreeVersion,
225        index: usize,
226        value: M::T,
227    ) -> PersistentSegmentTreeVersion {
228        assert!(index < self.len);
229        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
230        self.push_version_root(root)
231    }
232
233    pub fn update(
234        &mut self,
235        version: PersistentSegmentTreeVersion,
236        index: usize,
237        value: M::T,
238    ) -> PersistentSegmentTreeVersion {
239        assert!(index < self.len);
240        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
241        self.push_version_root(root)
242    }
Source

fn allocate_node( &mut self, children: [Option<NonNull<Node<M::T>>>; 2], value: M::T, ) -> NonNull<Node<M::T>>

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 113)
112    fn leaf_node(&mut self, value: M::T) -> NodePtr<M::T> {
113        Some(self.allocate_node([None, None], value))
114    }
115
116    fn merge_nodes(&mut self, left: NodePtr<M::T>, right: NodePtr<M::T>) -> NodePtr<M::T> {
117        if left.is_none() && right.is_none() {
118            None
119        } else {
120            let value = M::operate(&Self::subtree_value(left), &Self::subtree_value(right));
121            Some(self.allocate_node([left, right], value))
122        }
123    }
Source

fn build_dfs( &mut self, start: usize, end: usize, values: &[M::T], ) -> Option<NonNull<Node<M::T>>>

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 107)
102    fn build_dfs(&mut self, start: usize, end: usize, values: &[M::T]) -> NodePtr<M::T> {
103        if end - start == 1 {
104            return self.leaf_node(values[start].clone());
105        }
106        let mid = (start + end) / 2;
107        let left = self.build_dfs(start, mid, values);
108        let right = self.build_dfs(mid, end, values);
109        self.merge_nodes(left, right)
110    }
111
112    fn leaf_node(&mut self, value: M::T) -> NodePtr<M::T> {
113        Some(self.allocate_node([None, None], value))
114    }
115
116    fn merge_nodes(&mut self, left: NodePtr<M::T>, right: NodePtr<M::T>) -> NodePtr<M::T> {
117        if left.is_none() && right.is_none() {
118            None
119        } else {
120            let value = M::operate(&Self::subtree_value(left), &Self::subtree_value(right));
121            Some(self.allocate_node([left, right], value))
122        }
123    }
124
125    fn subtree_value(node: NodePtr<M::T>) -> M::T {
126        node.map(|node| unsafe { node.as_ref().value.clone() })
127            .unwrap_or_else(M::unit)
128    }
129
130    fn children(node: NodePtr<M::T>) -> [NodePtr<M::T>; 2] {
131        node.map(|node| unsafe { node.as_ref().children })
132            .unwrap_or([None, None])
133    }
134
135    fn point_get_dfs(node: NodePtr<M::T>, start: usize, end: usize, index: usize) -> M::T {
136        let Some(node) = node else {
137            return M::unit();
138        };
139        let node = unsafe { node.as_ref() };
140        if end - start == 1 {
141            node.value.clone()
142        } else {
143            let mid = (start + end) / 2;
144            if index < mid {
145                Self::point_get_dfs(node.children[0], start, mid, index)
146            } else {
147                Self::point_get_dfs(node.children[1], mid, end, index)
148            }
149        }
150    }
151
152    fn fold_dfs(node: NodePtr<M::T>, start: usize, end: usize, range: &Range<usize>) -> M::T {
153        if range.end <= start || end <= range.start {
154            return M::unit();
155        }
156        let Some(node) = node else {
157            return M::unit();
158        };
159        let node = unsafe { node.as_ref() };
160        if range.start <= start && end <= range.end {
161            node.value.clone()
162        } else {
163            let mid = (start + end) / 2;
164            let left = Self::fold_dfs(node.children[0], start, mid, range);
165            let right = Self::fold_dfs(node.children[1], mid, end, range);
166            M::operate(&left, &right)
167        }
168    }
169
170    fn set_dfs(
171        &mut self,
172        node: NodePtr<M::T>,
173        start: usize,
174        end: usize,
175        index: usize,
176        value: &M::T,
177    ) -> NodePtr<M::T> {
178        if end - start == 1 {
179            return self.leaf_node(value.clone());
180        }
181        let mid = (start + end) / 2;
182        let mut children = Self::children(node);
183        if index < mid {
184            children[0] = self.set_dfs(children[0], start, mid, index, value);
185        } else {
186            children[1] = self.set_dfs(children[1], mid, end, index, value);
187        }
188        self.merge_nodes(children[0], children[1])
189    }
190
191    fn update_dfs(
192        &mut self,
193        node: NodePtr<M::T>,
194        start: usize,
195        end: usize,
196        index: usize,
197        value: &M::T,
198    ) -> NodePtr<M::T> {
199        if end - start == 1 {
200            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
201        }
202        let mid = (start + end) / 2;
203        let mut children = Self::children(node);
204        if index < mid {
205            children[0] = self.update_dfs(children[0], start, mid, index, value);
206        } else {
207            children[1] = self.update_dfs(children[1], mid, end, index, value);
208        }
209        self.merge_nodes(children[0], children[1])
210    }
211
212    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
213        assert_eq!(v.len(), self.len);
214        let root = if self.len == 0 {
215            None
216        } else {
217            self.build_dfs(0, self.len, &v)
218        };
219        self.push_version_root(root)
220    }
Source

fn leaf_node(&mut self, value: M::T) -> Option<NonNull<Node<M::T>>>

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 104)
102    fn build_dfs(&mut self, start: usize, end: usize, values: &[M::T]) -> NodePtr<M::T> {
103        if end - start == 1 {
104            return self.leaf_node(values[start].clone());
105        }
106        let mid = (start + end) / 2;
107        let left = self.build_dfs(start, mid, values);
108        let right = self.build_dfs(mid, end, values);
109        self.merge_nodes(left, right)
110    }
111
112    fn leaf_node(&mut self, value: M::T) -> NodePtr<M::T> {
113        Some(self.allocate_node([None, None], value))
114    }
115
116    fn merge_nodes(&mut self, left: NodePtr<M::T>, right: NodePtr<M::T>) -> NodePtr<M::T> {
117        if left.is_none() && right.is_none() {
118            None
119        } else {
120            let value = M::operate(&Self::subtree_value(left), &Self::subtree_value(right));
121            Some(self.allocate_node([left, right], value))
122        }
123    }
124
125    fn subtree_value(node: NodePtr<M::T>) -> M::T {
126        node.map(|node| unsafe { node.as_ref().value.clone() })
127            .unwrap_or_else(M::unit)
128    }
129
130    fn children(node: NodePtr<M::T>) -> [NodePtr<M::T>; 2] {
131        node.map(|node| unsafe { node.as_ref().children })
132            .unwrap_or([None, None])
133    }
134
135    fn point_get_dfs(node: NodePtr<M::T>, start: usize, end: usize, index: usize) -> M::T {
136        let Some(node) = node else {
137            return M::unit();
138        };
139        let node = unsafe { node.as_ref() };
140        if end - start == 1 {
141            node.value.clone()
142        } else {
143            let mid = (start + end) / 2;
144            if index < mid {
145                Self::point_get_dfs(node.children[0], start, mid, index)
146            } else {
147                Self::point_get_dfs(node.children[1], mid, end, index)
148            }
149        }
150    }
151
152    fn fold_dfs(node: NodePtr<M::T>, start: usize, end: usize, range: &Range<usize>) -> M::T {
153        if range.end <= start || end <= range.start {
154            return M::unit();
155        }
156        let Some(node) = node else {
157            return M::unit();
158        };
159        let node = unsafe { node.as_ref() };
160        if range.start <= start && end <= range.end {
161            node.value.clone()
162        } else {
163            let mid = (start + end) / 2;
164            let left = Self::fold_dfs(node.children[0], start, mid, range);
165            let right = Self::fold_dfs(node.children[1], mid, end, range);
166            M::operate(&left, &right)
167        }
168    }
169
170    fn set_dfs(
171        &mut self,
172        node: NodePtr<M::T>,
173        start: usize,
174        end: usize,
175        index: usize,
176        value: &M::T,
177    ) -> NodePtr<M::T> {
178        if end - start == 1 {
179            return self.leaf_node(value.clone());
180        }
181        let mid = (start + end) / 2;
182        let mut children = Self::children(node);
183        if index < mid {
184            children[0] = self.set_dfs(children[0], start, mid, index, value);
185        } else {
186            children[1] = self.set_dfs(children[1], mid, end, index, value);
187        }
188        self.merge_nodes(children[0], children[1])
189    }
190
191    fn update_dfs(
192        &mut self,
193        node: NodePtr<M::T>,
194        start: usize,
195        end: usize,
196        index: usize,
197        value: &M::T,
198    ) -> NodePtr<M::T> {
199        if end - start == 1 {
200            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
201        }
202        let mid = (start + end) / 2;
203        let mut children = Self::children(node);
204        if index < mid {
205            children[0] = self.update_dfs(children[0], start, mid, index, value);
206        } else {
207            children[1] = self.update_dfs(children[1], mid, end, index, value);
208        }
209        self.merge_nodes(children[0], children[1])
210    }
Source

fn merge_nodes( &mut self, left: Option<NonNull<Node<M::T>>>, right: Option<NonNull<Node<M::T>>>, ) -> Option<NonNull<Node<M::T>>>

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 109)
102    fn build_dfs(&mut self, start: usize, end: usize, values: &[M::T]) -> NodePtr<M::T> {
103        if end - start == 1 {
104            return self.leaf_node(values[start].clone());
105        }
106        let mid = (start + end) / 2;
107        let left = self.build_dfs(start, mid, values);
108        let right = self.build_dfs(mid, end, values);
109        self.merge_nodes(left, right)
110    }
111
112    fn leaf_node(&mut self, value: M::T) -> NodePtr<M::T> {
113        Some(self.allocate_node([None, None], value))
114    }
115
116    fn merge_nodes(&mut self, left: NodePtr<M::T>, right: NodePtr<M::T>) -> NodePtr<M::T> {
117        if left.is_none() && right.is_none() {
118            None
119        } else {
120            let value = M::operate(&Self::subtree_value(left), &Self::subtree_value(right));
121            Some(self.allocate_node([left, right], value))
122        }
123    }
124
125    fn subtree_value(node: NodePtr<M::T>) -> M::T {
126        node.map(|node| unsafe { node.as_ref().value.clone() })
127            .unwrap_or_else(M::unit)
128    }
129
130    fn children(node: NodePtr<M::T>) -> [NodePtr<M::T>; 2] {
131        node.map(|node| unsafe { node.as_ref().children })
132            .unwrap_or([None, None])
133    }
134
135    fn point_get_dfs(node: NodePtr<M::T>, start: usize, end: usize, index: usize) -> M::T {
136        let Some(node) = node else {
137            return M::unit();
138        };
139        let node = unsafe { node.as_ref() };
140        if end - start == 1 {
141            node.value.clone()
142        } else {
143            let mid = (start + end) / 2;
144            if index < mid {
145                Self::point_get_dfs(node.children[0], start, mid, index)
146            } else {
147                Self::point_get_dfs(node.children[1], mid, end, index)
148            }
149        }
150    }
151
152    fn fold_dfs(node: NodePtr<M::T>, start: usize, end: usize, range: &Range<usize>) -> M::T {
153        if range.end <= start || end <= range.start {
154            return M::unit();
155        }
156        let Some(node) = node else {
157            return M::unit();
158        };
159        let node = unsafe { node.as_ref() };
160        if range.start <= start && end <= range.end {
161            node.value.clone()
162        } else {
163            let mid = (start + end) / 2;
164            let left = Self::fold_dfs(node.children[0], start, mid, range);
165            let right = Self::fold_dfs(node.children[1], mid, end, range);
166            M::operate(&left, &right)
167        }
168    }
169
170    fn set_dfs(
171        &mut self,
172        node: NodePtr<M::T>,
173        start: usize,
174        end: usize,
175        index: usize,
176        value: &M::T,
177    ) -> NodePtr<M::T> {
178        if end - start == 1 {
179            return self.leaf_node(value.clone());
180        }
181        let mid = (start + end) / 2;
182        let mut children = Self::children(node);
183        if index < mid {
184            children[0] = self.set_dfs(children[0], start, mid, index, value);
185        } else {
186            children[1] = self.set_dfs(children[1], mid, end, index, value);
187        }
188        self.merge_nodes(children[0], children[1])
189    }
190
191    fn update_dfs(
192        &mut self,
193        node: NodePtr<M::T>,
194        start: usize,
195        end: usize,
196        index: usize,
197        value: &M::T,
198    ) -> NodePtr<M::T> {
199        if end - start == 1 {
200            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
201        }
202        let mid = (start + end) / 2;
203        let mut children = Self::children(node);
204        if index < mid {
205            children[0] = self.update_dfs(children[0], start, mid, index, value);
206        } else {
207            children[1] = self.update_dfs(children[1], mid, end, index, value);
208        }
209        self.merge_nodes(children[0], children[1])
210    }
Source

fn subtree_value(node: Option<NonNull<Node<M::T>>>) -> M::T

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 120)
116    fn merge_nodes(&mut self, left: NodePtr<M::T>, right: NodePtr<M::T>) -> NodePtr<M::T> {
117        if left.is_none() && right.is_none() {
118            None
119        } else {
120            let value = M::operate(&Self::subtree_value(left), &Self::subtree_value(right));
121            Some(self.allocate_node([left, right], value))
122        }
123    }
124
125    fn subtree_value(node: NodePtr<M::T>) -> M::T {
126        node.map(|node| unsafe { node.as_ref().value.clone() })
127            .unwrap_or_else(M::unit)
128    }
129
130    fn children(node: NodePtr<M::T>) -> [NodePtr<M::T>; 2] {
131        node.map(|node| unsafe { node.as_ref().children })
132            .unwrap_or([None, None])
133    }
134
135    fn point_get_dfs(node: NodePtr<M::T>, start: usize, end: usize, index: usize) -> M::T {
136        let Some(node) = node else {
137            return M::unit();
138        };
139        let node = unsafe { node.as_ref() };
140        if end - start == 1 {
141            node.value.clone()
142        } else {
143            let mid = (start + end) / 2;
144            if index < mid {
145                Self::point_get_dfs(node.children[0], start, mid, index)
146            } else {
147                Self::point_get_dfs(node.children[1], mid, end, index)
148            }
149        }
150    }
151
152    fn fold_dfs(node: NodePtr<M::T>, start: usize, end: usize, range: &Range<usize>) -> M::T {
153        if range.end <= start || end <= range.start {
154            return M::unit();
155        }
156        let Some(node) = node else {
157            return M::unit();
158        };
159        let node = unsafe { node.as_ref() };
160        if range.start <= start && end <= range.end {
161            node.value.clone()
162        } else {
163            let mid = (start + end) / 2;
164            let left = Self::fold_dfs(node.children[0], start, mid, range);
165            let right = Self::fold_dfs(node.children[1], mid, end, range);
166            M::operate(&left, &right)
167        }
168    }
169
170    fn set_dfs(
171        &mut self,
172        node: NodePtr<M::T>,
173        start: usize,
174        end: usize,
175        index: usize,
176        value: &M::T,
177    ) -> NodePtr<M::T> {
178        if end - start == 1 {
179            return self.leaf_node(value.clone());
180        }
181        let mid = (start + end) / 2;
182        let mut children = Self::children(node);
183        if index < mid {
184            children[0] = self.set_dfs(children[0], start, mid, index, value);
185        } else {
186            children[1] = self.set_dfs(children[1], mid, end, index, value);
187        }
188        self.merge_nodes(children[0], children[1])
189    }
190
191    fn update_dfs(
192        &mut self,
193        node: NodePtr<M::T>,
194        start: usize,
195        end: usize,
196        index: usize,
197        value: &M::T,
198    ) -> NodePtr<M::T> {
199        if end - start == 1 {
200            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
201        }
202        let mid = (start + end) / 2;
203        let mut children = Self::children(node);
204        if index < mid {
205            children[0] = self.update_dfs(children[0], start, mid, index, value);
206        } else {
207            children[1] = self.update_dfs(children[1], mid, end, index, value);
208        }
209        self.merge_nodes(children[0], children[1])
210    }
211
212    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
213        assert_eq!(v.len(), self.len);
214        let root = if self.len == 0 {
215            None
216        } else {
217            self.build_dfs(0, self.len, &v)
218        };
219        self.push_version_root(root)
220    }
221
222    pub fn set(
223        &mut self,
224        version: PersistentSegmentTreeVersion,
225        index: usize,
226        value: M::T,
227    ) -> PersistentSegmentTreeVersion {
228        assert!(index < self.len);
229        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
230        self.push_version_root(root)
231    }
232
233    pub fn update(
234        &mut self,
235        version: PersistentSegmentTreeVersion,
236        index: usize,
237        value: M::T,
238    ) -> PersistentSegmentTreeVersion {
239        assert!(index < self.len);
240        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
241        self.push_version_root(root)
242    }
243
244    #[must_use]
245    pub fn get(&self, version: PersistentSegmentTreeVersion, index: usize) -> M::T {
246        assert!(index < self.len);
247        Self::point_get_dfs(self.version_root(version), 0, self.len, index)
248    }
249
250    #[must_use]
251    pub fn fold<R>(&self, version: PersistentSegmentTreeVersion, range: R) -> M::T
252    where
253        R: RangeBounds<usize>,
254    {
255        let range = range.to_range_bounded(0, self.len).expect("invalid range");
256        if range.is_empty() {
257            M::unit()
258        } else {
259            Self::fold_dfs(self.version_root(version), 0, self.len, &range)
260        }
261    }
262
263    #[must_use]
264    pub fn fold_all(&self, version: PersistentSegmentTreeVersion) -> M::T {
265        Self::subtree_value(self.version_root(version))
266    }
Source

fn children( node: Option<NonNull<Node<M::T>>>, ) -> [Option<NonNull<Node<M::T>>>; 2]

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 182)
170    fn set_dfs(
171        &mut self,
172        node: NodePtr<M::T>,
173        start: usize,
174        end: usize,
175        index: usize,
176        value: &M::T,
177    ) -> NodePtr<M::T> {
178        if end - start == 1 {
179            return self.leaf_node(value.clone());
180        }
181        let mid = (start + end) / 2;
182        let mut children = Self::children(node);
183        if index < mid {
184            children[0] = self.set_dfs(children[0], start, mid, index, value);
185        } else {
186            children[1] = self.set_dfs(children[1], mid, end, index, value);
187        }
188        self.merge_nodes(children[0], children[1])
189    }
190
191    fn update_dfs(
192        &mut self,
193        node: NodePtr<M::T>,
194        start: usize,
195        end: usize,
196        index: usize,
197        value: &M::T,
198    ) -> NodePtr<M::T> {
199        if end - start == 1 {
200            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
201        }
202        let mid = (start + end) / 2;
203        let mut children = Self::children(node);
204        if index < mid {
205            children[0] = self.update_dfs(children[0], start, mid, index, value);
206        } else {
207            children[1] = self.update_dfs(children[1], mid, end, index, value);
208        }
209        self.merge_nodes(children[0], children[1])
210    }
Source

fn point_get_dfs( node: Option<NonNull<Node<M::T>>>, start: usize, end: usize, index: usize, ) -> M::T

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 145)
135    fn point_get_dfs(node: NodePtr<M::T>, start: usize, end: usize, index: usize) -> M::T {
136        let Some(node) = node else {
137            return M::unit();
138        };
139        let node = unsafe { node.as_ref() };
140        if end - start == 1 {
141            node.value.clone()
142        } else {
143            let mid = (start + end) / 2;
144            if index < mid {
145                Self::point_get_dfs(node.children[0], start, mid, index)
146            } else {
147                Self::point_get_dfs(node.children[1], mid, end, index)
148            }
149        }
150    }
151
152    fn fold_dfs(node: NodePtr<M::T>, start: usize, end: usize, range: &Range<usize>) -> M::T {
153        if range.end <= start || end <= range.start {
154            return M::unit();
155        }
156        let Some(node) = node else {
157            return M::unit();
158        };
159        let node = unsafe { node.as_ref() };
160        if range.start <= start && end <= range.end {
161            node.value.clone()
162        } else {
163            let mid = (start + end) / 2;
164            let left = Self::fold_dfs(node.children[0], start, mid, range);
165            let right = Self::fold_dfs(node.children[1], mid, end, range);
166            M::operate(&left, &right)
167        }
168    }
169
170    fn set_dfs(
171        &mut self,
172        node: NodePtr<M::T>,
173        start: usize,
174        end: usize,
175        index: usize,
176        value: &M::T,
177    ) -> NodePtr<M::T> {
178        if end - start == 1 {
179            return self.leaf_node(value.clone());
180        }
181        let mid = (start + end) / 2;
182        let mut children = Self::children(node);
183        if index < mid {
184            children[0] = self.set_dfs(children[0], start, mid, index, value);
185        } else {
186            children[1] = self.set_dfs(children[1], mid, end, index, value);
187        }
188        self.merge_nodes(children[0], children[1])
189    }
190
191    fn update_dfs(
192        &mut self,
193        node: NodePtr<M::T>,
194        start: usize,
195        end: usize,
196        index: usize,
197        value: &M::T,
198    ) -> NodePtr<M::T> {
199        if end - start == 1 {
200            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
201        }
202        let mid = (start + end) / 2;
203        let mut children = Self::children(node);
204        if index < mid {
205            children[0] = self.update_dfs(children[0], start, mid, index, value);
206        } else {
207            children[1] = self.update_dfs(children[1], mid, end, index, value);
208        }
209        self.merge_nodes(children[0], children[1])
210    }
211
212    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
213        assert_eq!(v.len(), self.len);
214        let root = if self.len == 0 {
215            None
216        } else {
217            self.build_dfs(0, self.len, &v)
218        };
219        self.push_version_root(root)
220    }
221
222    pub fn set(
223        &mut self,
224        version: PersistentSegmentTreeVersion,
225        index: usize,
226        value: M::T,
227    ) -> PersistentSegmentTreeVersion {
228        assert!(index < self.len);
229        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
230        self.push_version_root(root)
231    }
232
233    pub fn update(
234        &mut self,
235        version: PersistentSegmentTreeVersion,
236        index: usize,
237        value: M::T,
238    ) -> PersistentSegmentTreeVersion {
239        assert!(index < self.len);
240        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
241        self.push_version_root(root)
242    }
243
244    #[must_use]
245    pub fn get(&self, version: PersistentSegmentTreeVersion, index: usize) -> M::T {
246        assert!(index < self.len);
247        Self::point_get_dfs(self.version_root(version), 0, self.len, index)
248    }
Source

fn fold_dfs( node: Option<NonNull<Node<M::T>>>, start: usize, end: usize, range: &Range<usize>, ) -> M::T

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 164)
152    fn fold_dfs(node: NodePtr<M::T>, start: usize, end: usize, range: &Range<usize>) -> M::T {
153        if range.end <= start || end <= range.start {
154            return M::unit();
155        }
156        let Some(node) = node else {
157            return M::unit();
158        };
159        let node = unsafe { node.as_ref() };
160        if range.start <= start && end <= range.end {
161            node.value.clone()
162        } else {
163            let mid = (start + end) / 2;
164            let left = Self::fold_dfs(node.children[0], start, mid, range);
165            let right = Self::fold_dfs(node.children[1], mid, end, range);
166            M::operate(&left, &right)
167        }
168    }
169
170    fn set_dfs(
171        &mut self,
172        node: NodePtr<M::T>,
173        start: usize,
174        end: usize,
175        index: usize,
176        value: &M::T,
177    ) -> NodePtr<M::T> {
178        if end - start == 1 {
179            return self.leaf_node(value.clone());
180        }
181        let mid = (start + end) / 2;
182        let mut children = Self::children(node);
183        if index < mid {
184            children[0] = self.set_dfs(children[0], start, mid, index, value);
185        } else {
186            children[1] = self.set_dfs(children[1], mid, end, index, value);
187        }
188        self.merge_nodes(children[0], children[1])
189    }
190
191    fn update_dfs(
192        &mut self,
193        node: NodePtr<M::T>,
194        start: usize,
195        end: usize,
196        index: usize,
197        value: &M::T,
198    ) -> NodePtr<M::T> {
199        if end - start == 1 {
200            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
201        }
202        let mid = (start + end) / 2;
203        let mut children = Self::children(node);
204        if index < mid {
205            children[0] = self.update_dfs(children[0], start, mid, index, value);
206        } else {
207            children[1] = self.update_dfs(children[1], mid, end, index, value);
208        }
209        self.merge_nodes(children[0], children[1])
210    }
211
212    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
213        assert_eq!(v.len(), self.len);
214        let root = if self.len == 0 {
215            None
216        } else {
217            self.build_dfs(0, self.len, &v)
218        };
219        self.push_version_root(root)
220    }
221
222    pub fn set(
223        &mut self,
224        version: PersistentSegmentTreeVersion,
225        index: usize,
226        value: M::T,
227    ) -> PersistentSegmentTreeVersion {
228        assert!(index < self.len);
229        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
230        self.push_version_root(root)
231    }
232
233    pub fn update(
234        &mut self,
235        version: PersistentSegmentTreeVersion,
236        index: usize,
237        value: M::T,
238    ) -> PersistentSegmentTreeVersion {
239        assert!(index < self.len);
240        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
241        self.push_version_root(root)
242    }
243
244    #[must_use]
245    pub fn get(&self, version: PersistentSegmentTreeVersion, index: usize) -> M::T {
246        assert!(index < self.len);
247        Self::point_get_dfs(self.version_root(version), 0, self.len, index)
248    }
249
250    #[must_use]
251    pub fn fold<R>(&self, version: PersistentSegmentTreeVersion, range: R) -> M::T
252    where
253        R: RangeBounds<usize>,
254    {
255        let range = range.to_range_bounded(0, self.len).expect("invalid range");
256        if range.is_empty() {
257            M::unit()
258        } else {
259            Self::fold_dfs(self.version_root(version), 0, self.len, &range)
260        }
261    }
Source

fn set_dfs( &mut self, node: Option<NonNull<Node<M::T>>>, start: usize, end: usize, index: usize, value: &M::T, ) -> Option<NonNull<Node<M::T>>>

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 184)
170    fn set_dfs(
171        &mut self,
172        node: NodePtr<M::T>,
173        start: usize,
174        end: usize,
175        index: usize,
176        value: &M::T,
177    ) -> NodePtr<M::T> {
178        if end - start == 1 {
179            return self.leaf_node(value.clone());
180        }
181        let mid = (start + end) / 2;
182        let mut children = Self::children(node);
183        if index < mid {
184            children[0] = self.set_dfs(children[0], start, mid, index, value);
185        } else {
186            children[1] = self.set_dfs(children[1], mid, end, index, value);
187        }
188        self.merge_nodes(children[0], children[1])
189    }
190
191    fn update_dfs(
192        &mut self,
193        node: NodePtr<M::T>,
194        start: usize,
195        end: usize,
196        index: usize,
197        value: &M::T,
198    ) -> NodePtr<M::T> {
199        if end - start == 1 {
200            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
201        }
202        let mid = (start + end) / 2;
203        let mut children = Self::children(node);
204        if index < mid {
205            children[0] = self.update_dfs(children[0], start, mid, index, value);
206        } else {
207            children[1] = self.update_dfs(children[1], mid, end, index, value);
208        }
209        self.merge_nodes(children[0], children[1])
210    }
211
212    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
213        assert_eq!(v.len(), self.len);
214        let root = if self.len == 0 {
215            None
216        } else {
217            self.build_dfs(0, self.len, &v)
218        };
219        self.push_version_root(root)
220    }
221
222    pub fn set(
223        &mut self,
224        version: PersistentSegmentTreeVersion,
225        index: usize,
226        value: M::T,
227    ) -> PersistentSegmentTreeVersion {
228        assert!(index < self.len);
229        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
230        self.push_version_root(root)
231    }
Source

fn update_dfs( &mut self, node: Option<NonNull<Node<M::T>>>, start: usize, end: usize, index: usize, value: &M::T, ) -> Option<NonNull<Node<M::T>>>

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 205)
191    fn update_dfs(
192        &mut self,
193        node: NodePtr<M::T>,
194        start: usize,
195        end: usize,
196        index: usize,
197        value: &M::T,
198    ) -> NodePtr<M::T> {
199        if end - start == 1 {
200            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
201        }
202        let mid = (start + end) / 2;
203        let mut children = Self::children(node);
204        if index < mid {
205            children[0] = self.update_dfs(children[0], start, mid, index, value);
206        } else {
207            children[1] = self.update_dfs(children[1], mid, end, index, value);
208        }
209        self.merge_nodes(children[0], children[1])
210    }
211
212    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
213        assert_eq!(v.len(), self.len);
214        let root = if self.len == 0 {
215            None
216        } else {
217            self.build_dfs(0, self.len, &v)
218        };
219        self.push_version_root(root)
220    }
221
222    pub fn set(
223        &mut self,
224        version: PersistentSegmentTreeVersion,
225        index: usize,
226        value: M::T,
227    ) -> PersistentSegmentTreeVersion {
228        assert!(index < self.len);
229        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
230        self.push_version_root(root)
231    }
232
233    pub fn update(
234        &mut self,
235        version: PersistentSegmentTreeVersion,
236        index: usize,
237        value: M::T,
238    ) -> PersistentSegmentTreeVersion {
239        assert!(index < self.len);
240        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
241        self.push_version_root(root)
242    }
Source

pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion

Source

pub fn set( &mut self, version: PersistentSegmentTreeVersion, index: usize, value: M::T, ) -> PersistentSegmentTreeVersion

Source

pub fn update( &mut self, version: PersistentSegmentTreeVersion, index: usize, value: M::T, ) -> PersistentSegmentTreeVersion

Source

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

Source

pub fn fold<R>(&self, version: PersistentSegmentTreeVersion, range: R) -> M::T
where R: RangeBounds<usize>,

Source

pub fn fold_all(&self, version: PersistentSegmentTreeVersion) -> M::T

Trait Implementations§

Source§

impl<M> Debug for PersistentSegmentTree<M>
where M: Monoid,

Source§

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

Formats the value using the given formatter. Read more

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.