Struct SegmentTree

Source

pub struct SegmentTree<M>where
    M: Monoid,{
    n: usize,
    seg: Vec<M::T>,
}

Fields§

§n: usize§seg: Vec<M::T>

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 17)

13pub fn dsl_2_a(reader: impl Read, mut writer: impl Write) {
14    let s = read_all_unchecked(reader);
15    let mut scanner = Scanner::new(&s);
16    scan!(scanner, n, q);
17    let mut seg = SegmentTree::<MinOperation<_>>::new(n);
18    for _ in 0..q {
19        scan!(scanner, query: Query);
20        match query {
21            Query::Update { x, y } => {
22                seg.set(x, y as i32);
23            }
24            Query::Fold { x, y } => {
25                writeln!(writer, "{}", seg.fold(x..=y)).ok();
26            }
27        }
28    }
29}

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

13pub fn dsl_2_b(reader: impl Read, mut writer: impl Write) {
14    let s = read_all_unchecked(reader);
15    let mut scanner = Scanner::new(&s);
16    scan!(scanner, n, q);
17    let mut seg = SegmentTree::<AdditiveOperation<_>>::new(n);
18    for _ in 0..q {
19        scan!(scanner, query: Query);
20        match query {
21            Query::Update { x, y } => {
22                seg.update(x, y as i32);
23            }
24            Query::Fold { x, y } => {
25                writeln!(writer, "{}", seg.fold(x..y)).ok();
26            }
27        }
28    }
29}

Source

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

Examples found in repository ?

crates/library_checker/src/data_structure/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/data_structure/point_add_range_sum.rs (line 42)

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

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

17pub fn point_set_range_composite(reader: impl Read, mut writer: impl Write) {
18    let s = read_all_unchecked(reader);
19    let mut scanner = Scanner::new(&s);
20    scan!(scanner, n, q, ab: [(MInt998244353, MInt998244353); n]);
21    let mut seg = SegmentTree::<LinearOperation<_>>::from_vec(ab);
22    for _ in 0..q {
23        scan!(scanner, query: Query);
24        match query {
25            Query::Set { p, cd } => {
26                seg.set(p, cd);
27            }
28            Query::Apply { l, r, x } => {
29                let (a, b) = seg.fold(l..r);
30                writeln!(writer, "{}", a * x + b).ok();
31            }
32        }
33    }
34}

crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 22)

15pub fn vertex_add_subtree_sum(reader: impl Read, mut writer: impl Write) {
16    let s = read_all_unchecked(reader);
17    let mut scanner = Scanner::new(&s);
18    scan!(scanner, n, q, a: [u64; n], p: [usize]);
19    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
20    let tree = UndirectedSparseGraph::from_edges(n, edges);
21    let (et, b) = tree.subtree_euler_tour_builder(0).build_with_rearrange(&a);
22    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { u, x } => {
27                et.update(u, x, |k, x| seg.update(k, x));
28            }
29            Query::Sum { u } => {
30                writeln!(writer, "{}", et.fold(u, |r| seg.fold(r))).ok();
31            }
32        }
33    }
34}

crates/library_checker/src/data_structure/majority_voting.rs (lines 20-22)

16pub fn majority_voting(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, q, a: [i32; n]);
20    let mut seg = SegmentTree::<FindMajorityOperation<i32>>::from_vec(
21        a.iter().map(|&a| (Some(a), 1)).collect(),
22    );
23    let mut rf = RangeFrequency::new(a);
24    let mut out = vec![];
25    for _ in 0..q {
26        scan!(scanner, query: Query);
27        match query {
28            Query::Update { p, x } => {
29                seg.set(p, (Some(x), 1));
30                rf.set(p, x);
31            }
32            Query::Query { l, r } => {
33                let x = seg.fold(l..r).0.unwrap_or(-1);
34                out.push((x, r - l));
35                rf.query(l, r, x);
36            }
37        }
38    }
39    rf.execute_with_callback(|i, v| {
40        if out[i].1 >= 2 * v {
41            out[i].0 = -1;
42        }
43    });
44    iter_print!(writer, @lf @it out.iter().map(|&(x, _)| x));
45}

crates/library_checker/src/tree/vertex_set_path_composite.rs (line 28)

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

Source

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

Examples found in repository ?

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

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

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 22)

13pub fn dsl_2_a(reader: impl Read, mut writer: impl Write) {
14    let s = read_all_unchecked(reader);
15    let mut scanner = Scanner::new(&s);
16    scan!(scanner, n, q);
17    let mut seg = SegmentTree::<MinOperation<_>>::new(n);
18    for _ in 0..q {
19        scan!(scanner, query: Query);
20        match query {
21            Query::Update { x, y } => {
22                seg.set(x, y as i32);
23            }
24            Query::Fold { x, y } => {
25                writeln!(writer, "{}", seg.fold(x..=y)).ok();
26            }
27        }
28    }
29}

crates/library_checker/src/data_structure/point_set_range_composite.rs (line 26)

17pub fn point_set_range_composite(reader: impl Read, mut writer: impl Write) {
18    let s = read_all_unchecked(reader);
19    let mut scanner = Scanner::new(&s);
20    scan!(scanner, n, q, ab: [(MInt998244353, MInt998244353); n]);
21    let mut seg = SegmentTree::<LinearOperation<_>>::from_vec(ab);
22    for _ in 0..q {
23        scan!(scanner, query: Query);
24        match query {
25            Query::Set { p, cd } => {
26                seg.set(p, cd);
27            }
28            Query::Apply { l, r, x } => {
29                let (a, b) = seg.fold(l..r);
30                writeln!(writer, "{}", a * x + b).ok();
31            }
32        }
33    }
34}

crates/library_checker/src/data_structure/majority_voting.rs (line 29)

16pub fn majority_voting(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, q, a: [i32; n]);
20    let mut seg = SegmentTree::<FindMajorityOperation<i32>>::from_vec(
21        a.iter().map(|&a| (Some(a), 1)).collect(),
22    );
23    let mut rf = RangeFrequency::new(a);
24    let mut out = vec![];
25    for _ in 0..q {
26        scan!(scanner, query: Query);
27        match query {
28            Query::Update { p, x } => {
29                seg.set(p, (Some(x), 1));
30                rf.set(p, x);
31            }
32            Query::Query { l, r } => {
33                let x = seg.fold(l..r).0.unwrap_or(-1);
34                out.push((x, r - l));
35                rf.query(l, r, x);
36            }
37        }
38    }
39    rf.execute_with_callback(|i, v| {
40        if out[i].1 >= 2 * v {
41            out[i].0 = -1;
42        }
43    });
44    iter_print!(writer, @lf @it out.iter().map(|&(x, _)| x));
45}

crates/library_checker/src/tree/vertex_set_path_composite.rs (line 34)

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

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 22)

13pub fn dsl_2_b(reader: impl Read, mut writer: impl Write) {
14    let s = read_all_unchecked(reader);
15    let mut scanner = Scanner::new(&s);
16    scan!(scanner, n, q);
17    let mut seg = SegmentTree::<AdditiveOperation<_>>::new(n);
18    for _ in 0..q {
19        scan!(scanner, query: Query);
20        match query {
21            Query::Update { x, y } => {
22                seg.update(x, y as i32);
23            }
24            Query::Fold { x, y } => {
25                writeln!(writer, "{}", seg.fold(x..y)).ok();
26            }
27        }
28    }
29}

More examples

Hide additional examples

crates/library_checker/src/data_structure/point_add_range_sum.rs (line 47)

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

crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 27)

15pub fn vertex_add_subtree_sum(reader: impl Read, mut writer: impl Write) {
16    let s = read_all_unchecked(reader);
17    let mut scanner = Scanner::new(&s);
18    scan!(scanner, n, q, a: [u64; n], p: [usize]);
19    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
20    let tree = UndirectedSparseGraph::from_edges(n, edges);
21    let (et, b) = tree.subtree_euler_tour_builder(0).build_with_rearrange(&a);
22    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { u, x } => {
27                et.update(u, x, |k, x| seg.update(k, x));
28            }
29            Query::Sum { u } => {
30                writeln!(writer, "{}", et.fold(u, |r| seg.fold(r))).ok();
31            }
32        }
33    }
34}

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/data_structure/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 25)

13pub fn dsl_2_a(reader: impl Read, mut writer: impl Write) {
14    let s = read_all_unchecked(reader);
15    let mut scanner = Scanner::new(&s);
16    scan!(scanner, n, q);
17    let mut seg = SegmentTree::<MinOperation<_>>::new(n);
18    for _ in 0..q {
19        scan!(scanner, query: Query);
20        match query {
21            Query::Update { x, y } => {
22                seg.set(x, y as i32);
23            }
24            Query::Fold { x, y } => {
25                writeln!(writer, "{}", seg.fold(x..=y)).ok();
26            }
27        }
28    }
29}

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

13pub fn dsl_2_b(reader: impl Read, mut writer: impl Write) {
14    let s = read_all_unchecked(reader);
15    let mut scanner = Scanner::new(&s);
16    scan!(scanner, n, q);
17    let mut seg = SegmentTree::<AdditiveOperation<_>>::new(n);
18    for _ in 0..q {
19        scan!(scanner, query: Query);
20        match query {
21            Query::Update { x, y } => {
22                seg.update(x, y as i32);
23            }
24            Query::Fold { x, y } => {
25                writeln!(writer, "{}", seg.fold(x..y)).ok();
26            }
27        }
28    }
29}

crates/library_checker/src/data_structure/point_add_range_sum.rs (line 50)

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

crates/library_checker/src/data_structure/point_set_range_composite.rs (line 29)

17pub fn point_set_range_composite(reader: impl Read, mut writer: impl Write) {
18    let s = read_all_unchecked(reader);
19    let mut scanner = Scanner::new(&s);
20    scan!(scanner, n, q, ab: [(MInt998244353, MInt998244353); n]);
21    let mut seg = SegmentTree::<LinearOperation<_>>::from_vec(ab);
22    for _ in 0..q {
23        scan!(scanner, query: Query);
24        match query {
25            Query::Set { p, cd } => {
26                seg.set(p, cd);
27            }
28            Query::Apply { l, r, x } => {
29                let (a, b) = seg.fold(l..r);
30                writeln!(writer, "{}", a * x + b).ok();
31            }
32        }
33    }
34}

crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 30)

15pub fn vertex_add_subtree_sum(reader: impl Read, mut writer: impl Write) {
16    let s = read_all_unchecked(reader);
17    let mut scanner = Scanner::new(&s);
18    scan!(scanner, n, q, a: [u64; n], p: [usize]);
19    let edges = p.take(n - 1).enumerate().map(|(i, p)| (i + 1, p)).collect();
20    let tree = UndirectedSparseGraph::from_edges(n, edges);
21    let (et, b) = tree.subtree_euler_tour_builder(0).build_with_rearrange(&a);
22    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
23    for _ in 0..q {
24        scan!(scanner, query: Query);
25        match query {
26            Query::Add { u, x } => {
27                et.update(u, x, |k, x| seg.update(k, x));
28            }
29            Query::Sum { u } => {
30                writeln!(writer, "{}", et.fold(u, |r| seg.fold(r))).ok();
31            }
32        }
33    }
34}

Additional examples can be found in:

Source

fn bisect_perfect<F>(&self, pos: usize, acc: M::T, f: F) -> (usize, M::T)
where F: Fn(&M::T) -> bool,

Examples found in repository ?

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

137    pub fn position_acc<R, F>(&self, range: R, f: F) -> Option<usize>
138    where
139        R: RangeBounds<usize>,
140        F: Fn(&M::T) -> bool,
141    {
142        let range = range.to_range_bounded(0, self.n).expect("invalid range");
143        let mut l = range.start + self.n;
144        let r = range.end + self.n;
145        let mut k = 0usize;
146        let mut acc = M::unit();
147        while l < r >> k {
148            if l & 1 != 0 {
149                let nacc = M::operate(&acc, &self.seg[l]);
150                if f(&nacc) {
151                    return Some(self.bisect_perfect(l, acc, f).0);
152                }
153                acc = nacc;
154                l += 1;
155            }
156            l >>= 1;
157            k += 1;
158        }
159        for k in (0..k).rev() {
160            let r = r >> k;
161            if r & 1 != 0 {
162                let nacc = M::operate(&acc, &self.seg[r - 1]);
163                if f(&nacc) {
164                    return Some(self.bisect_perfect(r - 1, acc, f).0);
165                }
166                acc = nacc;
167            }
168        }
169        None
170    }

Source

fn rbisect_perfect<F>(&self, pos: usize, acc: M::T, f: F) -> (usize, M::T)
where F: Fn(&M::T) -> bool,

Examples found in repository ?

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

172    pub fn rposition_acc<R, F>(&self, range: R, f: F) -> Option<usize>
173    where
174        R: RangeBounds<usize>,
175        F: Fn(&M::T) -> bool,
176    {
177        let range = range.to_range_bounded(0, self.n).expect("invalid range");
178        let mut l = range.start + self.n;
179        let mut r = range.end + self.n;
180        let mut c = 0usize;
181        let mut k = 0usize;
182        let mut acc = M::unit();
183        while l >> k < r {
184            c <<= 1;
185            if l & (1 << k) != 0 {
186                l += 1 << k;
187                c += 1;
188            }
189            if r & 1 != 0 {
190                r -= 1;
191                let nacc = M::operate(&self.seg[r], &acc);
192                if f(&nacc) {
193                    return Some(self.rbisect_perfect(r, acc, f).0);
194                }
195                acc = nacc;
196            }
197            r >>= 1;
198            k += 1;
199        }
200        for k in (0..k).rev() {
201            if c & 1 != 0 {
202                l -= 1 << k;
203                let l = l >> k;
204                let nacc = M::operate(&self.seg[l], &acc);
205                if f(&nacc) {
206                    return Some(self.rbisect_perfect(l, acc, f).0);
207                }
208                acc = nacc;
209            }
210            c >>= 1;
211        }
212        None
213    }

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    }