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: &Self::T, b: &Self::T) -> 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(0, 5)); // 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(0, 5)); // 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: &Self::T, b: &Self::T) -> Self::T {
111            (*a).min(*b)
112        }
113    }
114
115    let values = vec![7, 3, 9, 1, 6, 2, 8, 4];
116    let seg_tree = SegTree::<MinSpec>::from_vec(&values);
117
118    println!("Values: {:?}", values);
119    println!("Min of entire array: {}", seg_tree.query(0, 8)); // 1
120    println!("Min of [2, 5): {}", seg_tree.query(2, 5)); // min(9, 1, 6) = 1
121    println!("Min of [0, 3): {}", seg_tree.query(0, 3)); // min(7, 3, 9) = 3
122    println!("Min of [5, 8): {}", seg_tree.query(5, 8)); // min(2, 8, 4) = 2
123    println!();
124}
125
126/// Example 4: Custom LazySegTree for range add + range sum
127fn custom_lazy_example() {
128    println!("4. Custom LazySegTree for Range Add + Range Sum");
129    println!("----------------------------------------------");
130
131    // Define a spec for range add operations with sum queries
132    struct RangeAddSum;
133
134    impl LazySegTreeSpec for RangeAddSum {
135        type T = i64; // Data type (stores sums)
136        type U = i64; // Update type (add values)
137        const ID: Self::T = 0;
138
139        // Combine two sum values
140        fn op_on_data(d1: &Self::T, d2: &Self::T) -> Self::T {
141            d1 + d2
142        }
143
144        // Compose two add operations
145        fn op_on_update(u1: &Self::U, u2: &Self::U) -> Self::U {
146            u1 + u2
147        }
148
149        // Apply add operation to sum (multiply by range size)
150        fn op_update_on_data(u: &Self::U, d: &Self::T, size: usize) -> Self::T {
151            d + u * (size as i64)
152        }
153    }
154
155    let values = vec![1i64, 2, 3, 4, 5];
156    let mut lazy_tree = LazySegTree::<RangeAddSum>::from_vec(&values);
157
158    println!("Initial values: {:?}", values);
159    println!("Initial sum [1, 4): {}", lazy_tree.query(1, 4)); // 2 + 3 + 4 = 9
160    println!("Initial sum [0, 5): {}", lazy_tree.query(0, 5)); // 15
161
162    // Add 10 to all elements in range [1, 4)
163    lazy_tree.update(1, 4, 10);
164    println!("\nAfter adding 10 to range [1, 4):");
165    println!("Sum [1, 4): {}", lazy_tree.query(1, 4)); // (2+10) + (3+10) + (4+10) = 39
166    println!("Sum [0, 5): {}", lazy_tree.query(0, 5)); // 1 + 12 + 13 + 14 + 5 = 45
167
168    // Add 5 to range [0, 2)
169    lazy_tree.update(0, 2, 5);
170    println!("\nAfter adding 5 to range [0, 2):");
171    println!("Sum [0, 2): {}", lazy_tree.query(0, 2)); // (1+5) + (12+5) = 23
172    println!("Sum [0, 5): {}", lazy_tree.query(0, 5)); // 6 + 17 + 13 + 14 + 5 = 55
173    println!();
174}
175
176/// Example 5: Using LazySegTree helper types
177fn lazy_helper_example() {
178    println!("5. LazySegTree Helper Types");
179    println!("--------------------------");
180
181    // Range add + range sum
182    let values = vec![2i32, 4, 6, 8, 10];
183    let mut sum_tree = LazySegTreeAddSum::<i32>::from_vec(&values);
184
185    println!("Initial values: {:?}", values);
186    println!("Sum [0, 5): {}", sum_tree.query(0, 5)); // 30
187    println!("Sum [1, 4): {}", sum_tree.query(1, 4)); // 4 + 6 + 8 = 18
188
189    // Add 3 to range [1, 4)
190    sum_tree.update(1, 4, 3);
191    println!("\nAfter adding 3 to range [1, 4):");
192    println!("Sum [0, 5): {}", sum_tree.query(0, 5)); // 2 + 7 + 9 + 11 + 10 = 39
193    println!("Sum [1, 4): {}", sum_tree.query(1, 4)); // 7 + 9 + 11 = 27
194
195    // Add -2 to range [0, 3)
196    sum_tree.update(0, 3, -2);
197    println!("\nAfter subtracting 2 from range [0, 3):");
198    println!("Sum [0, 5): {}", sum_tree.query(0, 5)); // 0 + 5 + 7 + 11 + 10 = 33
199    println!("Sum [0, 3): {}", sum_tree.query(0, 3)); // 0 + 5 + 7 = 12
200
201    // Range add + range min
202    let min_values = vec![5, 2, 8, 1, 9, 3];
203    let mut min_tree = LazySegTreeAddMin::<i32>::from_vec(&min_values);
204    println!("\nInitial min values: {:?}", min_values);
205    println!("Min [0, 6): {}", min_tree.query(0, 6)); // 1
206    min_tree.update(1, 4, 2);
207    println!(
208        "After adding 2 to [1, 4): Min [0, 6): {}",
209        min_tree.query(0, 6)
210    ); // min(5, 4, 10, 3, 9, 3) = 3
211
212    // Range assignment (replace) + range sum
213    let rep_values = vec![1, 2, 3, 4, 5];
214    let mut rep_tree = LazySegTreeReplaceSum::<i32>::from_vec(&rep_values);
215    println!("\nInitial replace values: {:?}", rep_values);
216    println!("Sum [0, 5): {}", rep_tree.query(0, 5)); // 15
217    rep_tree.update(1, 4, 10); // Replace [1, 4) with 10
218    println!(
219        "After replacing [1, 4) with 10: Sum [0, 5): {}",
220        rep_tree.query(0, 5)
221    ); // 1 + 10 + 10 + 10 + 5 = 36
222    println!();
223}
224
225/// Example 6: Advanced lazy operations with overlapping updates
226fn advanced_lazy_example() {
227    println!("6. Advanced Lazy Operations");
228    println!("--------------------------");
229
230    let values = vec![1i32, 1, 1, 1, 1, 1, 1, 1]; // 8 ones
231    let mut tree = LazySegTreeAddSum::<i32>::from_vec(&values);
232
233    println!("Initial: 8 ones, sum = {}", tree.query(0, 8));
234
235    // Perform overlapping updates
236    tree.update(0, 4, 2); // Add 2 to first half
237    tree.update(2, 6, 3); // Add 3 to middle section (overlaps)
238    tree.update(4, 8, 1); // Add 1 to second half
239
240    println!("After overlapping updates:");
241    println!("Range [0, 2): sum = {}", tree.query(0, 2)); // (1+2) + (1+2) = 6
242    println!("Range [2, 4): sum = {}", tree.query(2, 4)); // (1+2+3) + (1+2+3) = 12
243    println!("Range [4, 6): sum = {}", tree.query(4, 6)); // (1+3+1) + (1+3+1) = 10
244    println!("Range [6, 8): sum = {}", tree.query(6, 8)); // (1+1) + (1+1) = 4
245    println!("Total sum: {}", tree.query(0, 8)); // 6 + 12 + 10 + 4 = 32
246
247    // Verify by querying individual ranges
248    let mut total = 0;
249    for i in 0..4 {
250        let range_sum = tree.query(i * 2, (i + 1) * 2);
251        total += range_sum;
252        println!("  Range [{}, {}): {}", i * 2, (i + 1) * 2, range_sum);
253    }
254    println!("Sum verification: {}", total);
255    println!();
256}
basic_usage/basic_usage.rs

basic_usage/
basic_usage.rs
