Struct SegmentTree

Source

pub struct SegmentTree<M>where
    M: Monoid,
{ /* private fields */ }

Implementations§

Source §

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

Source

pub fn new(n: usize) -> Self

Examples found in repository ?

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 81)

80    pub fn new(n: usize) -> Self {
81        let in_edges = SegmentTree::new(n);
82        let out_edges = SegmentTree::new(n);
83        let flow = SegmentTree::new(n);
84        Self {
85            n,
86            in_edges,
87            out_edges,
88            flow,
89        }
90    }

More examples

Hide additional examples

crates/aizu_online_judge/src/dsl/dsl_2_a.rs (line 10)

6pub fn dsl_2_a(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = SegmentTree::<MinOperation<_>>::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, x, y);
13        if ty == 0 {
14            seg.set(x, y as i32);
15        } else {
16            writeln!(writer, "{}", seg.fold(x..=y)).ok();
17        }
18    }
19}

crates/aizu_online_judge/src/dsl/dsl_2_b.rs (line 10)

6pub fn dsl_2_b(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = SegmentTree::<AdditiveOperation<_>>::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, x: Usize1, y);
13        if ty == 0 {
14            seg.update(x, y as i32);
15        } else {
16            writeln!(writer, "{}", seg.fold(x..y)).ok();
17        }
18    }
19}

Source

pub fn from_vec(v: Vec<M::T>) -> Self

Examples found in repository ?

crates/library_checker/src/datastructure/staticrmq.rs (line 24)

20pub fn staticrmq_segment_tree(reader: impl Read, mut writer: impl Write) {
21    let s = read_all_unchecked(reader);
22    let mut scanner = Scanner::new(&s);
23    scan!(scanner, n, q, a: [u64; n], lr: [(usize, usize)]);
24    let seg = SegmentTree::<MinOperation<_>>::from_vec(a);
25    for (l, r) in lr.take(q) {
26        writeln!(writer, "{}", seg.fold(l..r)).ok();
27    }
28}

More examples

Hide additional examples

crates/library_checker/src/datastructure/point_add_range_sum.rs (line 37)

33pub fn point_add_range_sum_segment_tree(reader: impl Read, mut writer: impl Write) {
34    let s = read_all_unchecked(reader);
35    let mut scanner = Scanner::new(&s);
36    scan!(scanner, n, q, a: [i64; n]);
37    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(a);
38    for _ in 0..q {
39        match scanner.scan::<usize>() {
40            0 => {
41                scan!(scanner, p, x: i64);
42                seg.update(p, x);
43            }
44            1 => {
45                scan!(scanner, l, r);
46                writeln!(writer, "{}", seg.fold(l..r)).ok();
47            }
48            _ => panic!("unknown query"),
49        }
50    }
51}

crates/library_checker/src/datastructure/point_set_range_composite.rs (line 14)

10pub fn point_set_range_composite(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, n, q, ab: [(MInt998244353, MInt998244353); n]);
14    let mut seg = SegmentTree::<LinearOperation<_>>::from_vec(ab);
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, p, cd: (MInt998244353, MInt998244353));
19                seg.set(p, cd);
20            }
21            1 => {
22                scan!(scanner, l, r, x: MInt998244353);
23                let (a, b) = seg.fold(l..r);
24                writeln!(writer, "{}", a * x + b).ok();
25            }
26            _ => panic!("unknown query"),
27        }
28    }
29}

crates/library_checker/src/datastructure/vertex_add_subtree_sum.rs (line 21)

9pub fn vertex_add_subtree_sum(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, a: [u64; n], p: [usize]);
13    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
14    let graph = UndirectedSparseGraph::from_edges(n, edges);
15    let mut et = EulerTourForVertex::new(&graph);
16    et.subtree_vertex_tour(0, n);
17    let mut b = vec![0; n];
18    for i in 0..n {
19        b[et.vidx[i].0] = a[i];
20    }
21    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
22    for _ in 0..q {
23        match scanner.scan::<usize>() {
24            0 => {
25                scan!(scanner, u, x: u64);
26                et.subtree_update(u, x, |k, x| seg.update(k, x));
27            }
28            1 => {
29                scan!(scanner, u);
30                writeln!(writer, "{}", et.subtree_query(u, |l, r| seg.fold(l..r))).ok();
31            }
32            _ => panic!("unknown query"),
33        }
34    }
35}

crates/library_checker/src/datastructure/vertex_set_path_composite.rs (line 21)

12pub fn vertex_set_path_composite(reader: impl Read, mut writer: impl Write) {
13    let s = read_all_unchecked(reader);
14    let mut scanner = Scanner::new(&s);
15    scan!(scanner, n, q, ab: [(MInt998244353, MInt998244353); n], (mut graph, _): @TreeGraphScanner::<usize, ()>::new(n));
16    let hld = HeavyLightDecomposition::new(0, &mut graph);
17    let mut nab = vec![(MInt998244353::default(), MInt998244353::default()); n];
18    for i in 0..n {
19        nab[hld.vidx[i]] = ab[i];
20    }
21    let mut seg1 = SegmentTree::<LinearOperation<_>>::from_vec(nab.clone());
22    let mut seg2 = SegmentTree::<ReverseOperation<LinearOperation<_>>>::from_vec(nab);
23    for _ in 0..q {
24        match scanner.scan::<usize>() {
25            0 => {
26                scan!(scanner, p, cd: (MInt998244353, MInt998244353));
27                seg1.set(hld.vidx[p], cd);
28                seg2.set(hld.vidx[p], cd);
29            }
30            1 => {
31                scan!(scanner, u, v, x: MInt998244353);
32                let (a, b) = hld.query_noncom::<LinearOperation<_>, _, _>(
33                    u,
34                    v,
35                    false,
36                    |l, r| seg1.fold(l..r),
37                    |l, r| seg2.fold(l..r),
38                );
39                writeln!(writer, "{}", a * x + b).ok();
40            }
41            _ => panic!("unknown query"),
42        }
43    }
44}

Source

pub fn set(&mut self, k: usize, x: M::T)

Examples found in repository ?

crates/competitive/src/data_structure/segment_tree.rs (line 70)

69    pub fn clear(&mut self, k: usize) {
70        self.set(k, M::unit());
71    }

More examples

Hide additional examples

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 93)

91    fn update_flow(&mut self, l: usize, r: usize, x: i32) {
92        let s = self.flow.get(l).sum + x;
93        self.flow.set(l, SumMinimum::singleton(s));
94        let s = self.flow.get(r).sum - x;
95        self.flow.set(r, SumMinimum::singleton(s));
96    }
97    pub unsafe fn set_push_unchecked(&mut self, i: usize, x: T) -> Option<T> {
98        assert!(i < self.n);
99        let p = self.flow.fold(i..self.n).sum;
100        let j = if p < 0 {
101            self.flow
102                .rposition_acc(0..i, |s| s.suffix_min + p >= 0)
103                .unwrap_or(0)
104        } else {
105            i
106        };
107        let (min, k) = self.out_edges.fold(j..self.n);
108        if x <= min {
109            self.in_edges.set(i, (x.clone(), Reverse(i)));
110            return Some(x);
111        }
112        if i <= k {
113            self.update_flow(i, k, 1);
114        } else {
115            self.update_flow(k, i, -1);
116        }
117        self.out_edges.set(i, (x.clone(), i));
118        self.out_edges.clear(k);
119        self.in_edges.set(k, (min.clone(), Reverse(k)));
120        if min == T::minimum() { None } else { Some(min) }
121    }
122    pub unsafe fn unset_pop_unchecked(&mut self, i: usize) -> Option<T> {
123        assert!(i < self.n);
124        if self.out_edges.get(i) == (T::minimum(), i) {
125            self.out_edges.clear(i);
126            return None;
127        }
128        let p = self.flow.fold(i..self.n).sum;
129        let j = if p < 0 {
130            self.flow
131                .rposition_acc(0..i, |s| s.suffix_min + p >= 0)
132                .unwrap_or(0)
133        } else {
134            i
135        };
136        let (min, k) = self.out_edges.fold(j..self.n);
137        assert_ne!(k, !0);
138        if i <= k {
139            self.update_flow(i, k, 1);
140        } else {
141            self.update_flow(k, i, -1);
142        }
143        self.in_edges.clear(i);
144        self.out_edges.clear(k);
145        self.in_edges.set(k, (min.clone(), Reverse(k)));
146        if min == T::minimum() { None } else { Some(min) }
147    }
148    pub unsafe fn set_pop_unchecked(&mut self, i: usize) -> Option<T> {
149        assert!(i < self.n);
150        let p = self.flow.fold(0..=i).sum;
151        let j = if p > 0 {
152            self.flow
153                .position_acc(i + 1..self.n - 1, |s| p + s.prefix_min <= 0)
154                .unwrap_or(self.n - 1)
155        } else {
156            i
157        };
158        let (max, Reverse(k)) = self.in_edges.fold(0..=j);
159        if max == T::minimum() {
160            self.out_edges.set(i, (T::minimum(), i));
161            return None;
162        }
163        if k <= i {
164            self.update_flow(k, i, 1);
165        } else {
166            self.update_flow(i, k, -1);
167        }
168        self.in_edges.set(i, (T::minimum(), Reverse(i)));
169        self.in_edges.clear(k);
170        self.out_edges.set(k, (max.clone(), k));
171        Some(max)
172    }
173    pub unsafe fn unset_push_unchecked(&mut self, i: usize) -> Option<T> {
174        assert!(i < self.n);
175        let (max, Reverse(k)) = self.in_edges.get(i);
176        if k == i && max != T::minimum() {
177            self.in_edges.clear(i);
178            return Some(max);
179        }
180        let p = self.flow.fold(0..=i).sum;
181        let j = if p > 0 {
182            self.flow
183                .position_acc(i + 1..self.n - 1, |s| p + s.prefix_min <= 0)
184                .unwrap_or(self.n - 1)
185        } else {
186            i
187        };
188        let (max, Reverse(k)) = self.in_edges.fold(0..=j);
189        if k <= i {
190            self.update_flow(k, i, 1);
191        } else {
192            self.update_flow(i, k, -1);
193        }
194        self.out_edges.clear(i);
195        self.in_edges.clear(k);
196        self.out_edges.set(k, (max.clone(), k));
197        if max == T::minimum() { None } else { Some(max) }
198    }

crates/aizu_online_judge/src/dsl/dsl_2_a.rs (line 14)

6pub fn dsl_2_a(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = SegmentTree::<MinOperation<_>>::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, x, y);
13        if ty == 0 {
14            seg.set(x, y as i32);
15        } else {
16            writeln!(writer, "{}", seg.fold(x..=y)).ok();
17        }
18    }
19}

crates/library_checker/src/datastructure/point_set_range_composite.rs (line 19)

10pub fn point_set_range_composite(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, n, q, ab: [(MInt998244353, MInt998244353); n]);
14    let mut seg = SegmentTree::<LinearOperation<_>>::from_vec(ab);
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, p, cd: (MInt998244353, MInt998244353));
19                seg.set(p, cd);
20            }
21            1 => {
22                scan!(scanner, l, r, x: MInt998244353);
23                let (a, b) = seg.fold(l..r);
24                writeln!(writer, "{}", a * x + b).ok();
25            }
26            _ => panic!("unknown query"),
27        }
28    }
29}

crates/library_checker/src/datastructure/vertex_set_path_composite.rs (line 27)

12pub fn vertex_set_path_composite(reader: impl Read, mut writer: impl Write) {
13    let s = read_all_unchecked(reader);
14    let mut scanner = Scanner::new(&s);
15    scan!(scanner, n, q, ab: [(MInt998244353, MInt998244353); n], (mut graph, _): @TreeGraphScanner::<usize, ()>::new(n));
16    let hld = HeavyLightDecomposition::new(0, &mut graph);
17    let mut nab = vec![(MInt998244353::default(), MInt998244353::default()); n];
18    for i in 0..n {
19        nab[hld.vidx[i]] = ab[i];
20    }
21    let mut seg1 = SegmentTree::<LinearOperation<_>>::from_vec(nab.clone());
22    let mut seg2 = SegmentTree::<ReverseOperation<LinearOperation<_>>>::from_vec(nab);
23    for _ in 0..q {
24        match scanner.scan::<usize>() {
25            0 => {
26                scan!(scanner, p, cd: (MInt998244353, MInt998244353));
27                seg1.set(hld.vidx[p], cd);
28                seg2.set(hld.vidx[p], cd);
29            }
30            1 => {
31                scan!(scanner, u, v, x: MInt998244353);
32                let (a, b) = hld.query_noncom::<LinearOperation<_>, _, _>(
33                    u,
34                    v,
35                    false,
36                    |l, r| seg1.fold(l..r),
37                    |l, r| seg2.fold(l..r),
38                );
39                writeln!(writer, "{}", a * x + b).ok();
40            }
41            _ => panic!("unknown query"),
42        }
43    }
44}

Source

pub fn clear(&mut self, k: usize)

Examples found in repository ?

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 118)

97    pub unsafe fn set_push_unchecked(&mut self, i: usize, x: T) -> Option<T> {
98        assert!(i < self.n);
99        let p = self.flow.fold(i..self.n).sum;
100        let j = if p < 0 {
101            self.flow
102                .rposition_acc(0..i, |s| s.suffix_min + p >= 0)
103                .unwrap_or(0)
104        } else {
105            i
106        };
107        let (min, k) = self.out_edges.fold(j..self.n);
108        if x <= min {
109            self.in_edges.set(i, (x.clone(), Reverse(i)));
110            return Some(x);
111        }
112        if i <= k {
113            self.update_flow(i, k, 1);
114        } else {
115            self.update_flow(k, i, -1);
116        }
117        self.out_edges.set(i, (x.clone(), i));
118        self.out_edges.clear(k);
119        self.in_edges.set(k, (min.clone(), Reverse(k)));
120        if min == T::minimum() { None } else { Some(min) }
121    }
122    pub unsafe fn unset_pop_unchecked(&mut self, i: usize) -> Option<T> {
123        assert!(i < self.n);
124        if self.out_edges.get(i) == (T::minimum(), i) {
125            self.out_edges.clear(i);
126            return None;
127        }
128        let p = self.flow.fold(i..self.n).sum;
129        let j = if p < 0 {
130            self.flow
131                .rposition_acc(0..i, |s| s.suffix_min + p >= 0)
132                .unwrap_or(0)
133        } else {
134            i
135        };
136        let (min, k) = self.out_edges.fold(j..self.n);
137        assert_ne!(k, !0);
138        if i <= k {
139            self.update_flow(i, k, 1);
140        } else {
141            self.update_flow(k, i, -1);
142        }
143        self.in_edges.clear(i);
144        self.out_edges.clear(k);
145        self.in_edges.set(k, (min.clone(), Reverse(k)));
146        if min == T::minimum() { None } else { Some(min) }
147    }
148    pub unsafe fn set_pop_unchecked(&mut self, i: usize) -> Option<T> {
149        assert!(i < self.n);
150        let p = self.flow.fold(0..=i).sum;
151        let j = if p > 0 {
152            self.flow
153                .position_acc(i + 1..self.n - 1, |s| p + s.prefix_min <= 0)
154                .unwrap_or(self.n - 1)
155        } else {
156            i
157        };
158        let (max, Reverse(k)) = self.in_edges.fold(0..=j);
159        if max == T::minimum() {
160            self.out_edges.set(i, (T::minimum(), i));
161            return None;
162        }
163        if k <= i {
164            self.update_flow(k, i, 1);
165        } else {
166            self.update_flow(i, k, -1);
167        }
168        self.in_edges.set(i, (T::minimum(), Reverse(i)));
169        self.in_edges.clear(k);
170        self.out_edges.set(k, (max.clone(), k));
171        Some(max)
172    }
173    pub unsafe fn unset_push_unchecked(&mut self, i: usize) -> Option<T> {
174        assert!(i < self.n);
175        let (max, Reverse(k)) = self.in_edges.get(i);
176        if k == i && max != T::minimum() {
177            self.in_edges.clear(i);
178            return Some(max);
179        }
180        let p = self.flow.fold(0..=i).sum;
181        let j = if p > 0 {
182            self.flow
183                .position_acc(i + 1..self.n - 1, |s| p + s.prefix_min <= 0)
184                .unwrap_or(self.n - 1)
185        } else {
186            i
187        };
188        let (max, Reverse(k)) = self.in_edges.fold(0..=j);
189        if k <= i {
190            self.update_flow(k, i, 1);
191        } else {
192            self.update_flow(i, k, -1);
193        }
194        self.out_edges.clear(i);
195        self.in_edges.clear(k);
196        self.out_edges.set(k, (max.clone(), k));
197        if max == T::minimum() { None } else { Some(max) }
198    }

Source

pub fn update(&mut self, k: usize, x: M::T)

Examples found in repository ?

crates/aizu_online_judge/src/dsl/dsl_2_b.rs (line 14)

6pub fn dsl_2_b(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = SegmentTree::<AdditiveOperation<_>>::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, x: Usize1, y);
13        if ty == 0 {
14            seg.update(x, y as i32);
15        } else {
16            writeln!(writer, "{}", seg.fold(x..y)).ok();
17        }
18    }
19}

More examples

Hide additional examples

crates/library_checker/src/datastructure/point_add_range_sum.rs (line 42)

33pub fn point_add_range_sum_segment_tree(reader: impl Read, mut writer: impl Write) {
34    let s = read_all_unchecked(reader);
35    let mut scanner = Scanner::new(&s);
36    scan!(scanner, n, q, a: [i64; n]);
37    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(a);
38    for _ in 0..q {
39        match scanner.scan::<usize>() {
40            0 => {
41                scan!(scanner, p, x: i64);
42                seg.update(p, x);
43            }
44            1 => {
45                scan!(scanner, l, r);
46                writeln!(writer, "{}", seg.fold(l..r)).ok();
47            }
48            _ => panic!("unknown query"),
49        }
50    }
51}

crates/library_checker/src/datastructure/vertex_add_subtree_sum.rs (line 26)

9pub fn vertex_add_subtree_sum(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, a: [u64; n], p: [usize]);
13    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
14    let graph = UndirectedSparseGraph::from_edges(n, edges);
15    let mut et = EulerTourForVertex::new(&graph);
16    et.subtree_vertex_tour(0, n);
17    let mut b = vec![0; n];
18    for i in 0..n {
19        b[et.vidx[i].0] = a[i];
20    }
21    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
22    for _ in 0..q {
23        match scanner.scan::<usize>() {
24            0 => {
25                scan!(scanner, u, x: u64);
26                et.subtree_update(u, x, |k, x| seg.update(k, x));
27            }
28            1 => {
29                scan!(scanner, u);
30                writeln!(writer, "{}", et.subtree_query(u, |l, r| seg.fold(l..r))).ok();
31            }
32            _ => panic!("unknown query"),
33        }
34    }
35}

Source

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

Examples found in repository ?

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

91    fn update_flow(&mut self, l: usize, r: usize, x: i32) {
92        let s = self.flow.get(l).sum + x;
93        self.flow.set(l, SumMinimum::singleton(s));
94        let s = self.flow.get(r).sum - x;
95        self.flow.set(r, SumMinimum::singleton(s));
96    }
97    pub unsafe fn set_push_unchecked(&mut self, i: usize, x: T) -> Option<T> {
98        assert!(i < self.n);
99        let p = self.flow.fold(i..self.n).sum;
100        let j = if p < 0 {
101            self.flow
102                .rposition_acc(0..i, |s| s.suffix_min + p >= 0)
103                .unwrap_or(0)
104        } else {
105            i
106        };
107        let (min, k) = self.out_edges.fold(j..self.n);
108        if x <= min {
109            self.in_edges.set(i, (x.clone(), Reverse(i)));
110            return Some(x);
111        }
112        if i <= k {
113            self.update_flow(i, k, 1);
114        } else {
115            self.update_flow(k, i, -1);
116        }
117        self.out_edges.set(i, (x.clone(), i));
118        self.out_edges.clear(k);
119        self.in_edges.set(k, (min.clone(), Reverse(k)));
120        if min == T::minimum() { None } else { Some(min) }
121    }
122    pub unsafe fn unset_pop_unchecked(&mut self, i: usize) -> Option<T> {
123        assert!(i < self.n);
124        if self.out_edges.get(i) == (T::minimum(), i) {
125            self.out_edges.clear(i);
126            return None;
127        }
128        let p = self.flow.fold(i..self.n).sum;
129        let j = if p < 0 {
130            self.flow
131                .rposition_acc(0..i, |s| s.suffix_min + p >= 0)
132                .unwrap_or(0)
133        } else {
134            i
135        };
136        let (min, k) = self.out_edges.fold(j..self.n);
137        assert_ne!(k, !0);
138        if i <= k {
139            self.update_flow(i, k, 1);
140        } else {
141            self.update_flow(k, i, -1);
142        }
143        self.in_edges.clear(i);
144        self.out_edges.clear(k);
145        self.in_edges.set(k, (min.clone(), Reverse(k)));
146        if min == T::minimum() { None } else { Some(min) }
147    }
148    pub unsafe fn set_pop_unchecked(&mut self, i: usize) -> Option<T> {
149        assert!(i < self.n);
150        let p = self.flow.fold(0..=i).sum;
151        let j = if p > 0 {
152            self.flow
153                .position_acc(i + 1..self.n - 1, |s| p + s.prefix_min <= 0)
154                .unwrap_or(self.n - 1)
155        } else {
156            i
157        };
158        let (max, Reverse(k)) = self.in_edges.fold(0..=j);
159        if max == T::minimum() {
160            self.out_edges.set(i, (T::minimum(), i));
161            return None;
162        }
163        if k <= i {
164            self.update_flow(k, i, 1);
165        } else {
166            self.update_flow(i, k, -1);
167        }
168        self.in_edges.set(i, (T::minimum(), Reverse(i)));
169        self.in_edges.clear(k);
170        self.out_edges.set(k, (max.clone(), k));
171        Some(max)
172    }
173    pub unsafe fn unset_push_unchecked(&mut self, i: usize) -> Option<T> {
174        assert!(i < self.n);
175        let (max, Reverse(k)) = self.in_edges.get(i);
176        if k == i && max != T::minimum() {
177            self.in_edges.clear(i);
178            return Some(max);
179        }
180        let p = self.flow.fold(0..=i).sum;
181        let j = if p > 0 {
182            self.flow
183                .position_acc(i + 1..self.n - 1, |s| p + s.prefix_min <= 0)
184                .unwrap_or(self.n - 1)
185        } else {
186            i
187        };
188        let (max, Reverse(k)) = self.in_edges.fold(0..=j);
189        if k <= i {
190            self.update_flow(k, i, 1);
191        } else {
192            self.update_flow(i, k, -1);
193        }
194        self.out_edges.clear(i);
195        self.in_edges.clear(k);
196        self.out_edges.set(k, (max.clone(), k));
197        if max == T::minimum() { None } else { Some(max) }
198    }
199    pub fn set_no_op(&mut self, i: usize) -> Changed<T> {
200        assert!(i < self.n);
201        let mut changed = Changed::default();
202        let (max, Reverse(k)) = self.in_edges.get(i);
203        let (min, kk) = self.out_edges.get(i);
204        if k != i && kk != i {
205            return changed;
206        }
207        if i == k && max == T::minimum() || i == kk && min == T::minimum() {
208            changed.inserted[0] = unsafe { self.unset_pop_unchecked(i) };
209        } else {
210            changed.removed[0] = unsafe { self.unset_push_unchecked(i) };
211        }
212        changed
213    }
214    pub fn set_push(&mut self, i: usize, x: T) -> Changed<T> {
215        assert!(i < self.n);
216        let mut changed = self.set_no_op(i);
217        changed.inserted[1] = unsafe { self.set_push_unchecked(i, x) };
218        changed
219    }
220    pub fn set_pop(&mut self, i: usize) -> Changed<T> {
221        assert!(i < self.n);
222        let mut changed = self.set_no_op(i);
223        changed.removed[1] = unsafe { self.set_pop_unchecked(i) };
224        changed
225    }
226    #[allow(dead_code)]
227    fn check(&self) -> Vec<T> {
228        let mut pq = vec![];
229        for i in 0..self.n {
230            let (max, Reverse(k)) = self.in_edges.get(i);
231            let (min, kk) = self.out_edges.get(i);
232            if k == i {
233                if max == T::minimum() {
234                    // pop 1 element
235                } else {
236                    // push (not pop)
237                    pq.push(max);
238                }
239            } else if kk == i {
240                if min == T::minimum() {
241                    // pop 0 element
242                } else {
243                    // push (poped)
244                }
245            } else {
246                // nop
247            }
248        }
249        pq.sort_unstable();
250        pq
251    }

Source

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

Examples found in repository ?

crates/library_checker/src/datastructure/staticrmq.rs (line 26)

20pub fn staticrmq_segment_tree(reader: impl Read, mut writer: impl Write) {
21    let s = read_all_unchecked(reader);
22    let mut scanner = Scanner::new(&s);
23    scan!(scanner, n, q, a: [u64; n], lr: [(usize, usize)]);
24    let seg = SegmentTree::<MinOperation<_>>::from_vec(a);
25    for (l, r) in lr.take(q) {
26        writeln!(writer, "{}", seg.fold(l..r)).ok();
27    }
28}

More examples

Hide additional examples

crates/aizu_online_judge/src/dsl/dsl_2_a.rs (line 16)

6pub fn dsl_2_a(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = SegmentTree::<MinOperation<_>>::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, x, y);
13        if ty == 0 {
14            seg.set(x, y as i32);
15        } else {
16            writeln!(writer, "{}", seg.fold(x..=y)).ok();
17        }
18    }
19}

crates/aizu_online_judge/src/dsl/dsl_2_b.rs (line 16)

6pub fn dsl_2_b(reader: impl Read, mut writer: impl Write) {
7    let s = read_all_unchecked(reader);
8    let mut scanner = Scanner::new(&s);
9    scan!(scanner, n, q);
10    let mut seg = SegmentTree::<AdditiveOperation<_>>::new(n);
11    for _ in 0..q {
12        scan!(scanner, ty, x: Usize1, y);
13        if ty == 0 {
14            seg.update(x, y as i32);
15        } else {
16            writeln!(writer, "{}", seg.fold(x..y)).ok();
17        }
18    }
19}

crates/library_checker/src/datastructure/point_add_range_sum.rs (line 46)

33pub fn point_add_range_sum_segment_tree(reader: impl Read, mut writer: impl Write) {
34    let s = read_all_unchecked(reader);
35    let mut scanner = Scanner::new(&s);
36    scan!(scanner, n, q, a: [i64; n]);
37    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(a);
38    for _ in 0..q {
39        match scanner.scan::<usize>() {
40            0 => {
41                scan!(scanner, p, x: i64);
42                seg.update(p, x);
43            }
44            1 => {
45                scan!(scanner, l, r);
46                writeln!(writer, "{}", seg.fold(l..r)).ok();
47            }
48            _ => panic!("unknown query"),
49        }
50    }
51}

crates/library_checker/src/datastructure/point_set_range_composite.rs (line 23)

10pub fn point_set_range_composite(reader: impl Read, mut writer: impl Write) {
11    let s = read_all_unchecked(reader);
12    let mut scanner = Scanner::new(&s);
13    scan!(scanner, n, q, ab: [(MInt998244353, MInt998244353); n]);
14    let mut seg = SegmentTree::<LinearOperation<_>>::from_vec(ab);
15    for _ in 0..q {
16        match scanner.scan::<usize>() {
17            0 => {
18                scan!(scanner, p, cd: (MInt998244353, MInt998244353));
19                seg.set(p, cd);
20            }
21            1 => {
22                scan!(scanner, l, r, x: MInt998244353);
23                let (a, b) = seg.fold(l..r);
24                writeln!(writer, "{}", a * x + b).ok();
25            }
26            _ => panic!("unknown query"),
27        }
28    }
29}

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 99)

97    pub unsafe fn set_push_unchecked(&mut self, i: usize, x: T) -> Option<T> {
98        assert!(i < self.n);
99        let p = self.flow.fold(i..self.n).sum;
100        let j = if p < 0 {
101            self.flow
102                .rposition_acc(0..i, |s| s.suffix_min + p >= 0)
103                .unwrap_or(0)
104        } else {
105            i
106        };
107        let (min, k) = self.out_edges.fold(j..self.n);
108        if x <= min {
109            self.in_edges.set(i, (x.clone(), Reverse(i)));
110            return Some(x);
111        }
112        if i <= k {
113            self.update_flow(i, k, 1);
114        } else {
115            self.update_flow(k, i, -1);
116        }
117        self.out_edges.set(i, (x.clone(), i));
118        self.out_edges.clear(k);
119        self.in_edges.set(k, (min.clone(), Reverse(k)));
120        if min == T::minimum() { None } else { Some(min) }
121    }
122    pub unsafe fn unset_pop_unchecked(&mut self, i: usize) -> Option<T> {
123        assert!(i < self.n);
124        if self.out_edges.get(i) == (T::minimum(), i) {
125            self.out_edges.clear(i);
126            return None;
127        }
128        let p = self.flow.fold(i..self.n).sum;
129        let j = if p < 0 {
130            self.flow
131                .rposition_acc(0..i, |s| s.suffix_min + p >= 0)
132                .unwrap_or(0)
133        } else {
134            i
135        };
136        let (min, k) = self.out_edges.fold(j..self.n);
137        assert_ne!(k, !0);
138        if i <= k {
139            self.update_flow(i, k, 1);
140        } else {
141            self.update_flow(k, i, -1);
142        }
143        self.in_edges.clear(i);
144        self.out_edges.clear(k);
145        self.in_edges.set(k, (min.clone(), Reverse(k)));
146        if min == T::minimum() { None } else { Some(min) }
147    }
148    pub unsafe fn set_pop_unchecked(&mut self, i: usize) -> Option<T> {
149        assert!(i < self.n);
150        let p = self.flow.fold(0..=i).sum;
151        let j = if p > 0 {
152            self.flow
153                .position_acc(i + 1..self.n - 1, |s| p + s.prefix_min <= 0)
154                .unwrap_or(self.n - 1)
155        } else {
156            i
157        };
158        let (max, Reverse(k)) = self.in_edges.fold(0..=j);
159        if max == T::minimum() {
160            self.out_edges.set(i, (T::minimum(), i));
161            return None;
162        }
163        if k <= i {
164            self.update_flow(k, i, 1);
165        } else {
166            self.update_flow(i, k, -1);
167        }
168        self.in_edges.set(i, (T::minimum(), Reverse(i)));
169        self.in_edges.clear(k);
170        self.out_edges.set(k, (max.clone(), k));
171        Some(max)
172    }
173    pub unsafe fn unset_push_unchecked(&mut self, i: usize) -> Option<T> {
174        assert!(i < self.n);
175        let (max, Reverse(k)) = self.in_edges.get(i);
176        if k == i && max != T::minimum() {
177            self.in_edges.clear(i);
178            return Some(max);
179        }
180        let p = self.flow.fold(0..=i).sum;
181        let j = if p > 0 {
182            self.flow
183                .position_acc(i + 1..self.n - 1, |s| p + s.prefix_min <= 0)
184                .unwrap_or(self.n - 1)
185        } else {
186            i
187        };
188        let (max, Reverse(k)) = self.in_edges.fold(0..=j);
189        if k <= i {
190            self.update_flow(k, i, 1);
191        } else {
192            self.update_flow(i, k, -1);
193        }
194        self.out_edges.clear(i);
195        self.in_edges.clear(k);
196        self.out_edges.set(k, (max.clone(), k));
197        if max == T::minimum() { None } else { Some(max) }
198    }

Additional examples can be found in:

Source

pub fn position_acc<R, F>(&self, range: R, f: F) -> Option<usize>
where R: RangeBounds<usize>, F: Fn(&M::T) -> bool,

Returns the first index that satisfies a accumlative predicate.

Examples found in repository ?

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 153)

148    pub unsafe fn set_pop_unchecked(&mut self, i: usize) -> Option<T> {
149        assert!(i < self.n);
150        let p = self.flow.fold(0..=i).sum;
151        let j = if p > 0 {
152            self.flow
153                .position_acc(i + 1..self.n - 1, |s| p + s.prefix_min <= 0)
154                .unwrap_or(self.n - 1)
155        } else {
156            i
157        };
158        let (max, Reverse(k)) = self.in_edges.fold(0..=j);
159        if max == T::minimum() {
160            self.out_edges.set(i, (T::minimum(), i));
161            return None;
162        }
163        if k <= i {
164            self.update_flow(k, i, 1);
165        } else {
166            self.update_flow(i, k, -1);
167        }
168        self.in_edges.set(i, (T::minimum(), Reverse(i)));
169        self.in_edges.clear(k);
170        self.out_edges.set(k, (max.clone(), k));
171        Some(max)
172    }
173    pub unsafe fn unset_push_unchecked(&mut self, i: usize) -> Option<T> {
174        assert!(i < self.n);
175        let (max, Reverse(k)) = self.in_edges.get(i);
176        if k == i && max != T::minimum() {
177            self.in_edges.clear(i);
178            return Some(max);
179        }
180        let p = self.flow.fold(0..=i).sum;
181        let j = if p > 0 {
182            self.flow
183                .position_acc(i + 1..self.n - 1, |s| p + s.prefix_min <= 0)
184                .unwrap_or(self.n - 1)
185        } else {
186            i
187        };
188        let (max, Reverse(k)) = self.in_edges.fold(0..=j);
189        if k <= i {
190            self.update_flow(k, i, 1);
191        } else {
192            self.update_flow(i, k, -1);
193        }
194        self.out_edges.clear(i);
195        self.in_edges.clear(k);
196        self.out_edges.set(k, (max.clone(), k));
197        if max == T::minimum() { None } else { Some(max) }
198    }

Source

pub fn rposition_acc<R, F>(&self, range: R, f: F) -> Option<usize>
where R: RangeBounds<usize>, F: Fn(&M::T) -> bool,

Returns the last index that satisfies a accumlative predicate.

Examples found in repository ?

crates/competitive/src/data_structure/partially_retroactive_priority_queue.rs (line 102)

97    pub unsafe fn set_push_unchecked(&mut self, i: usize, x: T) -> Option<T> {
98        assert!(i < self.n);
99        let p = self.flow.fold(i..self.n).sum;
100        let j = if p < 0 {
101            self.flow
102                .rposition_acc(0..i, |s| s.suffix_min + p >= 0)
103                .unwrap_or(0)
104        } else {
105            i
106        };
107        let (min, k) = self.out_edges.fold(j..self.n);
108        if x <= min {
109            self.in_edges.set(i, (x.clone(), Reverse(i)));
110            return Some(x);
111        }
112        if i <= k {
113            self.update_flow(i, k, 1);
114        } else {
115            self.update_flow(k, i, -1);
116        }
117        self.out_edges.set(i, (x.clone(), i));
118        self.out_edges.clear(k);
119        self.in_edges.set(k, (min.clone(), Reverse(k)));
120        if min == T::minimum() { None } else { Some(min) }
121    }
122    pub unsafe fn unset_pop_unchecked(&mut self, i: usize) -> Option<T> {
123        assert!(i < self.n);
124        if self.out_edges.get(i) == (T::minimum(), i) {
125            self.out_edges.clear(i);
126            return None;
127        }
128        let p = self.flow.fold(i..self.n).sum;
129        let j = if p < 0 {
130            self.flow
131                .rposition_acc(0..i, |s| s.suffix_min + p >= 0)
132                .unwrap_or(0)
133        } else {
134            i
135        };
136        let (min, k) = self.out_edges.fold(j..self.n);
137        assert_ne!(k, !0);
138        if i <= k {
139            self.update_flow(i, k, 1);
140        } else {
141            self.update_flow(k, i, -1);
142        }
143        self.in_edges.clear(i);
144        self.out_edges.clear(k);
145        self.in_edges.set(k, (min.clone(), Reverse(k)));
146        if min == T::minimum() { None } else { Some(min) }
147    }