1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

"""
Segment Tree Query Implementation
=================================
 
The query function decomposes [L, R] into precomputed ranges
and combines their values in O(log n) time.
"""
 
class SegmentTree:
    """
    Segment tree with query support.
    """
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n) if self.n > 0 else []
        self.arr = arr
        
        if self.n > 0:
            self._build(1, 0, self.n - 1)
    
    def _build(self, node, start, end):
        if start == end:
            self.tree[node] = self.arr[start]
            return
        
        mid = (start + end) // 2
        self._build(2 * node, start, mid)
        self._build(2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def query(self, L: int, R: int) -> int:
        """
        Query the sum of elements in range [L, R].
        
        Args:
            L: Left boundary (inclusive), 0-indexed
            R: Right boundary (inclusive), 0-indexed
        
        Returns:
            Sum of elements A[L] + A[L+1] + ... + A[R]
        
        Time Complexity: O(log n)
        """
        if self.n == 0 or L > R or L < 0 or R >= self.n:
            return 0  # Invalid query
        
        return self._query(1, 0, self.n - 1, L, R)
    
    def _query(self, node: int, start: int, end: int, L: int, R: int) -> int:
        """
        Recursive query helper.
        
        Args:
            node: Current node index in tree
            start, end: Range this node covers
            L, R: Query range
        
        Returns:
            Sum of elements in [L, R] that fall within [start, end]
        """
        # Case 1: No overlap
        # The query range [L, R] is completely outside [start, end]
        if R < start or L > end:
            return 0  # Identity element for sum
        
        # Case 2: Complete overlap
        # The node's range [start, end] is entirely within query range [L, R]
        if L <= start and end <= R:
            return self.tree[node]  # Use precomputed value
        
        # Case 3: Partial overlap
        # Need to check both children
        mid = (start + end) // 2
        
        left_sum = self._query(2 * node, start, mid, L, R)
        right_sum = self._query(2 * node + 1, mid + 1, end, L, R)
        
        return left_sum + right_sum
 
 
# Demonstration with step-by-step tracing
def trace_query():
    """Trace a query step by step."""
    arr = [1, 3, 5, 7, 9, 11]
    st = SegmentTree(arr)
    
    print("Array:", arr)
    print("\n" + "=" * 60)
    print("QUERY TRACING: Sum of [1, 4]")
    print("=" * 60)
    
    # Manual trace
    print("""
    Query: sum([1, 4]) = 3 + 5 + 7 + 9 = 24
    
    Starting at root: node=1, [0,5], query=[1,4]
    ├── Partial overlap (0 < 1, 5 > 4)
    │
    ├── Left child: node=2, [0,2], query=[1,4]
    │   ├── Partial overlap (0 < 1)
    │   │
    │   ├── Left child: node=4, [0,1], query=[1,4]
    │   │   ├── Partial overlap (0 < 1)
    │   │   │
    │   │   ├── Left child: node=8, [0,0], query=[1,4]
    │   │   │   └── NO OVERLAP (0 < 1) → return 0
    │   │   │
    │   │   └── Right child: node=9, [1,1], query=[1,4]
    │   │       └── COMPLETE OVERLAP (1 ≤ 1 ≤ 1 ≤ 4) → return 3
    │   │   
    │   │   → return 0 + 3 = 3
    │   │
    │   └── Right child: node=5, [2,2], query=[1,4]
    │       └── COMPLETE OVERLAP (1 ≤ 2 ≤ 2 ≤ 4) → return 5
    │   
    │   → return 3 + 5 = 8
    │
    └── Right child: node=3, [3,5], query=[1,4]
        ├── Partial overlap (5 > 4)
        │
        ├── Left child: node=6, [3,4], query=[1,4]
        │   └── COMPLETE OVERLAP (1 ≤ 3 ≤ 4 ≤ 4) → return 16
        │
        └── Right child: node=7, [5,5], query=[1,4]
            └── NO OVERLAP (5 > 4) → return 0
        
        → return 16 + 0 = 16
    
    Final: 8 + 16 = 24 ✓
    """)
    
    result = st.query(1, 4)
    print(f"Computed result: {result}")
    print(f"Expected: {sum(arr[1:5])}")
    print(f"Match: {result == sum(arr[1:5])}")
 
 
if __name__ == "__main__":
    trace_query()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

"""
Demonstration of O(log n) query complexity.
Count the nodes visited during queries.
"""
 
class SegmentTreeWithStats:
    """Segment tree that tracks query statistics."""
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n) if self.n > 0 else []
        
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)
        
        self.nodes_visited = 0
        self.visit_log = []
    
    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return
        
        mid = (start + end) // 2
        self._build(arr, 2 * node, start, mid)
        self._build(arr, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def query(self, L: int, R: int) -> int:
        """Query with statistics tracking."""
        self.nodes_visited = 0
        self.visit_log = []
        return self._query(1, 0, self.n - 1, L, R)
    
    def _query(self, node, start, end, L, R) -> int:
        self.nodes_visited += 1
        
        # No overlap
        if R < start or L > end:
            self.visit_log.append(
                f"Node {node} [{start},{end}]: No overlap → 0"
            )
            return 0
        
        # Complete overlap
        if L <= start and end <= R:
            self.visit_log.append(
                f"Node {node} [{start},{end}]: Complete overlap → {self.tree[node]}"
            )
            return self.tree[node]
        
        # Partial overlap
        self.visit_log.append(
            f"Node {node} [{start},{end}]: Partial overlap → descend"
        )
        
        mid = (start + end) // 2
        left = self._query(2 * node, start, mid, L, R)
        right = self._query(2 * node + 1, mid + 1, end, L, R)
        
        return left + right
    
    def print_stats(self, L, R, result):
        """Print query statistics."""
        import math
        expected_max = 4 * (math.ceil(math.log2(self.n)) + 1) if self.n > 1 else 1
        
        print(f"\nQuery [{L}, {R}] = {result}")
        print(f"  Nodes visited: {self.nodes_visited}")
        print(f"  Array size n: {self.n}")
        print(f"  log₂(n): {math.log2(self.n):.2f}")
        print(f"  Theoretical max: ~{expected_max} nodes")
        print(f"\n  Visit log:")
        for log in self.visit_log:
            print(f"    {log}")
 
 
def demonstrate_query_complexity():
    """Show that queries are O(log n)."""
    import math
    import random
    
    print("=" * 70)
    print("QUERY COMPLEXITY DEMONSTRATION")
    print("=" * 70)
    
    # Small example with detailed trace
    arr = [1, 3, 5, 7, 9, 11]
    st = SegmentTreeWithStats(arr)
    
    print(f"\nArray: {arr}")
    print(f"Size n = {len(arr)}, log₂(n) = {math.log2(len(arr)):.2f}")
    
    # Trace a few queries
    for (L, R) in [(0, 5), (1, 4), (2, 3), (0, 0)]:
        result = st.query(L, R)
        st.print_stats(L, R, result)
    
    # Statistics for larger arrays
    print("\n" + "=" * 70)
    print("SCALING BEHAVIOR")
    print("=" * 70)
    print(f"\n{'n':>10} {'log₂(n)':>10} {'Max nodes visited':>20}")
    print("-" * 42)
    
    for size in [10, 100, 1000, 10000, 100000]:
        arr = list(range(size))
        st = SegmentTreeWithStats(arr)
        
        max_visited = 0
        for _ in range(100):  # 100 random queries
            L = random.randint(0, size - 1)
            R = random.randint(L, size - 1)
            st.query(L, R)
            max_visited = max(max_visited, st.nodes_visited)
        
        log_n = math.log2(size)
        print(f"{size:>10} {log_n:>10.2f} {max_visited:>20}")
    
    print("\nObservation: Nodes visited grows as O(log n) ✓")
 
 
if __name__ == "__main__":
    demonstrate_query_complexity()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

"""
Query implementations for various segment tree operations.
"""
 
from typing import Callable, TypeVar
from math import gcd
 
T = TypeVar('T')
 
 
class GenericSegmentTree:
    """
    A generic segment tree supporting any associative operation.
    """
    
    def __init__(
        self,
        arr: list,
        combine: Callable[[T, T], T],
        identity: T
    ):
        """
        Initialize segment tree.
        
        Args:
            arr: Input array
            combine: Binary function to combine two values
            identity: Identity element for the operation
        """
        self.n = len(arr)
        self.combine = combine
        self.identity = identity
        self.tree = [identity] * (4 * self.n) if self.n > 0 else []
        
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)
    
    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return
        
        mid = (start + end) // 2
        self._build(arr, 2 * node, start, mid)
        self._build(arr, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.combine(
            self.tree[2 * node],
            self.tree[2 * node + 1]
        )
    
    def query(self, L: int, R: int) -> T:
        """Query the aggregate of [L, R]."""
        if self.n == 0 or L > R or L < 0 or R >= self.n:
            return self.identity
        return self._query(1, 0, self.n - 1, L, R)
    
    def _query(self, node, start, end, L, R) -> T:
        # No overlap
        if R < start or L > end:
            return self.identity
        
        # Complete overlap
        if L <= start and end <= R:
            return self.tree[node]
        
        # Partial overlap
        mid = (start + end) // 2
        left = self._query(2 * node, start, mid, L, R)
        right = self._query(2 * node + 1, mid + 1, end, L, R)
        return self.combine(left, right)
 
 
# Specialized implementations for common operations
 
class SumSegmentTree(GenericSegmentTree):
    """Range Sum Queries."""
    
    def __init__(self, arr):
        super().__init__(arr, lambda a, b: a + b, 0)
 
 
class MinSegmentTree(GenericSegmentTree):
    """Range Minimum Queries."""
    
    def __init__(self, arr):
        super().__init__(arr, min, float('inf'))
 
 
class MaxSegmentTree(GenericSegmentTree):
    """Range Maximum Queries."""
    
    def __init__(self, arr):
        super().__init__(arr, max, float('-inf'))
 
 
class GCDSegmentTree(GenericSegmentTree):
    """Range GCD Queries."""
    
    def __init__(self, arr):
        super().__init__(arr, gcd, 0)
 
 
class XORSegmentTree(GenericSegmentTree):
    """Range XOR Queries."""
    
    def __init__(self, arr):
        super().__init__(arr, lambda a, b: a ^ b, 0)
 
 
class ProductSegmentTree(GenericSegmentTree):
    """Range Product Queries (watch for overflow!)."""
    
    def __init__(self, arr):
        super().__init__(arr, lambda a, b: a * b, 1)
 
 
# Demonstration
def demonstrate_query_variants():
    """Show queries with different operations."""
    
    arr = [12, 6, 18, 9, 3, 15, 24, 8]
    print("Array:", arr)
    print()
    
    queries = [(0, 7), (2, 5), (0, 3), (4, 7)]
    
    # Sum queries
    st_sum = SumSegmentTree(arr)
    print("=== SUM QUERIES ===")
    for L, R in queries:
        result = st_sum.query(L, R)
        expected = sum(arr[L:R+1])
        print(f"  Sum[{L},{R}] = {result} (expected: {expected}) ✓")
    
    # Min queries
    print("\n=== MIN QUERIES ===")
    st_min = MinSegmentTree(arr)
    for L, R in queries:
        result = st_min.query(L, R)
        expected = min(arr[L:R+1])
        print(f"  Min[{L},{R}] = {result} (expected: {expected}) ✓")
    
    # Max queries
    print("\n=== MAX QUERIES ===")
    st_max = MaxSegmentTree(arr)
    for L, R in queries:
        result = st_max.query(L, R)
        expected = max(arr[L:R+1])
        print(f"  Max[{L},{R}] = {result} (expected: {expected}) ✓")
    
    # GCD queries
    print("\n=== GCD QUERIES ===")
    st_gcd = GCDSegmentTree(arr)
    from functools import reduce
    for L, R in queries:
        result = st_gcd.query(L, R)
        expected = reduce(gcd, arr[L:R+1])
        print(f"  GCD[{L},{R}] = {result} (expected: {expected}) ✓")
    
    # XOR queries
    print("\n=== XOR QUERIES ===")
    st_xor = XORSegmentTree(arr)
    for L, R in queries:
        result = st_xor.query(L, R)
        expected = reduce(lambda x, y: x ^ y, arr[L:R+1])
        print(f"  XOR[{L},{R}] = {result} (expected: {expected}) ✓")
 
 
if __name__ == "__main__":
    demonstrate_query_variants()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

"""
Testing edge cases in segment tree queries.
"""
 
class RobustSegmentTree:
    """Segment tree with robust edge case handling."""
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n) if self.n > 0 else []
        
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)
    
    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return
        
        mid = (start + end) // 2
        self._build(arr, 2 * node, start, mid)
        self._build(arr, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def query(self, L: int, R: int) -> int:
        """
        Query with comprehensive edge case handling.
        
        Returns:
            - Sum of [L, R] if valid
            - 0 for invalid/empty queries
        """
        # Edge case: Empty array
        if self.n == 0:
            return 0
        
        # Edge case: Invalid range (L > R)
        if L > R:
            return 0
        
        # Edge case: Out of bounds
        L = max(0, L)        # Clamp L to valid range
        R = min(self.n - 1, R)  # Clamp R to valid range
        
        if L > R:  # Check again after clamping
            return 0
        
        return self._query(1, 0, self.n - 1, L, R)
    
    def _query(self, node, start, end, L, R):
        if R < start or L > end:
            return 0
        if L <= start and end <= R:
            return self.tree[node]
        
        mid = (start + end) // 2
        return (self._query(2 * node, start, mid, L, R) +
                self._query(2 * node + 1, mid + 1, end, L, R))
 
 
def test_edge_cases():
    """Test all edge cases."""
    
    print("=" * 50)
    print("EDGE CASE TESTS")
    print("=" * 50)
    
    # Test 1: Empty array
    print("\n[Test 1] Empty array")
    empty_st = RobustSegmentTree([])
    result = empty_st.query(0, 0)
    print(f"  Query on empty: {result}")
    assert result == 0, "Empty array query should return 0"
    print("  ✓ Passed")
    
    # Test 2: Single element
    print("\n[Test 2] Single element array")
    single_st = RobustSegmentTree([42])
    result = single_st.query(0, 0)
    print(f"  Query [0,0]: {result}")
    assert result == 42, "Single element query should return that element"
    print("  ✓ Passed")
    
    # Test 3: Full range
    print("\n[Test 3] Full range query")
    arr = [1, 2, 3, 4, 5]
    st = RobustSegmentTree(arr)
    result = st.query(0, 4)
    print(f"  Query [0,4] on {arr}: {result}")
    assert result == 15, "Full range should equal sum of all elements"
    print("  ✓ Passed")
    
    # Test 4: L > R (invalid range)
    print("\n[Test 4] Invalid range (L > R)")
    result = st.query(3, 1)
    print(f"  Query [3,1]: {result}")
    assert result == 0, "Invalid range should return 0"
    print("  ✓ Passed")
    
    # Test 5: Out of bounds (negative L)
    print("\n[Test 5] Out of bounds (L < 0)")
    result = st.query(-5, 2)
    print(f"  Query [-5,2]: {result} (clamped to [0,2])")
    assert result == 6, "Should clamp and return sum of [0,2]"
    print("  ✓ Passed")
    
    # Test 6: Out of bounds (R >= n)
    print("\n[Test 6] Out of bounds (R >= n)")
    result = st.query(3, 100)
    print(f"  Query [3,100]: {result} (clamped to [3,4])")
    assert result == 9, "Should clamp and return sum of [3,4]"
    print("  ✓ Passed")
    
    # Test 7: Both bounds out of range, but valid after clamping
    print("\n[Test 7] Both bounds out of range")
    result = st.query(-10, 100)
    print(f"  Query [-10,100]: {result} (clamped to [0,4])")
    assert result == 15, "Should clamp and return full sum"
    print("  ✓ Passed")
    
    # Test 8: Completely out of bounds (no overlap after clamping)
    print("\n[Test 8] Completely out of bounds")
    result = st.query(-10, -5)
    print(f"  Query [-10,-5]: {result}")
    assert result == 0, "Completely out of bounds should return 0"
    print("  ✓ Passed")
    
    print("\n" + "=" * 50)
    print("ALL EDGE CASE TESTS PASSED!")
    print("=" * 50)
 
 
if __name__ == "__main__":
    test_edge_cases()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

"""
Optimized segment tree query implementations.
"""
 
class OptimizedSegmentTree:
    """
    Segment tree with optimized query implementation.
    """
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n) if self.n > 0 else []
        
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)
    
    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return
        
        mid = (start + end) // 2
        self._build(arr, 2 * node, start, mid)
        self._build(arr, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def query(self, L: int, R: int) -> int:
        """Optimized query with early termination."""
        
        # Early termination: full range query
        if L == 0 and R == self.n - 1:
            return self.tree[1]
        
        # Early termination: single element (could optimize further)
        if L == R:
            return self._query(1, 0, self.n - 1, L, R)
        
        return self._query(1, 0, self.n - 1, L, R)
    
    def _query(self, node: int, start: int, end: int, L: int, R: int) -> int:
        """
        Optimized recursive query.
        
        Optimizations:
        1. No overlap check comes first (most likely to trigger)
        2. Complete overlap doesn't recurse further
        3. Bit operations for child calculation (compiler usually optimizes anyway)
        """
        # Optimization: Check no overlap first (most common early termination)
        if end < L or start > R:
            return 0
        
        # Complete overlap - use precomputed value
        if L <= start and end <= R:
            return self.tree[node]
        
        # Partial overlap - must check children
        mid = (start + end) >> 1  # Bit shift instead of /2
        
        left_child = node << 1      # 2 * node
        right_child = (node << 1) | 1  # 2 * node + 1
        
        # Only recurse into children that have possible overlap
        left_result = 0
        right_result = 0
        
        if L <= mid:  # Query overlaps with left child
            left_result = self._query(left_child, start, mid, L, R)
        
        if R > mid:   # Query overlaps with right child
            right_result = self._query(right_child, mid + 1, end, L, R)
        
        return left_result + right_result
 
 
class MinimalRecursionSegmentTree:
    """
    Segment tree that minimizes unnecessary recursive calls.
    """
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n) if self.n > 0 else []
        
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)
    
    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return
        
        mid = (start + end) // 2
        self._build(arr, 2 * node, start, mid)
        self._build(arr, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def query(self, L: int, R: int) -> int:
        """Query with smarter recursion."""
        return self._query(1, 0, self.n - 1, L, R)
    
    def _query(self, node, start, end, L, R):
        # Complete overlap
        if L <= start and end <= R:
            return self.tree[node]
        
        mid = (start + end) // 2
        
        # Determine which children to visit
        left = 2 * node
        right = 2 * node + 1
        
        # If query is entirely in left half
        if R <= mid:
            return self._query(left, start, mid, L, R)
        
        # If query is entirely in right half
        if L > mid:
            return self._query(right, mid + 1, end, L, R)
        
        # Query spans both halves
        return (self._query(left, start, mid, L, mid) +
                self._query(right, mid + 1, end, mid + 1, R))
 
 
# Performance comparison (basic benchmark)
def compare_performance():
    """Compare original vs optimized implementations."""
    import time
    import random
    
    print("=" * 60)
    print("QUERY PERFORMANCE COMPARISON")
    print("=" * 60)
    
    sizes = [1000, 10000, 100000]
    
    for n in sizes:
        arr = [random.randint(1, 100) for _ in range(n)]
        
        st_basic = OptimizedSegmentTree(arr)
        st_minimal = MinimalRecursionSegmentTree(arr)
        
        # Generate random queries
        queries = [(random.randint(0, n-1), random.randint(0, n-1)) 
                   for _ in range(10000)]
        queries = [(min(L,R), max(L,R)) for L, R in queries]
        
        # Benchmark basic
        start_time = time.perf_counter()
        for L, R in queries:
            st_basic.query(L, R)
        basic_time = time.perf_counter() - start_time
        
        # Benchmark minimal recursion
        start_time = time.perf_counter()
        for L, R in queries:
            st_minimal.query(L, R)
        minimal_time = time.perf_counter() - start_time
        
        print(f"\nn = {n:,}, 10,000 queries:")
        print(f"  Optimized:         {basic_time:.4f}s")
        print(f"  Minimal recursion: {minimal_time:.4f}s")
 
 
if __name__ == "__main__":
    compare_performance()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230

"""
Complete Segment Tree with Query Operations
============================================
 
A production-ready implementation supporting:
- Construction in O(n)
- Range queries in O(log n)
- Multiple operation types
 
Usage:
    st = SegmentTree([1, 3, 5, 7, 9, 11])
    print(st.query(1, 4))  # Output: 24
"""
 
from typing import List, Callable, TypeVar
 
T = TypeVar('T')
 
 
class SegmentTree:
    """
    A flexible segment tree supporting various range queries.
    
    Time Complexity:
        - Build: O(n)
        - Query: O(log n)
    
    Space Complexity: O(n)
    """
    
    def __init__(
        self,
        arr: List[T],
        combine: Callable[[T, T], T] = lambda a, b: a + b,
        identity: T = 0
    ):
        """
        Build a segment tree from the input array.
        
        Args:
            arr: Input array
            combine: Binary associative function to combine values
            identity: Identity element for the combine function
        
        Example:
            # Sum tree (default)
            st = SegmentTree([1, 2, 3, 4, 5])
            
            # Min tree
            st = SegmentTree([1, 2, 3], min, float('inf'))
            
            # Max tree
            st = SegmentTree([1, 2, 3], max, float('-inf'))
        """
        self.n = len(arr)
        self.combine = combine
        self.identity = identity
        
        if self.n == 0:
            self.tree = []
            return
        
        self.tree = [identity] * (4 * self.n)
        self._build(arr, 1, 0, self.n - 1)
    
    def _build(self, arr: List[T], node: int, start: int, end: int) -> None:
        """Recursively build the segment tree."""
        if start == end:
            self.tree[node] = arr[start]
            return
        
        mid = (start + end) // 2
        left, right = 2 * node, 2 * node + 1
        
        self._build(arr, left, start, mid)
        self._build(arr, right, mid + 1, end)
        
        self.tree[node] = self.combine(self.tree[left], self.tree[right])
    
    def query(self, L: int, R: int) -> T:
        """
        Query the aggregate of elements in range [L, R].
        
        Args:
            L: Left index (inclusive), 0-indexed
            R: Right index (inclusive), 0-indexed
        
        Returns:
            Aggregate of elements from index L to R
        
        Example:
            st = SegmentTree([1, 3, 5, 7, 9, 11])
            print(st.query(1, 4))  # 3 + 5 + 7 + 9 = 24
        """
        if self.n == 0:
            return self.identity
        
        if L < 0:
            L = 0
        if R >= self.n:
            R = self.n - 1
        if L > R:
            return self.identity
        
        return self._query(1, 0, self.n - 1, L, R)
    
    def _query(self, node: int, start: int, end: int, L: int, R: int) -> T:
        """Recursive query helper."""
        # No overlap
        if R < start or L > end:
            return self.identity
        
        # Complete overlap
        if L <= start and end <= R:
            return self.tree[node]
        
        # Partial overlap
        mid = (start + end) // 2
        left_result = self._query(2 * node, start, mid, L, R)
        right_result = self._query(2 * node + 1, mid + 1, end, L, R)
        
        return self.combine(left_result, right_result)
    
    def __repr__(self) -> str:
        """String representation of the segment tree."""
        if self.n == 0:
            return "SegmentTree(empty)"
        return f"SegmentTree(n={self.n}, root={self.tree[1]})"
 
 
# ============================================================
# Comprehensive Test Suite
# ============================================================
 
def run_all_tests():
    """Run comprehensive tests on segment tree queries."""
    
    print("=" * 60)
    print("SEGMENT TREE QUERY - COMPREHENSIVE TESTS")
    print("=" * 60)
    
    # Test 1: Basic Sum Queries
    print("\n[1] Basic Sum Queries")
    arr = [1, 3, 5, 7, 9, 11]
    st = SegmentTree(arr)
    
    test_cases = [
        ((0, 5), 36),  # Full range
        ((0, 0), 1),   # Single element (first)
        ((5, 5), 11),  # Single element (last)
        ((1, 4), 24),  # Middle range
        ((0, 2), 9),   # Prefix
        ((3, 5), 27),  # Suffix
    ]
    
    for (L, R), expected in test_cases:
        result = st.query(L, R)
        status = "✓" if result == expected else "✗"
        print(f"    Sum[{L},{R}] = {result} (expected: {expected}) {status}")
        assert result == expected
    
    # Test 2: Min Queries
    print("\n[2] Min Queries")
    st_min = SegmentTree(arr, min, float('inf'))
    min_cases = [
        ((0, 5), 1),
        ((2, 4), 5),
        ((4, 5), 9),
    ]
    
    for (L, R), expected in min_cases:
        result = st_min.query(L, R)
        status = "✓" if result == expected else "✗"
        print(f"    Min[{L},{R}] = {result} (expected: {expected}) {status}")
        assert result == expected
    
    # Test 3: Max Queries
    print("\n[3] Max Queries")
    st_max = SegmentTree(arr, max, float('-inf'))
    max_cases = [
        ((0, 5), 11),
        ((0, 3), 7),
        ((1, 2), 5),
    ]
    
    for (L, R), expected in max_cases:
        result = st_max.query(L, R)
        status = "✓" if result == expected else "✗"
        print(f"    Max[{L},{R}] = {result} (expected: {expected}) {status}")
        assert result == expected
    
    # Test 4: Edge Cases
    print("\n[4] Edge Cases")
    assert SegmentTree([]).query(0, 0) == 0, "Empty array"
    assert SegmentTree([42]).query(0, 0) == 42, "Single element"
    assert st.query(-1, 2) == 9, "Negative L (clamped)"
    assert st.query(4, 100) == 20, "R out of bounds (clamped)"
    print("    All edge cases passed ✓")
    
    # Test 5: Large Array Performance
    print("\n[5] Large Array Performance")
    import time
    import random
    
    large_arr = [random.randint(1, 1000) for _ in range(100000)]
    
    build_start = time.perf_counter()
    large_st = SegmentTree(large_arr)
    build_time = time.perf_counter() - build_start
    
    queries = [(random.randint(0, 99999), random.randint(0, 99999)) 
               for _ in range(10000)]
    queries = [(min(a,b), max(a,b)) for a, b in queries]
    
    query_start = time.perf_counter()
    for L, R in queries:
        large_st.query(L, R)
    query_time = time.perf_counter() - query_start
    
    print(f"    Build time (n=100,000): {build_time:.4f}s")
    print(f"    Query time (10,000 queries): {query_time:.4f}s")
    print(f"    Avg query time: {query_time/10000*1000000:.2f} µs")
    
    print("\n" + "=" * 60)
    print("ALL TESTS PASSED!")
    print("=" * 60)
 
 
if __name__ == "__main__":
    run_all_tests()