Skip to main content

SegmentTree

competitive::data_structure

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 15)
12pub fn dsl_2_a(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = SegmentTree::<MinOperation<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Update { x, y } => {
20                seg.set(x, y as i32);
21            }
22            Query::Fold { x, y } => {
23                pp!(seg.fold(x..=y));
24            }
25        }
26    }
27}
crates/aizu_online_judge/src/dsl/dsl_2_b.rs (line 15)
12pub fn dsl_2_b(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = SegmentTree::<AdditiveOperation<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Update { x, y } => {
20                seg.update(x, y as i32);
21            }
22            Query::Fold { x, y } => {
23                pp!(seg.fold(x..y));
24            }
25        }
26    }
27}
crates/library_checker/src/data_structure/point_set_range_composite_large_array.rs (line 31)
18pub fn point_set_range_composite_large_array(reader: impl Read, writer: impl Write) {
19    prepare_io!(buffered; reader, writer);
20    sc!(_n: u32, q, queries: [Query; q]);
21    let mut values: Vec<_> = queries
22        .iter()
23        .filter_map(|&query| match query {
24            Query::Set { p, .. } => Some(p),
25            _ => None,
26        })
27        .collect();
28    values.radix_sort_by_key(|&x| x);
29    values.dedup();
30    let search = StaticSearch::from_sorted(&values);
31    let mut seg = SegmentTree::<LinearOperation<M>>::new(values.len());
32    let mut endpoints = Vec::with_capacity(2 * q);
33    for &query in &queries {
34        match query {
35            Query::Set { p, .. } => endpoints.push(p),
36            Query::Apply { l, r, .. } => endpoints.extend([l, r]),
37        }
38    }
39    let mut positions = vec![0; endpoints.len()];
40    search.lower_bound_batch(&endpoints, &mut positions);
41    let mut positions = positions.into_iter();
42    for query in queries {
43        match query {
44            Query::Set { cd, .. } => seg.set(positions.next().unwrap(), cd),
45            Query::Apply { x, .. } => {
46                let l = positions.next().unwrap();
47                let r = positions.next().unwrap();
48                let (a, b) = seg.fold(l..r);
49                pp!(a * x + b);
50            }
51        }
52    }
53}
Source

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

Examples found in repository?
crates/library_checker/src/data_structure/staticrmq.rs (line 21)
18pub fn staticrmq_segment_tree(reader: impl Read, writer: impl Write) {
19    prepare_io!(reader, writer);
20    sc!(n, q, a: [u64; n], lr: [(usize, usize); iter q]);
21    let seg = SegmentTree::<MinOperation<_>>::from_vec(a);
22    for (l, r) in lr {
23        pp!(seg.fold(l..r));
24    }
25}
More examples
Hide additional examples
crates/library_checker/src/data_structure/point_add_range_sum.rs (line 39)
36pub fn point_add_range_sum_segment_tree(reader: impl Read, writer: impl Write) {
37    prepare_io!(reader, writer);
38    sc!(n, q, a: [i64; n]);
39    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(a);
40    for _ in 0..q {
41        sc!(query: Query);
42        match query {
43            Query::Add { p, x } => {
44                seg.update(p, x);
45            }
46            Query::Sum { l, r } => {
47                pp!(seg.fold(l..r));
48            }
49        }
50    }
51}
crates/library_checker/src/data_structure/point_set_range_composite.rs (line 17)
14pub fn point_set_range_composite(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, ab: [(M, M); n]);
17    let mut seg = SegmentTree::<LinearOperation<_>>::from_vec(ab);
18    for _ in 0..q {
19        sc!(query: Query);
20        match query {
21            Query::Set { p, cd } => {
22                seg.set(p, cd);
23            }
24            Query::Apply { l, r, x } => {
25                let (a, b) = seg.fold(l..r);
26                pp!(a * x + b);
27            }
28        }
29    }
30}
crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 48)
38pub fn vertex_add_subtree_sum_hld(reader: impl Read, writer: impl Write) {
39    prepare_io!(reader, writer);
40    sc!(n, q, a: [u64; n], p: [usize; iter n - 1]);
41    let edges = p.enumerate().map(|(i, p)| (i + 1, p)).collect();
42    let tree = UndirectedSparseGraph::from_edges(n, edges);
43    let hld = tree.hld(0);
44    let mut b = vec![0; n];
45    for (v, x) in a.into_iter().enumerate() {
46        b[hld.index(v)] = x;
47    }
48    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
49    for _ in 0..q {
50        sc!(query: Query);
51        match query {
52            Query::Add { u, x } => seg.update(hld.index(u), x),
53            Query::Sum { u } => {
54                pp!(seg.fold(hld.subtree_range(u)));
55            }
56        }
57    }
58}
crates/library_checker/src/data_structure/majority_voting.rs (lines 18-20)
15pub fn majority_voting(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, q, a: [i32; n]);
18    let mut seg = SegmentTree::<FindMajorityOperation<i32>>::from_vec(
19        a.iter().map(|&a| (Some(a), 1)).collect(),
20    );
21    let mut rf = RangeFrequency::new(a);
22    let mut out = vec![];
23    for _ in 0..q {
24        sc!(query: Query);
25        match query {
26            Query::Update { p, x } => {
27                seg.set(p, (Some(x), 1));
28                rf.set(p, x);
29            }
30            Query::Query { l, r } => {
31                let x = seg.fold(l..r).0.unwrap_or(-1);
32                out.push((x, r - l));
33                rf.query(l, r, x);
34            }
35        }
36    }
37    rf.execute_with_callback(|i, v| {
38        if out[i].1 >= 2 * v {
39            out[i].0 = -1;
40        }
41    });
42    pp!(@lf @it out.iter().map(|&(x, _)| x));
43}
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                .rpartition_point_acc(i, |s| s.suffix_min + p < 0)
103                .saturating_sub(1)
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                .rpartition_point_acc(i, |s| s.suffix_min + p < 0)
132                .saturating_sub(1)
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                .partition_point_acc(i + 1, |s| p + s.prefix_min > 0)
154                .min(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                .partition_point_acc(i + 1, |s| p + s.prefix_min > 0)
184                .min(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 20)
12pub fn dsl_2_a(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = SegmentTree::<MinOperation<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Update { x, y } => {
20                seg.set(x, y as i32);
21            }
22            Query::Fold { x, y } => {
23                pp!(seg.fold(x..=y));
24            }
25        }
26    }
27}
crates/library_checker/src/data_structure/point_set_range_composite.rs (line 22)
14pub fn point_set_range_composite(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, ab: [(M, M); n]);
17    let mut seg = SegmentTree::<LinearOperation<_>>::from_vec(ab);
18    for _ in 0..q {
19        sc!(query: Query);
20        match query {
21            Query::Set { p, cd } => {
22                seg.set(p, cd);
23            }
24            Query::Apply { l, r, x } => {
25                let (a, b) = seg.fold(l..r);
26                pp!(a * x + b);
27            }
28        }
29    }
30}
crates/library_checker/src/data_structure/majority_voting.rs (line 27)
15pub fn majority_voting(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, q, a: [i32; n]);
18    let mut seg = SegmentTree::<FindMajorityOperation<i32>>::from_vec(
19        a.iter().map(|&a| (Some(a), 1)).collect(),
20    );
21    let mut rf = RangeFrequency::new(a);
22    let mut out = vec![];
23    for _ in 0..q {
24        sc!(query: Query);
25        match query {
26            Query::Update { p, x } => {
27                seg.set(p, (Some(x), 1));
28                rf.set(p, x);
29            }
30            Query::Query { l, r } => {
31                let x = seg.fold(l..r).0.unwrap_or(-1);
32                out.push((x, r - l));
33                rf.query(l, r, x);
34            }
35        }
36    }
37    rf.execute_with_callback(|i, v| {
38        if out[i].1 >= 2 * v {
39            out[i].0 = -1;
40        }
41    });
42    pp!(@lf @it out.iter().map(|&(x, _)| x));
43}
crates/library_checker/src/data_structure/point_set_range_composite_large_array.rs (line 44)
18pub fn point_set_range_composite_large_array(reader: impl Read, writer: impl Write) {
19    prepare_io!(buffered; reader, writer);
20    sc!(_n: u32, q, queries: [Query; q]);
21    let mut values: Vec<_> = queries
22        .iter()
23        .filter_map(|&query| match query {
24            Query::Set { p, .. } => Some(p),
25            _ => None,
26        })
27        .collect();
28    values.radix_sort_by_key(|&x| x);
29    values.dedup();
30    let search = StaticSearch::from_sorted(&values);
31    let mut seg = SegmentTree::<LinearOperation<M>>::new(values.len());
32    let mut endpoints = Vec::with_capacity(2 * q);
33    for &query in &queries {
34        match query {
35            Query::Set { p, .. } => endpoints.push(p),
36            Query::Apply { l, r, .. } => endpoints.extend([l, r]),
37        }
38    }
39    let mut positions = vec![0; endpoints.len()];
40    search.lower_bound_batch(&endpoints, &mut positions);
41    let mut positions = positions.into_iter();
42    for query in queries {
43        match query {
44            Query::Set { cd, .. } => seg.set(positions.next().unwrap(), cd),
45            Query::Apply { x, .. } => {
46                let l = positions.next().unwrap();
47                let r = positions.next().unwrap();
48                let (a, b) = seg.fold(l..r);
49                pp!(a * x + b);
50            }
51        }
52    }
53}
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                .rpartition_point_acc(i, |s| s.suffix_min + p < 0)
103                .saturating_sub(1)
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                .rpartition_point_acc(i, |s| s.suffix_min + p < 0)
132                .saturating_sub(1)
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                .partition_point_acc(i + 1, |s| p + s.prefix_min > 0)
154                .min(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                .partition_point_acc(i + 1, |s| p + s.prefix_min > 0)
184                .min(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 20)
12pub fn dsl_2_b(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = SegmentTree::<AdditiveOperation<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Update { x, y } => {
20                seg.update(x, y as i32);
21            }
22            Query::Fold { x, y } => {
23                pp!(seg.fold(x..y));
24            }
25        }
26    }
27}
More examples
Hide additional examples
crates/library_checker/src/data_structure/point_add_range_sum.rs (line 44)
36pub fn point_add_range_sum_segment_tree(reader: impl Read, writer: impl Write) {
37    prepare_io!(reader, writer);
38    sc!(n, q, a: [i64; n]);
39    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(a);
40    for _ in 0..q {
41        sc!(query: Query);
42        match query {
43            Query::Add { p, x } => {
44                seg.update(p, x);
45            }
46            Query::Sum { l, r } => {
47                pp!(seg.fold(l..r));
48            }
49        }
50    }
51}
crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 52)
38pub fn vertex_add_subtree_sum_hld(reader: impl Read, writer: impl Write) {
39    prepare_io!(reader, writer);
40    sc!(n, q, a: [u64; n], p: [usize; iter n - 1]);
41    let edges = p.enumerate().map(|(i, p)| (i + 1, p)).collect();
42    let tree = UndirectedSparseGraph::from_edges(n, edges);
43    let hld = tree.hld(0);
44    let mut b = vec![0; n];
45    for (v, x) in a.into_iter().enumerate() {
46        b[hld.index(v)] = x;
47    }
48    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
49    for _ in 0..q {
50        sc!(query: Query);
51        match query {
52            Query::Add { u, x } => seg.update(hld.index(u), x),
53            Query::Sum { u } => {
54                pp!(seg.fold(hld.subtree_range(u)));
55            }
56        }
57    }
58}
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                .rpartition_point_acc(i, |s| s.suffix_min + p < 0)
103                .saturating_sub(1)
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                .rpartition_point_acc(i, |s| s.suffix_min + p < 0)
132                .saturating_sub(1)
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                .partition_point_acc(i + 1, |s| p + s.prefix_min > 0)
154                .min(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                .partition_point_acc(i + 1, |s| p + s.prefix_min > 0)
184                .min(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 23)
18pub fn staticrmq_segment_tree(reader: impl Read, writer: impl Write) {
19    prepare_io!(reader, writer);
20    sc!(n, q, a: [u64; n], lr: [(usize, usize); iter q]);
21    let seg = SegmentTree::<MinOperation<_>>::from_vec(a);
22    for (l, r) in lr {
23        pp!(seg.fold(l..r));
24    }
25}
More examples
Hide additional examples
crates/aizu_online_judge/src/dsl/dsl_2_a.rs (line 23)
12pub fn dsl_2_a(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = SegmentTree::<MinOperation<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Update { x, y } => {
20                seg.set(x, y as i32);
21            }
22            Query::Fold { x, y } => {
23                pp!(seg.fold(x..=y));
24            }
25        }
26    }
27}
crates/aizu_online_judge/src/dsl/dsl_2_b.rs (line 23)
12pub fn dsl_2_b(reader: impl Read, writer: impl Write) {
13    prepare_io!(reader, writer);
14    sc!(n, q);
15    let mut seg = SegmentTree::<AdditiveOperation<_>>::new(n);
16    for _ in 0..q {
17        sc!(query: Query);
18        match query {
19            Query::Update { x, y } => {
20                seg.update(x, y as i32);
21            }
22            Query::Fold { x, y } => {
23                pp!(seg.fold(x..y));
24            }
25        }
26    }
27}
crates/library_checker/src/data_structure/point_add_range_sum.rs (line 47)
36pub fn point_add_range_sum_segment_tree(reader: impl Read, writer: impl Write) {
37    prepare_io!(reader, writer);
38    sc!(n, q, a: [i64; n]);
39    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(a);
40    for _ in 0..q {
41        sc!(query: Query);
42        match query {
43            Query::Add { p, x } => {
44                seg.update(p, x);
45            }
46            Query::Sum { l, r } => {
47                pp!(seg.fold(l..r));
48            }
49        }
50    }
51}
crates/library_checker/src/data_structure/point_set_range_composite.rs (line 25)
14pub fn point_set_range_composite(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, ab: [(M, M); n]);
17    let mut seg = SegmentTree::<LinearOperation<_>>::from_vec(ab);
18    for _ in 0..q {
19        sc!(query: Query);
20        match query {
21            Query::Set { p, cd } => {
22                seg.set(p, cd);
23            }
24            Query::Apply { l, r, x } => {
25                let (a, b) = seg.fold(l..r);
26                pp!(a * x + b);
27            }
28        }
29    }
30}
crates/library_checker/src/tree/vertex_add_subtree_sum.rs (line 54)
38pub fn vertex_add_subtree_sum_hld(reader: impl Read, writer: impl Write) {
39    prepare_io!(reader, writer);
40    sc!(n, q, a: [u64; n], p: [usize; iter n - 1]);
41    let edges = p.enumerate().map(|(i, p)| (i + 1, p)).collect();
42    let tree = UndirectedSparseGraph::from_edges(n, edges);
43    let hld = tree.hld(0);
44    let mut b = vec![0; n];
45    for (v, x) in a.into_iter().enumerate() {
46        b[hld.index(v)] = x;
47    }
48    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(b);
49    for _ in 0..q {
50        sc!(query: Query);
51        match query {
52            Query::Add { u, x } => seg.update(hld.index(u), x),
53            Query::Sum { u } => {
54                pp!(seg.fold(hld.subtree_range(u)));
55            }
56        }
57    }
58}
Additional examples can be found in:
Source

fn partition_point_perfect<P>( &self, pos: usize, acc: M::T, pred: P, ) -> (usize, M::T)
where P: FnMut(&M::T) -> bool,

Examples found in repository?
crates/competitive/src/data_structure/segment_tree.rs (line 158)
146    pub fn partition_point_acc<P>(&self, left: usize, mut pred: P) -> usize
147    where
148        P: FnMut(&M::T) -> bool,
149    {
150        let mut l = left + self.n;
151        let r = 2 * self.n;
152        let mut k = 0usize;
153        let mut acc = M::unit();
154        while l < r >> k {
155            if l & 1 != 0 {
156                let nacc = M::operate(&acc, &self.seg[l]);
157                if !pred(&nacc) {
158                    return self.partition_point_perfect(l, acc, pred).0;
159                }
160                acc = nacc;
161                l += 1;
162            }
163            l >>= 1;
164            k += 1;
165        }
166        for k in (0..k).rev() {
167            let r = r >> k;
168            if r & 1 != 0 {
169                let nacc = M::operate(&acc, &self.seg[r - 1]);
170                if !pred(&nacc) {
171                    return self.partition_point_perfect(r - 1, acc, pred).0;
172                }
173                acc = nacc;
174            }
175        }
176        self.n
177    }
Source

fn rpartition_point_perfect<P>( &self, pos: usize, acc: M::T, pred: P, ) -> (usize, M::T)
where P: FnMut(&M::T) -> bool,

Examples found in repository?
crates/competitive/src/data_structure/segment_tree.rs (line 197)
178    pub fn rpartition_point_acc<P>(&self, right: usize, mut pred: P) -> usize
179    where
180        P: FnMut(&M::T) -> bool,
181    {
182        let mut l = self.n;
183        let mut r = right + self.n;
184        let mut c = 0usize;
185        let mut k = 0usize;
186        let mut acc = M::unit();
187        while l >> k < r {
188            c <<= 1;
189            if l & (1 << k) != 0 {
190                l += 1 << k;
191                c += 1;
192            }
193            if r & 1 != 0 {
194                r -= 1;
195                let nacc = M::operate(&self.seg[r], &acc);
196                if !pred(&nacc) {
197                    return self.rpartition_point_perfect(r, acc, pred).0 + 1;
198                }
199                acc = nacc;
200            }
201            r >>= 1;
202            k += 1;
203        }
204        for k in (0..k).rev() {
205            if c & 1 != 0 {
206                l -= 1 << k;
207                let l = l >> k;
208                let nacc = M::operate(&self.seg[l], &acc);
209                if !pred(&nacc) {
210                    return self.rpartition_point_perfect(l, acc, pred).0 + 1;
211                }
212                acc = nacc;
213            }
214            c >>= 1;
215        }
216        0
217    }
Source

pub fn partition_point_acc<P>(&self, left: usize, pred: P) -> usize
where P: FnMut(&M::T) -> bool,

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                .partition_point_acc(i + 1, |s| p + s.prefix_min > 0)
154                .min(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                .partition_point_acc(i + 1, |s| p + s.prefix_min > 0)
184                .min(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 rpartition_point_acc<P>(&self, right: usize, pred: P) -> usize
where P: FnMut(&M::T) -> bool,

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                .rpartition_point_acc(i, |s| s.suffix_min + p < 0)
103                .saturating_sub(1)
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                .rpartition_point_acc(i, |s| s.suffix_min + p < 0)
132                .saturating_sub(1)
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    }
Source

pub fn as_slice(&self) -> &[M::T]

Source§

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

Source

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

Trait Implementations§

Source§

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

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<M> Debug for SegmentTree<M>
where M: Monoid<T: Debug>,

Source§

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

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<M> Freeze for SegmentTree<M>
where Vec<<M as Magma>::T>: Freeze,

§

impl<M> RefUnwindSafe for SegmentTree<M>
where Vec<<M as Magma>::T>: RefUnwindSafe,

§

impl<M> Send for SegmentTree<M>
where Vec<<M as Magma>::T>: Send,

§

impl<M> Sync for SegmentTree<M>
where Vec<<M as Magma>::T>: Sync,

§

impl<M> Unpin for SegmentTree<M>
where Vec<<M as Magma>::T>: Unpin,

§

impl<M> UnsafeUnpin for SegmentTree<M>
where Vec<<M as Magma>::T>: UnsafeUnpin,

§

impl<M> UnwindSafe for SegmentTree<M>
where Vec<<M as Magma>::T>: UnwindSafe,

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> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. 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> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
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.