basic_usage/
basic_usage.rs

1//! Basic usage examples for array_range_query crate.
2//!
3//! This example demonstrates how to use both SegTree and LazySegTree
4//! for common operations like sum, min, max queries and range updates.
5
6use array_range_query::{
7    LazySegTree, LazySegTreeAddMin, LazySegTreeAddSum, LazySegTreeReplaceSum, LazySegTreeSpec,
8    SegTree, SegTreeMax, SegTreeMin, SegTreeSpec, SegTreeSum,
9};
10
11fn main() {
12    println!("=== Basic Segment Tree Examples ===\n");
13
14    // Example 1: Custom SegTree for sum operations
15    custom_sum_example();
16
17    // Example 2: Helper types for common operations
18    helper_types_example();
19
20    // Example 3: Custom min operation with detailed output
21    custom_min_example();
22
23    println!("\n=== Lazy Segment Tree Examples ===\n");
24
25    // Example 4: Custom LazySegTree for range add + range sum
26    custom_lazy_example();
27
28    // Example 5: Using LazySegTree helper types
29    lazy_helper_example();
30
31    // Example 6: Advanced lazy operations
32    advanced_lazy_example();
33}
34
35/// Example 1: Custom SegTree implementation for sum queries
36fn custom_sum_example() {
37    println!("1. Custom SegTree for Sum Operations");
38    println!("-----------------------------------");
39
40    // Define a custom spec for sum operations
41    struct SumSpec;
42
43    impl SegTreeSpec for SumSpec {
44        type T = i64;
45        const ID: Self::T = 0; // Identity element for addition
46
47        fn op(a: &mut Self::T, b: &Self::T) {
48            *a += *b;
49        }
50    }
51
52    let values = vec![1, 2, 3, 4, 5];
53    let mut seg_tree = SegTree::<SumSpec>::from_vec(&values);
54
55    println!("Initial values: {:?}", values);
56    println!("Sum of range [1, 4): {}", seg_tree.query(1..4)); // 2 + 3 + 4 = 9
57    println!("Sum of entire array [0, 5): {}", seg_tree.query(..)); // 15
58
59    // Update element at index 2 from 3 to 10
60    seg_tree.update(2, 10);
61    println!("\nAfter updating index 2 to 10:");
62    println!("Sum of range [1, 4): {}", seg_tree.query(1..4)); // 2 + 10 + 4 = 16
63    println!("Sum of entire array [0, 5): {}", seg_tree.query(..)); // 22
64    println!();
65}
66
67/// Example 2: Using helper types for common operations
68fn helper_types_example() {
69    println!("2. Helper Types for Common Operations");
70    println!("------------------------------------");
71
72    let values = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
73    println!("Values: {:?}", values);
74
75    // Sum operations
76    let mut sum_tree = SegTreeSum::<i32>::from_vec(&values);
77    println!("Range sum [2, 6): {}", sum_tree.query(2..6)); // 4 + 1 + 5 + 9 = 19
78
79    // Min operations
80    let mut min_tree = SegTreeMin::<i32>::from_vec(&values);
81    println!("Range min [2, 6): {}", min_tree.query(2..6)); // min(4, 1, 5, 9) = 1
82
83    // Max operations
84    let mut max_tree = SegTreeMax::<i32>::from_vec(&values);
85    println!("Range max [2, 6): {}", max_tree.query(2..6)); // max(4, 1, 5, 9) = 9
86
87    // Demonstrate updates
88    println!("\nAfter updating index 3 to 20:");
89    sum_tree.update(3, 20);
90    min_tree.update(3, 20);
91    max_tree.update(3, 20);
92
93    println!("Range sum [2, 6): {}", sum_tree.query(2..6)); // 4 + 20 + 5 + 9 = 38
94    println!("Range min [2, 6): {}", min_tree.query(2..6)); // min(4, 20, 5, 9) = 4
95    println!("Range max [2, 6): {}", max_tree.query(2..6)); // max(4, 20, 5, 9) = 20
96    println!();
97}
98
99/// Example 3: Custom min operation with detailed explanation
100fn custom_min_example() {
101    println!("3. Custom Min Operation with Details");
102    println!("-----------------------------------");
103
104    struct MinSpec;
105
106    impl SegTreeSpec for MinSpec {
107        type T = i32;
108        const ID: Self::T = i32::MAX; // Identity for min is maximum possible value
109
110        fn op(a: &mut Self::T, b: &Self::T) {
111            if *a > *b {
112                *a = *b;
113            }
114        }
115    }
116
117    let values = vec![7, 3, 9, 1, 6, 2, 8, 4];
118    let seg_tree = SegTree::<MinSpec>::from_vec(&values);
119
120    println!("Values: {:?}", values);
121    println!("Min of entire array: {}", seg_tree.query(..)); // 1
122    println!("Min of [2, 5): {}", seg_tree.query(2..5)); // min(9, 1, 6) = 1
123    println!("Min of [0, 3): {}", seg_tree.query(..3)); // min(7, 3, 9) = 3
124    println!("Min of [5, 8): {}", seg_tree.query(5..)); // min(2, 8, 4) = 2
125    println!();
126}
127
128/// Example 4: Custom LazySegTree for range add + range sum
129fn custom_lazy_example() {
130    println!("4. Custom LazySegTree for Range Add + Range Sum");
131    println!("----------------------------------------------");
132
133    // Define a spec for range add operations with sum queries
134    struct RangeAddSum;
135
136    impl LazySegTreeSpec for RangeAddSum {
137        type T = i64; // Data type (stores sums)
138        type U = i64; // Update type (add values)
139        const ID: Self::T = 0;
140
141        // Combine two sum values
142        fn op_on_data(d1: &mut Self::T, d2: &Self::T) {
143            *d1 += *d2;
144        }
145
146        // Compose two add operations
147        fn op_on_update(u1: &mut Self::U, u2: &Self::U) {
148            *u1 += *u2;
149        }
150
151        // Apply add operation to sum (multiply by range size)
152        fn op_update_on_data(u: &Self::U, d: &mut Self::T, size: usize) {
153            *d += u * (size as i64);
154        }
155    }
156
157    let values = vec![1i64, 2, 3, 4, 5];
158    let mut lazy_tree = LazySegTree::<RangeAddSum>::from_vec(&values);
159
160    println!("Initial values: {:?}", values);
161    println!("Initial sum [1, 4): {}", lazy_tree.query(1..4)); // 2 + 3 + 4 = 9
162    println!("Initial sum [0, 5): {}", lazy_tree.query(..)); // 15
163
164    // Add 10 to all elements in range [1, 4)
165    lazy_tree.update(1..4, 10);
166    println!("\nAfter adding 10 to range [1, 4):");
167    println!("Sum [1, 4): {}", lazy_tree.query(1..4)); // (2+10) + (3+10) + (4+10) = 39
168    println!("Sum [0, 5): {}", lazy_tree.query(..)); // 1 + 12 + 13 + 14 + 5 = 45
169
170    // Add 5 to range [0, 2)
171    lazy_tree.update(..2, 5);
172    println!("\nAfter adding 5 to range [0, 2):");
173    println!("Sum [0, 2): {}", lazy_tree.query(..2)); // (1+5) + (12+5) = 23
174    println!("Sum [0, 5): {}", lazy_tree.query(..)); // 6 + 17 + 13 + 14 + 5 = 55
175    println!();
176}
177
178/// Example 5: Using LazySegTree helper types
179fn lazy_helper_example() {
180    println!("5. LazySegTree Helper Types");
181    println!("--------------------------");
182
183    // Range add + range sum
184    let values = vec![2i32, 4, 6, 8, 10];
185    let mut sum_tree = LazySegTreeAddSum::<i32>::from_vec(&values);
186
187    println!("Initial values: {:?}", values);
188    println!("Sum [0, 5): {}", sum_tree.query(..)); // 30
189    println!("Sum [1, 4): {}", sum_tree.query(1..4)); // 4 + 6 + 8 = 18
190
191    // Add 3 to range [1, 4)
192    sum_tree.update(1..4, 3);
193    println!("\nAfter adding 3 to range [1, 4):");
194    println!("Sum [0, 5): {}", sum_tree.query(..)); // 2 + 7 + 9 + 11 + 10 = 39
195    println!("Sum [1, 4): {}", sum_tree.query(1..4)); // 7 + 9 + 11 = 27
196
197    // Add -2 to range [0, 3)
198    sum_tree.update(..3, -2);
199    println!("\nAfter subtracting 2 from range [0, 3):");
200    println!("Sum [0, 5): {}", sum_tree.query(..)); // 0 + 5 + 7 + 11 + 10 = 33
201    println!("Sum [0, 3): {}", sum_tree.query(..3)); // 0 + 5 + 7 = 12
202
203    // Range add + range min
204    let min_values = vec![5, 2, 8, 1, 9, 3];
205    let mut min_tree = LazySegTreeAddMin::<i32>::from_vec(&min_values);
206    println!("\nInitial min values: {:?}", min_values);
207    println!("Min [0, 6): {}", min_tree.query(..)); // 1
208    min_tree.update(1..4, 2);
209    println!(
210        "After adding 2 to [1, 4): Min [0, 6): {}",
211        min_tree.query(..)
212    ); // min(5, 4, 10, 3, 9, 3) = 3
213
214    // Range assignment (replace) + range sum
215    let rep_values = vec![1, 2, 3, 4, 5];
216    let mut rep_tree = LazySegTreeReplaceSum::<i32>::from_vec(&rep_values);
217    println!("\nInitial replace values: {:?}", rep_values);
218    println!("Sum [0, 5): {}", rep_tree.query(..)); // 15
219    rep_tree.update(1..4, 10); // Replace [1, 4) with 10
220    println!(
221        "After replacing [1, 4) with 10: Sum [0, 5): {}",
222        rep_tree.query(..)
223    ); // 1 + 10 + 10 + 10 + 5 = 36
224    println!();
225}
226
227/// Example 6: Advanced lazy operations with overlapping updates
228fn advanced_lazy_example() {
229    println!("6. Advanced Lazy Operations");
230    println!("--------------------------");
231
232    let values = vec![1i32, 1, 1, 1, 1, 1, 1, 1]; // 8 ones
233    let mut tree = LazySegTreeAddSum::<i32>::from_vec(&values);
234
235    println!("Initial: 8 ones, sum = {}", tree.query(..));
236
237    // Perform overlapping updates
238    tree.update(..4, 2); // Add 2 to first half
239    tree.update(2..6, 3); // Add 3 to middle section (overlaps)
240    tree.update(4.., 1); // Add 1 to second half
241
242    println!("After overlapping updates:");
243    println!("Range [0, 2): sum = {}", tree.query(..2)); // (1+2) + (1+2) = 6
244    println!("Range [2, 4): sum = {}", tree.query(2..4)); // (1+2+3) + (1+2+3) = 12
245    println!("Range [4, 6): sum = {}", tree.query(4..6)); // (1+3+1) + (1+3+1) = 10
246    println!("Range [6, 8): sum = {}", tree.query(6..)); // (1+1) + (1+1) = 4
247    println!("Total sum: {}", tree.query(..)); // 6 + 12 + 10 + 4 = 32
248
249    // Verify by querying individual ranges
250    let mut total = 0;
251    for i in 0..4 {
252        let range_sum = tree.query(i * 2..(i + 1) * 2);
253        total += range_sum;
254        println!("  Range [{}, {}): {}", i * 2, (i + 1) * 2, range_sum);
255    }
256    println!("Sum verification: {}", total);
257    println!();
258}
basic_usage/basic_usage.rs

basic_usage/
basic_usage.rs
