contest_algorithms/range_query/
mod.rs

1pub mod dynamic_arq;
2pub mod specs;
3pub mod sqrt_decomp;
4pub mod static_arq;
5pub use dynamic_arq::{ArqView, DynamicArq};
6pub use specs::ArqSpec;
7pub use static_arq::StaticArq;
8
9#[cfg(test)]
10mod test {
11    use super::specs::*;
12    use super::*;
13
14    #[test]
15    fn test_rmq() {
16        let mut arq = StaticArq::<AssignMin>::new(&[0; 10]);
17
18        assert_eq!(arq.query(0, 9), 0);
19
20        arq.update(2, 4, &-5);
21        arq.update(5, 7, &-3);
22        arq.update(1, 6, &1);
23
24        assert_eq!(arq.query(0, 9), -3);
25    }
26
27    #[test]
28    fn test_dynamic_rmq() {
29        let mut arq = DynamicArq::<AssignMin>::new(false);
30        let view = arq.build_from_slice(&[0; 10]);
31
32        assert_eq!(arq.query(view, 0, 9), 0);
33
34        arq.update(view, 2, 4, &-5);
35        arq.update(view, 5, 7, &-3);
36        arq.update(view, 1, 6, &1);
37
38        assert_eq!(arq.query(view, 0, 9), -3);
39    }
40
41    #[test]
42    fn test_persistent_rmq() {
43        let mut arq = DynamicArq::<AssignMin>::new(true);
44        let mut view = arq.build_from_slice(&[0; 10]);
45
46        let at_init = view;
47        view = arq.update(view, 2, 4, &-5);
48        let snapshot = view;
49        view = arq.update(view, 5, 7, &-3);
50        view = arq.update(view, 1, 6, &1);
51
52        assert_eq!(arq.query(at_init, 0, 9), 0);
53        assert_eq!(arq.query(snapshot, 0, 9), -5);
54        assert_eq!(arq.query(view, 0, 9), -3);
55    }
56
57    #[test]
58    fn test_huge_rmq() {
59        let quintillion = 1_000_000_000_000_000_000;
60        let mut arq = DynamicArq::<AssignMin>::new(false);
61        let view = arq.build_from_identity(9 * quintillion + 1);
62
63        arq.update(view, 2 * quintillion, 4 * quintillion, &-5);
64        arq.update(view, 5 * quintillion, 7 * quintillion, &-3);
65        arq.update(view, 1 * quintillion, 6 * quintillion, &1);
66
67        assert_eq!(arq.query(view, 0, 9 * quintillion), -3);
68    }
69
70    #[test]
71    fn test_range_sum() {
72        let mut arq = StaticArq::<AssignSum>::new(&[0; 10]);
73
74        assert_eq!(arq.query(0, 9), 0);
75
76        arq.update(1, 3, &10);
77        arq.update(3, 5, &1);
78
79        assert_eq!(arq.query(0, 9), 23);
80        assert_eq!(arq.query(10, 4), 0);
81    }
82
83    #[test]
84    fn test_dynamic_range_sum() {
85        let mut arq = DynamicArq::<AssignSum>::new(false);
86        let view = arq.build_from_slice(&[0; 10]);
87
88        assert_eq!(arq.query(view, 0, 9), 0);
89
90        arq.update(view, 1, 3, &10);
91        arq.update(view, 3, 5, &1);
92
93        assert_eq!(arq.query(view, 0, 9), 23);
94        assert_eq!(arq.query(view, 10, 4), 0);
95    }
96
97    #[test]
98    fn test_supply_demand() {
99        let mut arq = StaticArq::<SupplyDemand>::new(&[(0, 0, 0); 10]);
100
101        arq.update(1, 1, &(25, 100));
102        arq.update(3, 3, &(100, 30));
103        arq.update(9, 9, &(0, 20));
104
105        assert_eq!(arq.query(0, 9), (125, 150, 75));
106    }
107
108    #[test]
109    fn test_dynamic_supply_demand() {
110        let mut arq = DynamicArq::<SupplyDemand>::new(false);
111        let view = arq.build_from_identity(10);
112
113        arq.update(view, 1, 1, &(25, 100));
114        arq.update(view, 3, 3, &(100, 30));
115        arq.update(view, 9, 9, &(0, 20));
116
117        assert_eq!(arq.query(view, 0, 9), (125, 150, 75));
118    }
119
120    #[test]
121    fn test_binary_search_rmq() {
122        let vec = vec![2, 1, 0, -1, -2, -3, -4, -5];
123        let mut arq = StaticArq::<AssignMin>::new(&vec);
124        let first_neg = static_arq::first_negative(&mut arq);
125
126        arq.update(3, 7, &0);
127        let first_neg_zeros = static_arq::first_negative(&mut arq);
128
129        assert_eq!(first_neg, Some(3));
130        assert_eq!(first_neg_zeros, None);
131    }
132
133    #[test]
134    fn test_dynamic_binary_search_rmq() {
135        let vec = vec![2, 1, 0, -1, -2, -3, -4, -5];
136        let mut arq = DynamicArq::<AssignMin>::new(false);
137        let view = arq.build_from_slice(&vec);
138        let first_neg = dynamic_arq::first_negative(&mut arq, view);
139
140        arq.update(view, 3, 7, &0);
141        let first_neg_zeros = dynamic_arq::first_negative(&mut arq, view);
142
143        assert_eq!(first_neg, Some(3));
144        assert_eq!(first_neg_zeros, None);
145    }
146}
contest_algorithms/range_query/mod.rs

contest_algorithms/range_query/
mod.rs
