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 301)
294    pub fn set(
295        &mut self,
296        version: PersistentSegmentTreeVersion,
297        index: usize,
298        value: M::T,
299    ) -> PersistentSegmentTreeVersion {
300        assert!(index < self.len);
301        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
302        self.push_version_root(root)
303    }
304
305    pub fn update(
306        &mut self,
307        version: PersistentSegmentTreeVersion,
308        index: usize,
309        value: M::T,
310    ) -> PersistentSegmentTreeVersion {
311        assert!(index < self.len);
312        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
313        self.push_version_root(root)
314    }
315
316    #[must_use]
317    pub fn get(&self, version: PersistentSegmentTreeVersion, index: usize) -> M::T {
318        assert!(index < self.len);
319        Self::point_get_dfs(self.version_root(version), 0, self.len, index)
320    }
321
322    #[must_use]
323    pub fn fold<R>(&self, version: PersistentSegmentTreeVersion, range: R) -> M::T
324    where
325        R: RangeBounds<usize>,
326    {
327        let range = range.to_range_bounded(0, self.len).expect("invalid range");
328        if range.is_empty() {
329            M::unit()
330        } else {
331            Self::fold_dfs(self.version_root(version), 0, self.len, &range)
332        }
333    }
334
335    pub fn partition_point_acc<P>(
336        &self,
337        version: PersistentSegmentTreeVersion,
338        left: usize,
339        mut pred: P,
340    ) -> (usize, M::T)
341    where
342        P: FnMut(&M::T) -> bool,
343    {
344        let root = self.version_root(version);
345        let mut acc = M::unit();
346        let pos = if self.len == 0 {
347            None
348        } else {
349            Self::partition_point_dfs(root, 0, self.len, left, &mut acc, &mut pred)
350        };
351        (pos.unwrap_or(self.len), acc)
352    }
353
354    pub fn rpartition_point_acc<P>(
355        &self,
356        version: PersistentSegmentTreeVersion,
357        right: usize,
358        mut pred: P,
359    ) -> (usize, M::T)
360    where
361        P: FnMut(&M::T) -> bool,
362    {
363        let root = self.version_root(version);
364        let mut acc = M::unit();
365        let pos = if self.len == 0 {
366            None
367        } else {
368            Self::rpartition_point_dfs(root, 0, self.len, right, &mut acc, &mut pred)
369        };
370        (pos.unwrap_or(0), acc)
371    }
372
373    #[must_use]
374    pub fn fold_all(&self, version: PersistentSegmentTreeVersion) -> M::T {
375        Self::subtree_value(self.version_root(version))
376    }
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 291)
284    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
285        assert_eq!(v.len(), self.len);
286        let root = if self.len == 0 {
287            None
288        } else {
289            self.build_dfs(0, self.len, &v)
290        };
291        self.push_version_root(root)
292    }
293
294    pub fn set(
295        &mut self,
296        version: PersistentSegmentTreeVersion,
297        index: usize,
298        value: M::T,
299    ) -> PersistentSegmentTreeVersion {
300        assert!(index < self.len);
301        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
302        self.push_version_root(root)
303    }
304
305    pub fn update(
306        &mut self,
307        version: PersistentSegmentTreeVersion,
308        index: usize,
309        value: M::T,
310    ) -> PersistentSegmentTreeVersion {
311        assert!(index < self.len);
312        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
313        self.push_version_root(root)
314    }
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            if range.end <= mid {
165                return Self::fold_dfs(node.children[0], start, mid, range);
166            }
167            if mid <= range.start {
168                return Self::fold_dfs(node.children[1], mid, end, range);
169            }
170            let left = Self::fold_dfs(node.children[0], start, mid, range);
171            let right = Self::fold_dfs(node.children[1], mid, end, range);
172            M::operate(&left, &right)
173        }
174    }
175
176    fn partition_point_dfs<P>(
177        node: NodePtr<M::T>,
178        start: usize,
179        end: usize,
180        left: usize,
181        acc: &mut M::T,
182        pred: &mut P,
183    ) -> Option<usize>
184    where
185        P: FnMut(&M::T) -> bool,
186    {
187        if end <= left {
188            return None;
189        }
190        if left <= start {
191            let nacc = M::operate(acc, &Self::subtree_value(node));
192            if pred(&nacc) {
193                *acc = nacc;
194                return None;
195            }
196            if end - start == 1 {
197                return Some(start);
198            }
199        }
200        let mid = (start + end) / 2;
201        let [l, r] = Self::children(node);
202        if let Some(pos) = Self::partition_point_dfs(l, start, mid, left, acc, pred) {
203            Some(pos)
204        } else {
205            Self::partition_point_dfs(r, mid, end, left, acc, pred)
206        }
207    }
208
209    fn rpartition_point_dfs<P>(
210        node: NodePtr<M::T>,
211        start: usize,
212        end: usize,
213        right: usize,
214        acc: &mut M::T,
215        pred: &mut P,
216    ) -> Option<usize>
217    where
218        P: FnMut(&M::T) -> bool,
219    {
220        if right <= start {
221            return None;
222        }
223        if end <= right {
224            let nacc = M::operate(&Self::subtree_value(node), acc);
225            if pred(&nacc) {
226                *acc = nacc;
227                return None;
228            }
229            if end - start == 1 {
230                return Some(end);
231            }
232        }
233        let mid = (start + end) / 2;
234        let [l, r] = Self::children(node);
235        if let Some(pos) = Self::rpartition_point_dfs(r, mid, end, right, acc, pred) {
236            Some(pos)
237        } else {
238            Self::rpartition_point_dfs(l, start, mid, right, acc, pred)
239        }
240    }
241
242    fn set_dfs(
243        &mut self,
244        node: NodePtr<M::T>,
245        start: usize,
246        end: usize,
247        index: usize,
248        value: &M::T,
249    ) -> NodePtr<M::T> {
250        if end - start == 1 {
251            return self.leaf_node(value.clone());
252        }
253        let mid = (start + end) / 2;
254        let mut children = Self::children(node);
255        if index < mid {
256            children[0] = self.set_dfs(children[0], start, mid, index, value);
257        } else {
258            children[1] = self.set_dfs(children[1], mid, end, index, value);
259        }
260        self.merge_nodes(children[0], children[1])
261    }
262
263    fn update_dfs(
264        &mut self,
265        node: NodePtr<M::T>,
266        start: usize,
267        end: usize,
268        index: usize,
269        value: &M::T,
270    ) -> NodePtr<M::T> {
271        if end - start == 1 {
272            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
273        }
274        let mid = (start + end) / 2;
275        let mut children = Self::children(node);
276        if index < mid {
277            children[0] = self.update_dfs(children[0], start, mid, index, value);
278        } else {
279            children[1] = self.update_dfs(children[1], mid, end, index, value);
280        }
281        self.merge_nodes(children[0], children[1])
282    }
283
284    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
285        assert_eq!(v.len(), self.len);
286        let root = if self.len == 0 {
287            None
288        } else {
289            self.build_dfs(0, self.len, &v)
290        };
291        self.push_version_root(root)
292    }
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            if range.end <= mid {
165                return Self::fold_dfs(node.children[0], start, mid, range);
166            }
167            if mid <= range.start {
168                return Self::fold_dfs(node.children[1], mid, end, range);
169            }
170            let left = Self::fold_dfs(node.children[0], start, mid, range);
171            let right = Self::fold_dfs(node.children[1], mid, end, range);
172            M::operate(&left, &right)
173        }
174    }
175
176    fn partition_point_dfs<P>(
177        node: NodePtr<M::T>,
178        start: usize,
179        end: usize,
180        left: usize,
181        acc: &mut M::T,
182        pred: &mut P,
183    ) -> Option<usize>
184    where
185        P: FnMut(&M::T) -> bool,
186    {
187        if end <= left {
188            return None;
189        }
190        if left <= start {
191            let nacc = M::operate(acc, &Self::subtree_value(node));
192            if pred(&nacc) {
193                *acc = nacc;
194                return None;
195            }
196            if end - start == 1 {
197                return Some(start);
198            }
199        }
200        let mid = (start + end) / 2;
201        let [l, r] = Self::children(node);
202        if let Some(pos) = Self::partition_point_dfs(l, start, mid, left, acc, pred) {
203            Some(pos)
204        } else {
205            Self::partition_point_dfs(r, mid, end, left, acc, pred)
206        }
207    }
208
209    fn rpartition_point_dfs<P>(
210        node: NodePtr<M::T>,
211        start: usize,
212        end: usize,
213        right: usize,
214        acc: &mut M::T,
215        pred: &mut P,
216    ) -> Option<usize>
217    where
218        P: FnMut(&M::T) -> bool,
219    {
220        if right <= start {
221            return None;
222        }
223        if end <= right {
224            let nacc = M::operate(&Self::subtree_value(node), acc);
225            if pred(&nacc) {
226                *acc = nacc;
227                return None;
228            }
229            if end - start == 1 {
230                return Some(end);
231            }
232        }
233        let mid = (start + end) / 2;
234        let [l, r] = Self::children(node);
235        if let Some(pos) = Self::rpartition_point_dfs(r, mid, end, right, acc, pred) {
236            Some(pos)
237        } else {
238            Self::rpartition_point_dfs(l, start, mid, right, acc, pred)
239        }
240    }
241
242    fn set_dfs(
243        &mut self,
244        node: NodePtr<M::T>,
245        start: usize,
246        end: usize,
247        index: usize,
248        value: &M::T,
249    ) -> NodePtr<M::T> {
250        if end - start == 1 {
251            return self.leaf_node(value.clone());
252        }
253        let mid = (start + end) / 2;
254        let mut children = Self::children(node);
255        if index < mid {
256            children[0] = self.set_dfs(children[0], start, mid, index, value);
257        } else {
258            children[1] = self.set_dfs(children[1], mid, end, index, value);
259        }
260        self.merge_nodes(children[0], children[1])
261    }
262
263    fn update_dfs(
264        &mut self,
265        node: NodePtr<M::T>,
266        start: usize,
267        end: usize,
268        index: usize,
269        value: &M::T,
270    ) -> NodePtr<M::T> {
271        if end - start == 1 {
272            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
273        }
274        let mid = (start + end) / 2;
275        let mut children = Self::children(node);
276        if index < mid {
277            children[0] = self.update_dfs(children[0], start, mid, index, value);
278        } else {
279            children[1] = self.update_dfs(children[1], mid, end, index, value);
280        }
281        self.merge_nodes(children[0], children[1])
282    }
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            if range.end <= mid {
165                return Self::fold_dfs(node.children[0], start, mid, range);
166            }
167            if mid <= range.start {
168                return Self::fold_dfs(node.children[1], mid, end, range);
169            }
170            let left = Self::fold_dfs(node.children[0], start, mid, range);
171            let right = Self::fold_dfs(node.children[1], mid, end, range);
172            M::operate(&left, &right)
173        }
174    }
175
176    fn partition_point_dfs<P>(
177        node: NodePtr<M::T>,
178        start: usize,
179        end: usize,
180        left: usize,
181        acc: &mut M::T,
182        pred: &mut P,
183    ) -> Option<usize>
184    where
185        P: FnMut(&M::T) -> bool,
186    {
187        if end <= left {
188            return None;
189        }
190        if left <= start {
191            let nacc = M::operate(acc, &Self::subtree_value(node));
192            if pred(&nacc) {
193                *acc = nacc;
194                return None;
195            }
196            if end - start == 1 {
197                return Some(start);
198            }
199        }
200        let mid = (start + end) / 2;
201        let [l, r] = Self::children(node);
202        if let Some(pos) = Self::partition_point_dfs(l, start, mid, left, acc, pred) {
203            Some(pos)
204        } else {
205            Self::partition_point_dfs(r, mid, end, left, acc, pred)
206        }
207    }
208
209    fn rpartition_point_dfs<P>(
210        node: NodePtr<M::T>,
211        start: usize,
212        end: usize,
213        right: usize,
214        acc: &mut M::T,
215        pred: &mut P,
216    ) -> Option<usize>
217    where
218        P: FnMut(&M::T) -> bool,
219    {
220        if right <= start {
221            return None;
222        }
223        if end <= right {
224            let nacc = M::operate(&Self::subtree_value(node), acc);
225            if pred(&nacc) {
226                *acc = nacc;
227                return None;
228            }
229            if end - start == 1 {
230                return Some(end);
231            }
232        }
233        let mid = (start + end) / 2;
234        let [l, r] = Self::children(node);
235        if let Some(pos) = Self::rpartition_point_dfs(r, mid, end, right, acc, pred) {
236            Some(pos)
237        } else {
238            Self::rpartition_point_dfs(l, start, mid, right, acc, pred)
239        }
240    }
241
242    fn set_dfs(
243        &mut self,
244        node: NodePtr<M::T>,
245        start: usize,
246        end: usize,
247        index: usize,
248        value: &M::T,
249    ) -> NodePtr<M::T> {
250        if end - start == 1 {
251            return self.leaf_node(value.clone());
252        }
253        let mid = (start + end) / 2;
254        let mut children = Self::children(node);
255        if index < mid {
256            children[0] = self.set_dfs(children[0], start, mid, index, value);
257        } else {
258            children[1] = self.set_dfs(children[1], mid, end, index, value);
259        }
260        self.merge_nodes(children[0], children[1])
261    }
262
263    fn update_dfs(
264        &mut self,
265        node: NodePtr<M::T>,
266        start: usize,
267        end: usize,
268        index: usize,
269        value: &M::T,
270    ) -> NodePtr<M::T> {
271        if end - start == 1 {
272            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
273        }
274        let mid = (start + end) / 2;
275        let mut children = Self::children(node);
276        if index < mid {
277            children[0] = self.update_dfs(children[0], start, mid, index, value);
278        } else {
279            children[1] = self.update_dfs(children[1], mid, end, index, value);
280        }
281        self.merge_nodes(children[0], children[1])
282    }
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            if range.end <= mid {
165                return Self::fold_dfs(node.children[0], start, mid, range);
166            }
167            if mid <= range.start {
168                return Self::fold_dfs(node.children[1], mid, end, range);
169            }
170            let left = Self::fold_dfs(node.children[0], start, mid, range);
171            let right = Self::fold_dfs(node.children[1], mid, end, range);
172            M::operate(&left, &right)
173        }
174    }
175
176    fn partition_point_dfs<P>(
177        node: NodePtr<M::T>,
178        start: usize,
179        end: usize,
180        left: usize,
181        acc: &mut M::T,
182        pred: &mut P,
183    ) -> Option<usize>
184    where
185        P: FnMut(&M::T) -> bool,
186    {
187        if end <= left {
188            return None;
189        }
190        if left <= start {
191            let nacc = M::operate(acc, &Self::subtree_value(node));
192            if pred(&nacc) {
193                *acc = nacc;
194                return None;
195            }
196            if end - start == 1 {
197                return Some(start);
198            }
199        }
200        let mid = (start + end) / 2;
201        let [l, r] = Self::children(node);
202        if let Some(pos) = Self::partition_point_dfs(l, start, mid, left, acc, pred) {
203            Some(pos)
204        } else {
205            Self::partition_point_dfs(r, mid, end, left, acc, pred)
206        }
207    }
208
209    fn rpartition_point_dfs<P>(
210        node: NodePtr<M::T>,
211        start: usize,
212        end: usize,
213        right: usize,
214        acc: &mut M::T,
215        pred: &mut P,
216    ) -> Option<usize>
217    where
218        P: FnMut(&M::T) -> bool,
219    {
220        if right <= start {
221            return None;
222        }
223        if end <= right {
224            let nacc = M::operate(&Self::subtree_value(node), acc);
225            if pred(&nacc) {
226                *acc = nacc;
227                return None;
228            }
229            if end - start == 1 {
230                return Some(end);
231            }
232        }
233        let mid = (start + end) / 2;
234        let [l, r] = Self::children(node);
235        if let Some(pos) = Self::rpartition_point_dfs(r, mid, end, right, acc, pred) {
236            Some(pos)
237        } else {
238            Self::rpartition_point_dfs(l, start, mid, right, acc, pred)
239        }
240    }
241
242    fn set_dfs(
243        &mut self,
244        node: NodePtr<M::T>,
245        start: usize,
246        end: usize,
247        index: usize,
248        value: &M::T,
249    ) -> NodePtr<M::T> {
250        if end - start == 1 {
251            return self.leaf_node(value.clone());
252        }
253        let mid = (start + end) / 2;
254        let mut children = Self::children(node);
255        if index < mid {
256            children[0] = self.set_dfs(children[0], start, mid, index, value);
257        } else {
258            children[1] = self.set_dfs(children[1], mid, end, index, value);
259        }
260        self.merge_nodes(children[0], children[1])
261    }
262
263    fn update_dfs(
264        &mut self,
265        node: NodePtr<M::T>,
266        start: usize,
267        end: usize,
268        index: usize,
269        value: &M::T,
270    ) -> NodePtr<M::T> {
271        if end - start == 1 {
272            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
273        }
274        let mid = (start + end) / 2;
275        let mut children = Self::children(node);
276        if index < mid {
277            children[0] = self.update_dfs(children[0], start, mid, index, value);
278        } else {
279            children[1] = self.update_dfs(children[1], mid, end, index, value);
280        }
281        self.merge_nodes(children[0], children[1])
282    }
283
284    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
285        assert_eq!(v.len(), self.len);
286        let root = if self.len == 0 {
287            None
288        } else {
289            self.build_dfs(0, self.len, &v)
290        };
291        self.push_version_root(root)
292    }
293
294    pub fn set(
295        &mut self,
296        version: PersistentSegmentTreeVersion,
297        index: usize,
298        value: M::T,
299    ) -> PersistentSegmentTreeVersion {
300        assert!(index < self.len);
301        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
302        self.push_version_root(root)
303    }
304
305    pub fn update(
306        &mut self,
307        version: PersistentSegmentTreeVersion,
308        index: usize,
309        value: M::T,
310    ) -> PersistentSegmentTreeVersion {
311        assert!(index < self.len);
312        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
313        self.push_version_root(root)
314    }
315
316    #[must_use]
317    pub fn get(&self, version: PersistentSegmentTreeVersion, index: usize) -> M::T {
318        assert!(index < self.len);
319        Self::point_get_dfs(self.version_root(version), 0, self.len, index)
320    }
321
322    #[must_use]
323    pub fn fold<R>(&self, version: PersistentSegmentTreeVersion, range: R) -> M::T
324    where
325        R: RangeBounds<usize>,
326    {
327        let range = range.to_range_bounded(0, self.len).expect("invalid range");
328        if range.is_empty() {
329            M::unit()
330        } else {
331            Self::fold_dfs(self.version_root(version), 0, self.len, &range)
332        }
333    }
334
335    pub fn partition_point_acc<P>(
336        &self,
337        version: PersistentSegmentTreeVersion,
338        left: usize,
339        mut pred: P,
340    ) -> (usize, M::T)
341    where
342        P: FnMut(&M::T) -> bool,
343    {
344        let root = self.version_root(version);
345        let mut acc = M::unit();
346        let pos = if self.len == 0 {
347            None
348        } else {
349            Self::partition_point_dfs(root, 0, self.len, left, &mut acc, &mut pred)
350        };
351        (pos.unwrap_or(self.len), acc)
352    }
353
354    pub fn rpartition_point_acc<P>(
355        &self,
356        version: PersistentSegmentTreeVersion,
357        right: usize,
358        mut pred: P,
359    ) -> (usize, M::T)
360    where
361        P: FnMut(&M::T) -> bool,
362    {
363        let root = self.version_root(version);
364        let mut acc = M::unit();
365        let pos = if self.len == 0 {
366            None
367        } else {
368            Self::rpartition_point_dfs(root, 0, self.len, right, &mut acc, &mut pred)
369        };
370        (pos.unwrap_or(0), acc)
371    }
372
373    #[must_use]
374    pub fn fold_all(&self, version: PersistentSegmentTreeVersion) -> M::T {
375        Self::subtree_value(self.version_root(version))
376    }
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 201)
176    fn partition_point_dfs<P>(
177        node: NodePtr<M::T>,
178        start: usize,
179        end: usize,
180        left: usize,
181        acc: &mut M::T,
182        pred: &mut P,
183    ) -> Option<usize>
184    where
185        P: FnMut(&M::T) -> bool,
186    {
187        if end <= left {
188            return None;
189        }
190        if left <= start {
191            let nacc = M::operate(acc, &Self::subtree_value(node));
192            if pred(&nacc) {
193                *acc = nacc;
194                return None;
195            }
196            if end - start == 1 {
197                return Some(start);
198            }
199        }
200        let mid = (start + end) / 2;
201        let [l, r] = Self::children(node);
202        if let Some(pos) = Self::partition_point_dfs(l, start, mid, left, acc, pred) {
203            Some(pos)
204        } else {
205            Self::partition_point_dfs(r, mid, end, left, acc, pred)
206        }
207    }
208
209    fn rpartition_point_dfs<P>(
210        node: NodePtr<M::T>,
211        start: usize,
212        end: usize,
213        right: usize,
214        acc: &mut M::T,
215        pred: &mut P,
216    ) -> Option<usize>
217    where
218        P: FnMut(&M::T) -> bool,
219    {
220        if right <= start {
221            return None;
222        }
223        if end <= right {
224            let nacc = M::operate(&Self::subtree_value(node), acc);
225            if pred(&nacc) {
226                *acc = nacc;
227                return None;
228            }
229            if end - start == 1 {
230                return Some(end);
231            }
232        }
233        let mid = (start + end) / 2;
234        let [l, r] = Self::children(node);
235        if let Some(pos) = Self::rpartition_point_dfs(r, mid, end, right, acc, pred) {
236            Some(pos)
237        } else {
238            Self::rpartition_point_dfs(l, start, mid, right, acc, pred)
239        }
240    }
241
242    fn set_dfs(
243        &mut self,
244        node: NodePtr<M::T>,
245        start: usize,
246        end: usize,
247        index: usize,
248        value: &M::T,
249    ) -> NodePtr<M::T> {
250        if end - start == 1 {
251            return self.leaf_node(value.clone());
252        }
253        let mid = (start + end) / 2;
254        let mut children = Self::children(node);
255        if index < mid {
256            children[0] = self.set_dfs(children[0], start, mid, index, value);
257        } else {
258            children[1] = self.set_dfs(children[1], mid, end, index, value);
259        }
260        self.merge_nodes(children[0], children[1])
261    }
262
263    fn update_dfs(
264        &mut self,
265        node: NodePtr<M::T>,
266        start: usize,
267        end: usize,
268        index: usize,
269        value: &M::T,
270    ) -> NodePtr<M::T> {
271        if end - start == 1 {
272            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
273        }
274        let mid = (start + end) / 2;
275        let mut children = Self::children(node);
276        if index < mid {
277            children[0] = self.update_dfs(children[0], start, mid, index, value);
278        } else {
279            children[1] = self.update_dfs(children[1], mid, end, index, value);
280        }
281        self.merge_nodes(children[0], children[1])
282    }
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            if range.end <= mid {
165                return Self::fold_dfs(node.children[0], start, mid, range);
166            }
167            if mid <= range.start {
168                return Self::fold_dfs(node.children[1], mid, end, range);
169            }
170            let left = Self::fold_dfs(node.children[0], start, mid, range);
171            let right = Self::fold_dfs(node.children[1], mid, end, range);
172            M::operate(&left, &right)
173        }
174    }
175
176    fn partition_point_dfs<P>(
177        node: NodePtr<M::T>,
178        start: usize,
179        end: usize,
180        left: usize,
181        acc: &mut M::T,
182        pred: &mut P,
183    ) -> Option<usize>
184    where
185        P: FnMut(&M::T) -> bool,
186    {
187        if end <= left {
188            return None;
189        }
190        if left <= start {
191            let nacc = M::operate(acc, &Self::subtree_value(node));
192            if pred(&nacc) {
193                *acc = nacc;
194                return None;
195            }
196            if end - start == 1 {
197                return Some(start);
198            }
199        }
200        let mid = (start + end) / 2;
201        let [l, r] = Self::children(node);
202        if let Some(pos) = Self::partition_point_dfs(l, start, mid, left, acc, pred) {
203            Some(pos)
204        } else {
205            Self::partition_point_dfs(r, mid, end, left, acc, pred)
206        }
207    }
208
209    fn rpartition_point_dfs<P>(
210        node: NodePtr<M::T>,
211        start: usize,
212        end: usize,
213        right: usize,
214        acc: &mut M::T,
215        pred: &mut P,
216    ) -> Option<usize>
217    where
218        P: FnMut(&M::T) -> bool,
219    {
220        if right <= start {
221            return None;
222        }
223        if end <= right {
224            let nacc = M::operate(&Self::subtree_value(node), acc);
225            if pred(&nacc) {
226                *acc = nacc;
227                return None;
228            }
229            if end - start == 1 {
230                return Some(end);
231            }
232        }
233        let mid = (start + end) / 2;
234        let [l, r] = Self::children(node);
235        if let Some(pos) = Self::rpartition_point_dfs(r, mid, end, right, acc, pred) {
236            Some(pos)
237        } else {
238            Self::rpartition_point_dfs(l, start, mid, right, acc, pred)
239        }
240    }
241
242    fn set_dfs(
243        &mut self,
244        node: NodePtr<M::T>,
245        start: usize,
246        end: usize,
247        index: usize,
248        value: &M::T,
249    ) -> NodePtr<M::T> {
250        if end - start == 1 {
251            return self.leaf_node(value.clone());
252        }
253        let mid = (start + end) / 2;
254        let mut children = Self::children(node);
255        if index < mid {
256            children[0] = self.set_dfs(children[0], start, mid, index, value);
257        } else {
258            children[1] = self.set_dfs(children[1], mid, end, index, value);
259        }
260        self.merge_nodes(children[0], children[1])
261    }
262
263    fn update_dfs(
264        &mut self,
265        node: NodePtr<M::T>,
266        start: usize,
267        end: usize,
268        index: usize,
269        value: &M::T,
270    ) -> NodePtr<M::T> {
271        if end - start == 1 {
272            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
273        }
274        let mid = (start + end) / 2;
275        let mut children = Self::children(node);
276        if index < mid {
277            children[0] = self.update_dfs(children[0], start, mid, index, value);
278        } else {
279            children[1] = self.update_dfs(children[1], mid, end, index, value);
280        }
281        self.merge_nodes(children[0], children[1])
282    }
283
284    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
285        assert_eq!(v.len(), self.len);
286        let root = if self.len == 0 {
287            None
288        } else {
289            self.build_dfs(0, self.len, &v)
290        };
291        self.push_version_root(root)
292    }
293
294    pub fn set(
295        &mut self,
296        version: PersistentSegmentTreeVersion,
297        index: usize,
298        value: M::T,
299    ) -> PersistentSegmentTreeVersion {
300        assert!(index < self.len);
301        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
302        self.push_version_root(root)
303    }
304
305    pub fn update(
306        &mut self,
307        version: PersistentSegmentTreeVersion,
308        index: usize,
309        value: M::T,
310    ) -> PersistentSegmentTreeVersion {
311        assert!(index < self.len);
312        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
313        self.push_version_root(root)
314    }
315
316    #[must_use]
317    pub fn get(&self, version: PersistentSegmentTreeVersion, index: usize) -> M::T {
318        assert!(index < self.len);
319        Self::point_get_dfs(self.version_root(version), 0, self.len, index)
320    }
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 165)
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            if range.end <= mid {
165                return Self::fold_dfs(node.children[0], start, mid, range);
166            }
167            if mid <= range.start {
168                return Self::fold_dfs(node.children[1], mid, end, range);
169            }
170            let left = Self::fold_dfs(node.children[0], start, mid, range);
171            let right = Self::fold_dfs(node.children[1], mid, end, range);
172            M::operate(&left, &right)
173        }
174    }
175
176    fn partition_point_dfs<P>(
177        node: NodePtr<M::T>,
178        start: usize,
179        end: usize,
180        left: usize,
181        acc: &mut M::T,
182        pred: &mut P,
183    ) -> Option<usize>
184    where
185        P: FnMut(&M::T) -> bool,
186    {
187        if end <= left {
188            return None;
189        }
190        if left <= start {
191            let nacc = M::operate(acc, &Self::subtree_value(node));
192            if pred(&nacc) {
193                *acc = nacc;
194                return None;
195            }
196            if end - start == 1 {
197                return Some(start);
198            }
199        }
200        let mid = (start + end) / 2;
201        let [l, r] = Self::children(node);
202        if let Some(pos) = Self::partition_point_dfs(l, start, mid, left, acc, pred) {
203            Some(pos)
204        } else {
205            Self::partition_point_dfs(r, mid, end, left, acc, pred)
206        }
207    }
208
209    fn rpartition_point_dfs<P>(
210        node: NodePtr<M::T>,
211        start: usize,
212        end: usize,
213        right: usize,
214        acc: &mut M::T,
215        pred: &mut P,
216    ) -> Option<usize>
217    where
218        P: FnMut(&M::T) -> bool,
219    {
220        if right <= start {
221            return None;
222        }
223        if end <= right {
224            let nacc = M::operate(&Self::subtree_value(node), acc);
225            if pred(&nacc) {
226                *acc = nacc;
227                return None;
228            }
229            if end - start == 1 {
230                return Some(end);
231            }
232        }
233        let mid = (start + end) / 2;
234        let [l, r] = Self::children(node);
235        if let Some(pos) = Self::rpartition_point_dfs(r, mid, end, right, acc, pred) {
236            Some(pos)
237        } else {
238            Self::rpartition_point_dfs(l, start, mid, right, acc, pred)
239        }
240    }
241
242    fn set_dfs(
243        &mut self,
244        node: NodePtr<M::T>,
245        start: usize,
246        end: usize,
247        index: usize,
248        value: &M::T,
249    ) -> NodePtr<M::T> {
250        if end - start == 1 {
251            return self.leaf_node(value.clone());
252        }
253        let mid = (start + end) / 2;
254        let mut children = Self::children(node);
255        if index < mid {
256            children[0] = self.set_dfs(children[0], start, mid, index, value);
257        } else {
258            children[1] = self.set_dfs(children[1], mid, end, index, value);
259        }
260        self.merge_nodes(children[0], children[1])
261    }
262
263    fn update_dfs(
264        &mut self,
265        node: NodePtr<M::T>,
266        start: usize,
267        end: usize,
268        index: usize,
269        value: &M::T,
270    ) -> NodePtr<M::T> {
271        if end - start == 1 {
272            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
273        }
274        let mid = (start + end) / 2;
275        let mut children = Self::children(node);
276        if index < mid {
277            children[0] = self.update_dfs(children[0], start, mid, index, value);
278        } else {
279            children[1] = self.update_dfs(children[1], mid, end, index, value);
280        }
281        self.merge_nodes(children[0], children[1])
282    }
283
284    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
285        assert_eq!(v.len(), self.len);
286        let root = if self.len == 0 {
287            None
288        } else {
289            self.build_dfs(0, self.len, &v)
290        };
291        self.push_version_root(root)
292    }
293
294    pub fn set(
295        &mut self,
296        version: PersistentSegmentTreeVersion,
297        index: usize,
298        value: M::T,
299    ) -> PersistentSegmentTreeVersion {
300        assert!(index < self.len);
301        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
302        self.push_version_root(root)
303    }
304
305    pub fn update(
306        &mut self,
307        version: PersistentSegmentTreeVersion,
308        index: usize,
309        value: M::T,
310    ) -> PersistentSegmentTreeVersion {
311        assert!(index < self.len);
312        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
313        self.push_version_root(root)
314    }
315
316    #[must_use]
317    pub fn get(&self, version: PersistentSegmentTreeVersion, index: usize) -> M::T {
318        assert!(index < self.len);
319        Self::point_get_dfs(self.version_root(version), 0, self.len, index)
320    }
321
322    #[must_use]
323    pub fn fold<R>(&self, version: PersistentSegmentTreeVersion, range: R) -> M::T
324    where
325        R: RangeBounds<usize>,
326    {
327        let range = range.to_range_bounded(0, self.len).expect("invalid range");
328        if range.is_empty() {
329            M::unit()
330        } else {
331            Self::fold_dfs(self.version_root(version), 0, self.len, &range)
332        }
333    }
Source

fn partition_point_dfs<P>( node: Option<NonNull<Node<M::T>>>, start: usize, end: usize, left: usize, acc: &mut M::T, pred: &mut P, ) -> Option<usize>
where P: FnMut(&M::T) -> bool,

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 202)
176    fn partition_point_dfs<P>(
177        node: NodePtr<M::T>,
178        start: usize,
179        end: usize,
180        left: usize,
181        acc: &mut M::T,
182        pred: &mut P,
183    ) -> Option<usize>
184    where
185        P: FnMut(&M::T) -> bool,
186    {
187        if end <= left {
188            return None;
189        }
190        if left <= start {
191            let nacc = M::operate(acc, &Self::subtree_value(node));
192            if pred(&nacc) {
193                *acc = nacc;
194                return None;
195            }
196            if end - start == 1 {
197                return Some(start);
198            }
199        }
200        let mid = (start + end) / 2;
201        let [l, r] = Self::children(node);
202        if let Some(pos) = Self::partition_point_dfs(l, start, mid, left, acc, pred) {
203            Some(pos)
204        } else {
205            Self::partition_point_dfs(r, mid, end, left, acc, pred)
206        }
207    }
208
209    fn rpartition_point_dfs<P>(
210        node: NodePtr<M::T>,
211        start: usize,
212        end: usize,
213        right: usize,
214        acc: &mut M::T,
215        pred: &mut P,
216    ) -> Option<usize>
217    where
218        P: FnMut(&M::T) -> bool,
219    {
220        if right <= start {
221            return None;
222        }
223        if end <= right {
224            let nacc = M::operate(&Self::subtree_value(node), acc);
225            if pred(&nacc) {
226                *acc = nacc;
227                return None;
228            }
229            if end - start == 1 {
230                return Some(end);
231            }
232        }
233        let mid = (start + end) / 2;
234        let [l, r] = Self::children(node);
235        if let Some(pos) = Self::rpartition_point_dfs(r, mid, end, right, acc, pred) {
236            Some(pos)
237        } else {
238            Self::rpartition_point_dfs(l, start, mid, right, acc, pred)
239        }
240    }
241
242    fn set_dfs(
243        &mut self,
244        node: NodePtr<M::T>,
245        start: usize,
246        end: usize,
247        index: usize,
248        value: &M::T,
249    ) -> NodePtr<M::T> {
250        if end - start == 1 {
251            return self.leaf_node(value.clone());
252        }
253        let mid = (start + end) / 2;
254        let mut children = Self::children(node);
255        if index < mid {
256            children[0] = self.set_dfs(children[0], start, mid, index, value);
257        } else {
258            children[1] = self.set_dfs(children[1], mid, end, index, value);
259        }
260        self.merge_nodes(children[0], children[1])
261    }
262
263    fn update_dfs(
264        &mut self,
265        node: NodePtr<M::T>,
266        start: usize,
267        end: usize,
268        index: usize,
269        value: &M::T,
270    ) -> NodePtr<M::T> {
271        if end - start == 1 {
272            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
273        }
274        let mid = (start + end) / 2;
275        let mut children = Self::children(node);
276        if index < mid {
277            children[0] = self.update_dfs(children[0], start, mid, index, value);
278        } else {
279            children[1] = self.update_dfs(children[1], mid, end, index, value);
280        }
281        self.merge_nodes(children[0], children[1])
282    }
283
284    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
285        assert_eq!(v.len(), self.len);
286        let root = if self.len == 0 {
287            None
288        } else {
289            self.build_dfs(0, self.len, &v)
290        };
291        self.push_version_root(root)
292    }
293
294    pub fn set(
295        &mut self,
296        version: PersistentSegmentTreeVersion,
297        index: usize,
298        value: M::T,
299    ) -> PersistentSegmentTreeVersion {
300        assert!(index < self.len);
301        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
302        self.push_version_root(root)
303    }
304
305    pub fn update(
306        &mut self,
307        version: PersistentSegmentTreeVersion,
308        index: usize,
309        value: M::T,
310    ) -> PersistentSegmentTreeVersion {
311        assert!(index < self.len);
312        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
313        self.push_version_root(root)
314    }
315
316    #[must_use]
317    pub fn get(&self, version: PersistentSegmentTreeVersion, index: usize) -> M::T {
318        assert!(index < self.len);
319        Self::point_get_dfs(self.version_root(version), 0, self.len, index)
320    }
321
322    #[must_use]
323    pub fn fold<R>(&self, version: PersistentSegmentTreeVersion, range: R) -> M::T
324    where
325        R: RangeBounds<usize>,
326    {
327        let range = range.to_range_bounded(0, self.len).expect("invalid range");
328        if range.is_empty() {
329            M::unit()
330        } else {
331            Self::fold_dfs(self.version_root(version), 0, self.len, &range)
332        }
333    }
334
335    pub fn partition_point_acc<P>(
336        &self,
337        version: PersistentSegmentTreeVersion,
338        left: usize,
339        mut pred: P,
340    ) -> (usize, M::T)
341    where
342        P: FnMut(&M::T) -> bool,
343    {
344        let root = self.version_root(version);
345        let mut acc = M::unit();
346        let pos = if self.len == 0 {
347            None
348        } else {
349            Self::partition_point_dfs(root, 0, self.len, left, &mut acc, &mut pred)
350        };
351        (pos.unwrap_or(self.len), acc)
352    }
Source

fn rpartition_point_dfs<P>( node: Option<NonNull<Node<M::T>>>, start: usize, end: usize, right: usize, acc: &mut M::T, pred: &mut P, ) -> Option<usize>
where P: FnMut(&M::T) -> bool,

Examples found in repository?
crates/competitive/src/data_structure/persistent_segment_tree.rs (line 235)
209    fn rpartition_point_dfs<P>(
210        node: NodePtr<M::T>,
211        start: usize,
212        end: usize,
213        right: usize,
214        acc: &mut M::T,
215        pred: &mut P,
216    ) -> Option<usize>
217    where
218        P: FnMut(&M::T) -> bool,
219    {
220        if right <= start {
221            return None;
222        }
223        if end <= right {
224            let nacc = M::operate(&Self::subtree_value(node), acc);
225            if pred(&nacc) {
226                *acc = nacc;
227                return None;
228            }
229            if end - start == 1 {
230                return Some(end);
231            }
232        }
233        let mid = (start + end) / 2;
234        let [l, r] = Self::children(node);
235        if let Some(pos) = Self::rpartition_point_dfs(r, mid, end, right, acc, pred) {
236            Some(pos)
237        } else {
238            Self::rpartition_point_dfs(l, start, mid, right, acc, pred)
239        }
240    }
241
242    fn set_dfs(
243        &mut self,
244        node: NodePtr<M::T>,
245        start: usize,
246        end: usize,
247        index: usize,
248        value: &M::T,
249    ) -> NodePtr<M::T> {
250        if end - start == 1 {
251            return self.leaf_node(value.clone());
252        }
253        let mid = (start + end) / 2;
254        let mut children = Self::children(node);
255        if index < mid {
256            children[0] = self.set_dfs(children[0], start, mid, index, value);
257        } else {
258            children[1] = self.set_dfs(children[1], mid, end, index, value);
259        }
260        self.merge_nodes(children[0], children[1])
261    }
262
263    fn update_dfs(
264        &mut self,
265        node: NodePtr<M::T>,
266        start: usize,
267        end: usize,
268        index: usize,
269        value: &M::T,
270    ) -> NodePtr<M::T> {
271        if end - start == 1 {
272            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
273        }
274        let mid = (start + end) / 2;
275        let mut children = Self::children(node);
276        if index < mid {
277            children[0] = self.update_dfs(children[0], start, mid, index, value);
278        } else {
279            children[1] = self.update_dfs(children[1], mid, end, index, value);
280        }
281        self.merge_nodes(children[0], children[1])
282    }
283
284    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
285        assert_eq!(v.len(), self.len);
286        let root = if self.len == 0 {
287            None
288        } else {
289            self.build_dfs(0, self.len, &v)
290        };
291        self.push_version_root(root)
292    }
293
294    pub fn set(
295        &mut self,
296        version: PersistentSegmentTreeVersion,
297        index: usize,
298        value: M::T,
299    ) -> PersistentSegmentTreeVersion {
300        assert!(index < self.len);
301        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
302        self.push_version_root(root)
303    }
304
305    pub fn update(
306        &mut self,
307        version: PersistentSegmentTreeVersion,
308        index: usize,
309        value: M::T,
310    ) -> PersistentSegmentTreeVersion {
311        assert!(index < self.len);
312        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
313        self.push_version_root(root)
314    }
315
316    #[must_use]
317    pub fn get(&self, version: PersistentSegmentTreeVersion, index: usize) -> M::T {
318        assert!(index < self.len);
319        Self::point_get_dfs(self.version_root(version), 0, self.len, index)
320    }
321
322    #[must_use]
323    pub fn fold<R>(&self, version: PersistentSegmentTreeVersion, range: R) -> M::T
324    where
325        R: RangeBounds<usize>,
326    {
327        let range = range.to_range_bounded(0, self.len).expect("invalid range");
328        if range.is_empty() {
329            M::unit()
330        } else {
331            Self::fold_dfs(self.version_root(version), 0, self.len, &range)
332        }
333    }
334
335    pub fn partition_point_acc<P>(
336        &self,
337        version: PersistentSegmentTreeVersion,
338        left: usize,
339        mut pred: P,
340    ) -> (usize, M::T)
341    where
342        P: FnMut(&M::T) -> bool,
343    {
344        let root = self.version_root(version);
345        let mut acc = M::unit();
346        let pos = if self.len == 0 {
347            None
348        } else {
349            Self::partition_point_dfs(root, 0, self.len, left, &mut acc, &mut pred)
350        };
351        (pos.unwrap_or(self.len), acc)
352    }
353
354    pub fn rpartition_point_acc<P>(
355        &self,
356        version: PersistentSegmentTreeVersion,
357        right: usize,
358        mut pred: P,
359    ) -> (usize, M::T)
360    where
361        P: FnMut(&M::T) -> bool,
362    {
363        let root = self.version_root(version);
364        let mut acc = M::unit();
365        let pos = if self.len == 0 {
366            None
367        } else {
368            Self::rpartition_point_dfs(root, 0, self.len, right, &mut acc, &mut pred)
369        };
370        (pos.unwrap_or(0), acc)
371    }
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 256)
242    fn set_dfs(
243        &mut self,
244        node: NodePtr<M::T>,
245        start: usize,
246        end: usize,
247        index: usize,
248        value: &M::T,
249    ) -> NodePtr<M::T> {
250        if end - start == 1 {
251            return self.leaf_node(value.clone());
252        }
253        let mid = (start + end) / 2;
254        let mut children = Self::children(node);
255        if index < mid {
256            children[0] = self.set_dfs(children[0], start, mid, index, value);
257        } else {
258            children[1] = self.set_dfs(children[1], mid, end, index, value);
259        }
260        self.merge_nodes(children[0], children[1])
261    }
262
263    fn update_dfs(
264        &mut self,
265        node: NodePtr<M::T>,
266        start: usize,
267        end: usize,
268        index: usize,
269        value: &M::T,
270    ) -> NodePtr<M::T> {
271        if end - start == 1 {
272            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
273        }
274        let mid = (start + end) / 2;
275        let mut children = Self::children(node);
276        if index < mid {
277            children[0] = self.update_dfs(children[0], start, mid, index, value);
278        } else {
279            children[1] = self.update_dfs(children[1], mid, end, index, value);
280        }
281        self.merge_nodes(children[0], children[1])
282    }
283
284    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
285        assert_eq!(v.len(), self.len);
286        let root = if self.len == 0 {
287            None
288        } else {
289            self.build_dfs(0, self.len, &v)
290        };
291        self.push_version_root(root)
292    }
293
294    pub fn set(
295        &mut self,
296        version: PersistentSegmentTreeVersion,
297        index: usize,
298        value: M::T,
299    ) -> PersistentSegmentTreeVersion {
300        assert!(index < self.len);
301        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
302        self.push_version_root(root)
303    }
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 277)
263    fn update_dfs(
264        &mut self,
265        node: NodePtr<M::T>,
266        start: usize,
267        end: usize,
268        index: usize,
269        value: &M::T,
270    ) -> NodePtr<M::T> {
271        if end - start == 1 {
272            return self.leaf_node(M::operate(&Self::subtree_value(node), value));
273        }
274        let mid = (start + end) / 2;
275        let mut children = Self::children(node);
276        if index < mid {
277            children[0] = self.update_dfs(children[0], start, mid, index, value);
278        } else {
279            children[1] = self.update_dfs(children[1], mid, end, index, value);
280        }
281        self.merge_nodes(children[0], children[1])
282    }
283
284    pub fn from_vec(&mut self, v: Vec<M::T>) -> PersistentSegmentTreeVersion {
285        assert_eq!(v.len(), self.len);
286        let root = if self.len == 0 {
287            None
288        } else {
289            self.build_dfs(0, self.len, &v)
290        };
291        self.push_version_root(root)
292    }
293
294    pub fn set(
295        &mut self,
296        version: PersistentSegmentTreeVersion,
297        index: usize,
298        value: M::T,
299    ) -> PersistentSegmentTreeVersion {
300        assert!(index < self.len);
301        let root = self.set_dfs(self.version_root(version), 0, self.len, index, &value);
302        self.push_version_root(root)
303    }
304
305    pub fn update(
306        &mut self,
307        version: PersistentSegmentTreeVersion,
308        index: usize,
309        value: M::T,
310    ) -> PersistentSegmentTreeVersion {
311        assert!(index < self.len);
312        let root = self.update_dfs(self.version_root(version), 0, self.len, index, &value);
313        self.push_version_root(root)
314    }
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 partition_point_acc<P>( &self, version: PersistentSegmentTreeVersion, left: usize, pred: P, ) -> (usize, M::T)
where P: FnMut(&M::T) -> bool,

Source

pub fn rpartition_point_acc<P>( &self, version: PersistentSegmentTreeVersion, right: usize, pred: P, ) -> (usize, M::T)
where P: FnMut(&M::T) -> bool,

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 = !

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

fn try_from(value: U) -> Result<T, !>

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.