Segment Tree Operations - Learning Module

Loading content...

0/276

Time Complexity: O(log n) per Operation

The Mathematics of Efficiency

We've built segment trees, queried them, and updated them. Throughout, we've claimed O(log n) time per operation. But what does this really mean? How do we prove it? And how does this compare to alternatives?

This page consolidates the complexity analysis, providing rigorous proofs for each operation, exploring the constants hidden in Big-O notation, and benchmarking real-world performance. Understanding these details is crucial for making informed decisions about when to use segment trees versus alternatives.

What You Will Learn

By the end of this page, you will understand rigorous proofs for O(n) build and O(log n) query/update times, the constant factors hidden in Big-O, how segment trees compare to arrays, prefix sums, and Fenwick trees, when segment trees are the optimal choice, and practical performance benchmarks.

Build Complexity: O(n)

Claim: Building a segment tree from an array of n elements takes O(n) time.

Proof (by counting nodes):

The build algorithm visits each node exactly once and does O(1) work per node.

How many nodes are there?

Leaf nodes: Exactly n (one for each array element)
Internal nodes: At most n - 1 (a binary tree with n leaves has exactly n - 1 internal nodes)

Total nodes: n + (n - 1) = 2n - 1 = O(n)

Work per node:

Read array element (leaves): O(1)
Combine two children (internals): O(1)

Total: O(1) × O(n) = O(n)

Alternative Proof (by recurrence):

Let T(n) be the time to build a segment tree for n elements.

T(1) = O(1)                          // Single element: just store it
T(n) = T(n/2) + T(n/2) + O(1)        // Build two halves, then combine
     = 2T(n/2) + O(1)

By the Master Theorem (Case 1: a = 2, b = 2, f(n) = O(1)):

T(n) = O(n^(log₂2)) = O(n)

Note on the 4n allocation:

We allocate 4n space, but only ~2n nodes are actually used. The allocation itself takes O(n) time (initializing the array), which doesn't change the overall O(n) build complexity.

Preprocessing Amortization

The O(n) build cost is a one-time preprocessing step. If you perform q queries and u updates, the total time is O(n + (q + u) log n). For large q or u, the O(n) build becomes negligible compared to the O(q log n) or O(u log n) operation costs.

Query Complexity: O(log n)

Claim: Querying a range [L, R] takes O(log n) time.

Proof (by bounding nodes visited):

We need to show that a query visits at most O(log n) nodes.

Key Observation: At each level of the tree, the query visits at most 4 nodes.

Why? At any level, nodes can be classified as:

Completely outside [L, R] → Return immediately, don't count
Completely inside [L, R] → Return immediately, count as 1
Partially overlapping [L, R] → Must recurse into children

Detailed Bound:

At any level, there are at most 2 nodes with partial overlap.

Proof by contradiction:

Suppose three consecutive nodes A, B, C at some level all partially overlap [L, R].

A partially overlaps → L is inside A's range but not fully contained
B partially overlaps → But B is between A and C, so if A and C partially overlap, B must be fully contained in [L, R]
This contradicts B being partially overlapping

Therefore, at most 2 partial overlaps per level.

Counting visited nodes:

Partial overlaps at level i: at most 2
Complete overlaps at level i: at most 2 (they're counted but don't generate children visits)
No overlaps: don't contribute

Actually, a tighter analysis shows at most 4 nodes per level are visited: up to 2 that are fully contained (we stop), and up to 2 that are partial (we continue).

With O(log n) levels, total nodes visited: O(log n).

query_complexity_analysis.py
Python
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
"""
Empirical verification of O(log n) query complexity.
"""
 
import math
import random
 
 
class SegmentTreeWithStats:
    """Segment tree that counts nodes visited per query."""
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n) if self.n > 0 else []
        self.nodes_visited = 0
        
        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) -> tuple:
        """Returns (result, nodes_visited)."""
        self.nodes_visited = 0
        result = self._query(1, 0, self.n - 1, L, R)
        return result, self.nodes_visited
    
    def _query(self, node, start, end, L, R):
        self.nodes_visited += 1
        
        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 analyze_query_complexity():
    """Analyze and verify O(log n) query complexity."""
    
    print("=" * 70)
    print("QUERY COMPLEXITY ANALYSIS")
    print("=" * 70)
    
    print("\n" + "-" * 70)
    print(f"{'n':>10} {'log₂(n)':>10} {'4·log₂(n)':>12} {'Max Visited':>12} {'Ratio':>10}")
    print("-" * 70)
    
    results = []
    
    for n in [10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000]:
        arr = [random.randint(1, 100) for _ in range(n)]
        st = SegmentTreeWithStats(arr)
        
        max_visited = 0
        
        # Test 1000 random queries
        for _ in range(min(1000, n)):
            L = random.randint(0, n - 1)
            R = random.randint(L, n - 1)
            _, visited = st.query(L, R)
            max_visited = max(max_visited, visited)
        
        log_n = math.log2(n)
        theoretical_max = 4 * log_n + 4  # 4 per level + some constant
        ratio = max_visited / log_n
        
        results.append((n, log_n, max_visited, ratio))
        
        print(f"{n:>10} {log_n:>10.2f} {4*log_n:>12.2f} {max_visited:>12} {ratio:>10.2f}")
    
    print("-" * 70)
    print("\nObservations:")
    print("  • Max nodes visited grows proportionally to log₂(n)")
    print("  • Ratio (max_visited / log₂(n)) stays bounded")
    print("  • This confirms O(log n) complexity empirically")
    
    # Calculate average ratio
    avg_ratio = sum(r[3] for r in results) / len(results)
    print(f"  • Average ratio across all sizes: {avg_ratio:.2f}")
 
 
if __name__ == "__main__":
    analyze_query_complexity()

Update Complexity: O(log n)

Claim: Updating a single element takes O(log n) time.

Proof (by path length):

An update starts at the root and descends to a specific leaf:

At each node, we make exactly ONE recursive call (left OR right, never both)
We descend until reaching a leaf (when start == end)
The path length from root to any leaf is the tree height

Tree Height:

For n elements, the tree has height h where:

2^h ≥ n   (enough leaves to cover all elements)
h ≥ log₂(n)
h = ⌈log₂(n)⌉

Nodes on the path:

Going down: h + 1 nodes (root to leaf)
Coming back up: h nodes (propagating changes)
But we visit each node only once (during the return)

Total nodes: h + 1 = O(log n)

Work per node:

Comparison and recursion: O(1)
Combine operation: O(1)

Total: O(1) × O(log n) = O(log n)

Update Path Length Examples
n	Tree Height	Path Length	Theory (⌈log₂n⌉)
1	0	1	0
2	1	2	1
4	2	3	2
8	3	4	3
16	4	5	4
100	7	8	7
1,000	10	11	10
1,000,000	20	21	20

Query vs Update Complexity

Both query and update are O(log n), but for different reasons. Query visits at most O(log n) nodes because at most 2 nodes per level can have partial overlap. Update visits exactly log n + 1 nodes because updates follow a single path from root to leaf.

Space Complexity: O(n)

Claim: A segment tree uses O(n) space.

Analysis:

Actual nodes:

Leaves: n
Internal nodes: n - 1
Total: 2n - 1

Allocated space:

We allocate 4n to handle non-power-of-2 array sizes
Many slots remain unused (initialized to identity)

Auxiliary space (recursion):

Stack depth: O(log n)
Each frame: O(1)
Total auxiliary: O(log n)

Summary:

Tree storage: O(n)
Auxiliary (during operations): O(log n)
Total: O(n)

space_analysis.py
Python
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
"""
Space complexity analysis of segment trees.
"""
 
import sys
 
 
class SpaceAwareSegmentTree:
    """Segment tree with space tracking."""
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n) if self.n > 0 else []
        self._used_nodes = 0
        
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)
    
    def _build(self, arr, node, start, end):
        self._used_nodes += 1
        
        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 space_stats(self) -> dict:
        """Calculate space usage statistics."""
        allocated = len(self.tree)
        used = self._used_nodes
        wasted = allocated - used
        efficiency = (used / allocated * 100) if allocated > 0 else 0
        
        # Memory in bytes (assuming 8 bytes per integer)
        bytes_per_int = 8
        total_bytes = allocated * bytes_per_int
        
        return {
            "n": self.n,
            "allocated_slots": allocated,
            "used_slots": used,
            "wasted_slots": wasted,
            "efficiency": f"{efficiency:.1f}%",
            "theoretical_min": 2 * self.n - 1 if self.n > 0 else 0,
            "bytes": total_bytes,
            "bytes_per_element": total_bytes / self.n if self.n > 0 else 0
        }
 
 
def analyze_space():
    """Analyze space usage for various array sizes."""
    
    print("=" * 70)
    print("SPACE COMPLEXITY ANALYSIS")
    print("=" * 70)
    
    print("\n" + "-" * 70)
    print(f"{'n':>10} {'Allocated':>12} {'Used':>10} {'Efficiency':>12} {'Bytes/elem':>12}")
    print("-" * 70)
    
    test_sizes = [
        1, 2, 3, 4, 5, 7, 8, 10, 15, 16, 17,
        100, 128, 500, 512, 1000, 1024, 10000
    ]
    
    for n in test_sizes:
        arr = list(range(n))
        st = SpaceAwareSegmentTree(arr)
        stats = st.space_stats()
        
        is_power_of_2 = (n & (n - 1)) == 0 and n > 0
        marker = "⚡" if is_power_of_2 else ""
        
        print(f"{n:>10} {stats['allocated_slots']:>12} {stats['used_slots']:>10} "
              f"{stats['efficiency']:>12} {stats['bytes_per_element']:>10.1f}B {marker}")
    
    print("-" * 70)
    print("⚡ = Power of 2 (most efficient)")
    
    print("""
    
Key Observations:
    
1. Space Efficiency:
   - Best case (power of 2):  ~50% efficiency (used = 2n, allocated = 4n)
   - Worst case (2^k + 1):    ~25% efficiency
   - Average:                 ~37% efficiency
 
2. Memory per Element:
   - Ranges from 16 to 32 bytes per element
   - Compared to raw array: 8 bytes per element
   - Overhead factor: 2x to 4x
 
3. The 4n Rule:
   - Always allocating 4n is simple and sufficient
   - More precise: allocate 2 × 2^⌈log₂(n)⌉
   - Trade-off: simplicity vs memory efficiency
""")
 
 
if __name__ == "__main__":
    analyze_space()

Comparing Data Structures

Segment trees excel at specific problems. Let's compare them with alternatives:

Data Structure Comparison for Range Queries
Structure	Build	Point Update	Range Query	When to Use
Raw Array	O(n)	O(1)	O(n)	Few queries, or no updates needed with O(n) ok
Prefix Sums	O(n)	O(n)	O(1)	Many queries, no updates, sum only
Segment Tree	O(n)	O(log n)	O(log n)	Mix of queries and updates, any associative op
Fenwick Tree	O(n)	O(log n)	O(log n)	Simpler to implement, prefix queries, sum only
Sparse Table	O(n log n)	N/A	O(1)	No updates, idempotent ops (min/max/GCD)
Sqrt Decomposition	O(n)	O(1)	O(√n)	Simple to understand, moderate performance

Detailed Comparison:

Segment Tree vs. Prefix Sums:

Prefix sums give O(1) range sum queries but O(n) updates
Segment Tree: O(log n) for both
Crossover: If you have more than O(log n) queries per update, prefix sums win for sum queries

Segment Tree vs. Fenwick Tree (BIT):

Both have O(log n) query and update
Fenwick trees are simpler and have smaller constants
Segment trees are more general (support min/max/GCD, lazy propagation)
For simple prefix/range sums: prefer Fenwick
For anything else: prefer Segment Trees

Segment Tree vs. Sparse Table:

Sparse tables give O(1) queries after O(n log n) preprocessing
But they don't support updates
For static min/max/GCD queries: prefer Sparse Tables
For dynamic data: Segment Trees are the only option

Constant Factors and Real Performance

Big-O notation hides constant factors. Let's examine what's really happening inside those O(log n) operations:

Query Cost Breakdown (per level):

Parameter passing (4 integers: node, start, end, L, R)
Overlap check: 2 comparisons
Mid calculation: 1 integer operation
Two recursive calls (in case of partial overlap)
Combine operation: 1 addition/min/max

With ~log₂(n) levels and potentially 2 branches per level in the worst case, but typically much less.

Estimated Constants:

Query: ~20-30 simple operations per level
Update: ~15-20 simple operations per level (single path)
Per operation: ~20 × log₂(n) to ~30 × log₂(n) CPU operations

performance_benchmark.py
Python
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
"""
Performance benchmarking of segment tree operations.
Compares segment tree with alternative approaches.
"""
 
import time
import random
from typing import List
 
 
class SegmentTree:
    """Optimized segment tree for benchmarking."""
    
    __slots__ = ['n', 'tree']
    
    def __init__(self, arr: List[int]):
        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) >> 1
        left, right = node << 1, (node << 1) | 1
        self._build(arr, left, start, mid)
        self._build(arr, right, mid + 1, end)
        self.tree[node] = self.tree[left] + self.tree[right]
    
    def query(self, L: int, R: int) -> int:
        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) >> 1
        return (self._query(node << 1, start, mid, L, R) +
                self._query((node << 1) | 1, mid + 1, end, L, R))
    
    def update(self, idx: int, val: int):
        self._update(1, 0, self.n - 1, idx, val)
    
    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
            return
        mid = (start + end) >> 1
        if idx <= mid:
            self._update(node << 1, start, mid, idx, val)
        else:
            self._update((node << 1) | 1, mid + 1, end, idx, val)
        self.tree[node] = self.tree[node << 1] + self.tree[(node << 1) | 1]
 
 
class PrefixSums:
    """Prefix sum array for comparison."""
    
    def __init__(self, arr: List[int]):
        self.n = len(arr)
        self.arr = arr[:]
        self.prefix = [0] * (self.n + 1)
        self._rebuild()
    
    def _rebuild(self):
        for i in range(self.n):
            self.prefix[i + 1] = self.prefix[i] + self.arr[i]
    
    def query(self, L: int, R: int) -> int:
        return self.prefix[R + 1] - self.prefix[L]
    
    def update(self, idx: int, val: int):
        self.arr[idx] = val
        self._rebuild()  # O(n) rebuild
 
 
class NaiveArray:
    """Naive approach for comparison."""
    
    def __init__(self, arr: List[int]):
        self.arr = arr[:]
    
    def query(self, L: int, R: int) -> int:
        return sum(self.arr[L:R+1])
    
    def update(self, idx: int, val: int):
        self.arr[idx] = val
 
 
def benchmark():
    """Run comparative benchmarks."""
    
    print("=" * 70)
    print("PERFORMANCE BENCHMARKS")
    print("=" * 70)
    
    n = 100000
    num_queries = 10000
    num_updates = 1000
    
    arr = [random.randint(1, 1000) for _ in range(n)]
    queries = [(random.randint(0, n-1), random.randint(0, n-1)) for _ in range(num_queries)]
    queries = [(min(a, b), max(a, b)) for a, b in queries]
    updates = [(random.randint(0, n-1), random.randint(1, 1000)) for _ in range(num_updates)]
    
    print(f"\nArray size: {n:,}")
    print(f"Queries: {num_queries:,}")
    print(f"Updates: {num_updates:,}")
    
    print("\n" + "-" * 70)
    print("BUILD TIME")
    print("-" * 70)
    
    # Segment Tree
    start = time.perf_counter()
    st = SegmentTree(arr)
    st_build = time.perf_counter() - start
    print(f"Segment Tree:  {st_build*1000:.2f} ms")
    
    # Prefix Sums
    start = time.perf_counter()
    ps = PrefixSums(arr)
    ps_build = time.perf_counter() - start
    print(f"Prefix Sums:   {ps_build*1000:.2f} ms")
    
    # Naive
    start = time.perf_counter()
    na = NaiveArray(arr)
    na_build = time.perf_counter() - start
    print(f"Naive Array:   {na_build*1000:.2f} ms")
    
    print("\n" + "-" * 70)
    print("QUERY TIME (10,000 queries)")
    print("-" * 70)
    
    # Segment Tree queries
    start = time.perf_counter()
    for L, R in queries:
        st.query(L, R)
    st_query = time.perf_counter() - start
    print(f"Segment Tree:  {st_query*1000:.2f} ms ({st_query/num_queries*1e6:.2f} µs/query)")
    
    # Prefix Sums queries
    start = time.perf_counter()
    for L, R in queries:
        ps.query(L, R)
    ps_query = time.perf_counter() - start
    print(f"Prefix Sums:   {ps_query*1000:.2f} ms ({ps_query/num_queries*1e6:.2f} µs/query)")
    
    # Naive queries (sample only)
    sample_queries = queries[:100]
    start = time.perf_counter()
    for L, R in sample_queries:
        na.query(L, R)
    na_query = (time.perf_counter() - start) * (num_queries / 100)
    print(f"Naive Array:   ~{na_query*1000:.2f} ms ({na_query/num_queries*1e6:.2f} µs/query) [estimated]")
    
    print("\n" + "-" * 70)
    print("UPDATE TIME (1,000 updates)")
    print("-" * 70)
    
    # Segment Tree updates
    start = time.perf_counter()
    for idx, val in updates:
        st.update(idx, val)
    st_update = time.perf_counter() - start
    print(f"Segment Tree:  {st_update*1000:.2f} ms ({st_update/num_updates*1e6:.2f} µs/update)")
    
    # Prefix Sums updates (sample only - very slow)
    sample_updates = updates[:10]
    start = time.perf_counter()
    for idx, val in sample_updates:
        ps.update(idx, val)
    ps_update = (time.perf_counter() - start) * (num_updates / 10)
    print(f"Prefix Sums:   ~{ps_update*1000:.2f} ms ({ps_update/num_updates*1e6:.2f} µs/update) [estimated]")
    
    # Naive updates
    start = time.perf_counter()
    for idx, val in updates:
        na.update(idx, val)
    na_update = time.perf_counter() - start
    print(f"Naive Array:   {na_update*1000:.2f} ms ({na_update/num_updates*1e6:.2f} µs/update)")
    
    print("\n" + "-" * 70)
    print("SUMMARY")
    print("-" * 70)
    print("""
    For mixed workloads (queries + updates):
    • Segment Tree is the clear winner
    • O(log n) for both operations
    
    For query-only workloads:
    • Prefix Sums win with O(1) queries
    • But they break down if updates are needed
    
    For update-only workloads:
    • Naive array wins with O(1) updates
    • But they can't do fast range queries
    
    Segment Tree: The BALANCED solution
    """)
 
 
if __name__ == "__main__":
    benchmark()

When to Use Segment Trees

Based on our complexity analysis, here's a decision framework:

Use Segment Trees When:

•Binary queries + updates — You need range queries AND point updates, both frequent.
•Non-sum operations — You need min, max, GCD, or other associative operations that prefix sums can't handle.
•Range updates — With lazy propagation (covered in next module), segment trees support range updates efficiently.
•Persistent versions — Segment trees can be made persistent (immutable with history) more easily than alternatives.
•2D or higher dimensions — 2D segment trees solve 2D range query problems.

Don't Use Segment Trees When:

•Only queries, no updates — Use prefix sums (O(1) sum queries) or sparse tables (O(1) min/max/GCD queries).
•Only prefix sums needed — Fenwick trees are simpler and have smaller constants.
•Very small n — For n < 100, a naive O(n) approach might be faster due to lower overhead.
•Memory constrained — Segment trees use ~4n memory; consider alternatives if space is tight.
•Simpler problem — If the problem doesn't actually need range queries, don't overcomplicate.

Rule of Thumb

If you can't immediately see a simpler solution (prefix sums, Fenwick tree, sparse table), and the problem involves range queries with updates, reach for a segment tree. It's rarely the wrong choice for such problems.

Comprehensive Complexity Summary

Let's consolidate all the complexity results in one place:

Segment Tree Complexity Summary
Operation	Time	Space	Notes
Build	O(n)	O(n)	Visit all ~2n nodes once
Point Query	O(log n)	O(log n) stack	Follow single path to leaf
Range Query	O(log n)	O(log n) stack	At most 4 nodes per level
Point Update	O(log n)	O(log n) stack	Update path from leaf to root
Range Update*	O(log n)	O(log n) stack	*With lazy propagation
Space	O(n)		4n allocation is common

Comparison: Segment Tree vs Alternatives
Data Structure	Build	Query	Update	Best For
Segment Tree	O(n)	O(log n)	O(log n)	Mixed workloads, any op
Fenwick Tree	O(n)	O(log n)	O(log n)	Prefix sums, simpler
Prefix Sums	O(n)	O(1)	O(n)	Static sum queries
Sparse Table	O(n log n)	O(1)	N/A	Static min/max/GCD
Naive Array	O(n)	O(n)	O(1)	Few queries

Summary: The Power of O(log n)

We've completed a comprehensive analysis of segment tree complexity. Here are the essential insights:

Key Takeaways

•O(n) Build — Construction visits each of the ~2n nodes exactly once, with O(1) work per node.
•O(log n) Query — Range queries visit at most O(log n) nodes because at most 2 nodes per level can have partial overlap.
•O(log n) Update — Point updates traverse a single root-to-leaf path, which has length O(log n).
•O(n) Space — We allocate 4n slots but only use ~2n, giving a 2× overhead.
•Balanced Tradeoff — Segment trees offer O(log n) for both queries and updates—better than prefix sums (O(1)/O(n)) for mixed workloads.
•Versatility — The same O(log n) complexity applies regardless of the operation (sum, min, max, GCD, etc.).

Module Complete:

Congratulations! You've now mastered the fundamentals of segment trees:

Construction — Building the tree from an array in O(n) time
Representation — Storing the tree efficiently in a flat array
Queries — Answering range queries in O(log n) time
Updates — Modifying elements in O(log n) time
Complexity — Understanding and proving the time/space bounds

These foundations prepare you for advanced topics like lazy propagation (efficient range updates), persistent segment trees, and 2D segment trees.

Module Complete

You now have a complete, rigorous understanding of segment tree complexity. The O(log n) bounds for queries and updates, combined with O(n) construction, make segment trees one of the most versatile data structures for range query problems. You're ready to apply these techniques to real problems and explore advanced variations.

Time Complexity: O(log n) per Operation

The Mathematics of Efficiency

What You Will Learn

Build Complexity: O(n)

Claim: Building a segment tree from an array of n elements takes O(n) time.

Proof (by counting nodes):

The build algorithm visits each node exactly once and does O(1) work per node.

How many nodes are there?

Leaf nodes: Exactly n (one for each array element)
Internal nodes: At most n - 1 (a binary tree with n leaves has exactly n - 1 internal nodes)

Total nodes: n + (n - 1) = 2n - 1 = O(n)

Work per node:

Read array element (leaves): O(1)
Combine two children (internals): O(1)

Total: O(1) × O(n) = O(n)

Alternative Proof (by recurrence):

Let T(n) be the time to build a segment tree for n elements.

T(1) = O(1)                          // Single element: just store it
T(n) = T(n/2) + T(n/2) + O(1)        // Build two halves, then combine
     = 2T(n/2) + O(1)

By the Master Theorem (Case 1: a = 2, b = 2, f(n) = O(1)):

T(n) = O(n^(log₂2)) = O(n)

Note on the 4n allocation:

We allocate 4n space, but only ~2n nodes are actually used. The allocation itself takes O(n) time (initializing the array), which doesn't change the overall O(n) build complexity.

Preprocessing Amortization

Query Complexity: O(log n)

Claim: Querying a range [L, R] takes O(log n) time.

Proof (by bounding nodes visited):

We need to show that a query visits at most O(log n) nodes.

Key Observation: At each level of the tree, the query visits at most 4 nodes.

Why? At any level, nodes can be classified as:

Completely outside [L, R] → Return immediately, don't count
Completely inside [L, R] → Return immediately, count as 1
Partially overlapping [L, R] → Must recurse into children

Detailed Bound:

At any level, there are at most 2 nodes with partial overlap.

Proof by contradiction:

Suppose three consecutive nodes A, B, C at some level all partially overlap [L, R].

A partially overlaps → L is inside A's range but not fully contained
B partially overlaps → But B is between A and C, so if A and C partially overlap, B must be fully contained in [L, R]
This contradicts B being partially overlapping

Therefore, at most 2 partial overlaps per level.

Counting visited nodes:

Partial overlaps at level i: at most 2
Complete overlaps at level i: at most 2 (they're counted but don't generate children visits)
No overlaps: don't contribute

Actually, a tighter analysis shows at most 4 nodes per level are visited: up to 2 that are fully contained (we stop), and up to 2 that are partial (we continue).

With O(log n) levels, total nodes visited: O(log n).

query_complexity_analysis.py
Python
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
"""
Empirical verification of O(log n) query complexity.
"""
 
import math
import random
 
 
class SegmentTreeWithStats:
    """Segment tree that counts nodes visited per query."""
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n) if self.n > 0 else []
        self.nodes_visited = 0
        
        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) -> tuple:
        """Returns (result, nodes_visited)."""
        self.nodes_visited = 0
        result = self._query(1, 0, self.n - 1, L, R)
        return result, self.nodes_visited
    
    def _query(self, node, start, end, L, R):
        self.nodes_visited += 1
        
        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 analyze_query_complexity():
    """Analyze and verify O(log n) query complexity."""
    
    print("=" * 70)
    print("QUERY COMPLEXITY ANALYSIS")
    print("=" * 70)
    
    print("\n" + "-" * 70)
    print(f"{'n':>10} {'log₂(n)':>10} {'4·log₂(n)':>12} {'Max Visited':>12} {'Ratio':>10}")
    print("-" * 70)
    
    results = []
    
    for n in [10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000]:
        arr = [random.randint(1, 100) for _ in range(n)]
        st = SegmentTreeWithStats(arr)
        
        max_visited = 0
        
        # Test 1000 random queries
        for _ in range(min(1000, n)):
            L = random.randint(0, n - 1)
            R = random.randint(L, n - 1)
            _, visited = st.query(L, R)
            max_visited = max(max_visited, visited)
        
        log_n = math.log2(n)
        theoretical_max = 4 * log_n + 4  # 4 per level + some constant
        ratio = max_visited / log_n
        
        results.append((n, log_n, max_visited, ratio))
        
        print(f"{n:>10} {log_n:>10.2f} {4*log_n:>12.2f} {max_visited:>12} {ratio:>10.2f}")
    
    print("-" * 70)
    print("\nObservations:")
    print("  • Max nodes visited grows proportionally to log₂(n)")
    print("  • Ratio (max_visited / log₂(n)) stays bounded")
    print("  • This confirms O(log n) complexity empirically")
    
    # Calculate average ratio
    avg_ratio = sum(r[3] for r in results) / len(results)
    print(f"  • Average ratio across all sizes: {avg_ratio:.2f}")
 
 
if __name__ == "__main__":
    analyze_query_complexity()

Update Complexity: O(log n)

Claim: Updating a single element takes O(log n) time.

Proof (by path length):

An update starts at the root and descends to a specific leaf:

At each node, we make exactly ONE recursive call (left OR right, never both)
We descend until reaching a leaf (when start == end)
The path length from root to any leaf is the tree height

Tree Height:

For n elements, the tree has height h where:

2^h ≥ n   (enough leaves to cover all elements)
h ≥ log₂(n)
h = ⌈log₂(n)⌉

Nodes on the path:

Going down: h + 1 nodes (root to leaf)
Coming back up: h nodes (propagating changes)
But we visit each node only once (during the return)

Total nodes: h + 1 = O(log n)

Work per node:

Comparison and recursion: O(1)
Combine operation: O(1)

Total: O(1) × O(log n) = O(log n)

Update Path Length Examples
n	Tree Height	Path Length	Theory (⌈log₂n⌉)
1	0	1	0
2	1	2	1
4	2	3	2
8	3	4	3
16	4	5	4
100	7	8	7
1,000	10	11	10
1,000,000	20	21	20

Query vs Update Complexity

Space Complexity: O(n)

Claim: A segment tree uses O(n) space.

Analysis:

Actual nodes:

Leaves: n
Internal nodes: n - 1
Total: 2n - 1

Allocated space:

We allocate 4n to handle non-power-of-2 array sizes
Many slots remain unused (initialized to identity)

Auxiliary space (recursion):

Stack depth: O(log n)
Each frame: O(1)
Total auxiliary: O(log n)

Summary:

Tree storage: O(n)
Auxiliary (during operations): O(log n)
Total: O(n)

space_analysis.py
Python
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
"""
Space complexity analysis of segment trees.
"""
 
import sys
 
 
class SpaceAwareSegmentTree:
    """Segment tree with space tracking."""
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n) if self.n > 0 else []
        self._used_nodes = 0
        
        if self.n > 0:
            self._build(arr, 1, 0, self.n - 1)
    
    def _build(self, arr, node, start, end):
        self._used_nodes += 1
        
        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 space_stats(self) -> dict:
        """Calculate space usage statistics."""
        allocated = len(self.tree)
        used = self._used_nodes
        wasted = allocated - used
        efficiency = (used / allocated * 100) if allocated > 0 else 0
        
        # Memory in bytes (assuming 8 bytes per integer)
        bytes_per_int = 8
        total_bytes = allocated * bytes_per_int
        
        return {
            "n": self.n,
            "allocated_slots": allocated,
            "used_slots": used,
            "wasted_slots": wasted,
            "efficiency": f"{efficiency:.1f}%",
            "theoretical_min": 2 * self.n - 1 if self.n > 0 else 0,
            "bytes": total_bytes,
            "bytes_per_element": total_bytes / self.n if self.n > 0 else 0
        }
 
 
def analyze_space():
    """Analyze space usage for various array sizes."""
    
    print("=" * 70)
    print("SPACE COMPLEXITY ANALYSIS")
    print("=" * 70)
    
    print("\n" + "-" * 70)
    print(f"{'n':>10} {'Allocated':>12} {'Used':>10} {'Efficiency':>12} {'Bytes/elem':>12}")
    print("-" * 70)
    
    test_sizes = [
        1, 2, 3, 4, 5, 7, 8, 10, 15, 16, 17,
        100, 128, 500, 512, 1000, 1024, 10000
    ]
    
    for n in test_sizes:
        arr = list(range(n))
        st = SpaceAwareSegmentTree(arr)
        stats = st.space_stats()
        
        is_power_of_2 = (n & (n - 1)) == 0 and n > 0
        marker = "⚡" if is_power_of_2 else ""
        
        print(f"{n:>10} {stats['allocated_slots']:>12} {stats['used_slots']:>10} "
              f"{stats['efficiency']:>12} {stats['bytes_per_element']:>10.1f}B {marker}")
    
    print("-" * 70)
    print("⚡ = Power of 2 (most efficient)")
    
    print("""
    
Key Observations:
    
1. Space Efficiency:
   - Best case (power of 2):  ~50% efficiency (used = 2n, allocated = 4n)
   - Worst case (2^k + 1):    ~25% efficiency
   - Average:                 ~37% efficiency
 
2. Memory per Element:
   - Ranges from 16 to 32 bytes per element
   - Compared to raw array: 8 bytes per element
   - Overhead factor: 2x to 4x
 
3. The 4n Rule:
   - Always allocating 4n is simple and sufficient
   - More precise: allocate 2 × 2^⌈log₂(n)⌉
   - Trade-off: simplicity vs memory efficiency
""")
 
 
if __name__ == "__main__":
    analyze_space()

Comparing Data Structures

Segment trees excel at specific problems. Let's compare them with alternatives:

Data Structure Comparison for Range Queries
Structure	Build	Point Update	Range Query	When to Use
Raw Array	O(n)	O(1)	O(n)	Few queries, or no updates needed with O(n) ok
Prefix Sums	O(n)	O(n)	O(1)	Many queries, no updates, sum only
Segment Tree	O(n)	O(log n)	O(log n)	Mix of queries and updates, any associative op
Fenwick Tree	O(n)	O(log n)	O(log n)	Simpler to implement, prefix queries, sum only
Sparse Table	O(n log n)	N/A	O(1)	No updates, idempotent ops (min/max/GCD)
Sqrt Decomposition	O(n)	O(1)	O(√n)	Simple to understand, moderate performance

Detailed Comparison:

Segment Tree vs. Prefix Sums:

Prefix sums give O(1) range sum queries but O(n) updates
Segment Tree: O(log n) for both
Crossover: If you have more than O(log n) queries per update, prefix sums win for sum queries

Segment Tree vs. Fenwick Tree (BIT):

Both have O(log n) query and update
Fenwick trees are simpler and have smaller constants
Segment trees are more general (support min/max/GCD, lazy propagation)
For simple prefix/range sums: prefer Fenwick
For anything else: prefer Segment Trees

Segment Tree vs. Sparse Table:

Sparse tables give O(1) queries after O(n log n) preprocessing
But they don't support updates
For static min/max/GCD queries: prefer Sparse Tables
For dynamic data: Segment Trees are the only option

Constant Factors and Real Performance

Big-O notation hides constant factors. Let's examine what's really happening inside those O(log n) operations:

Query Cost Breakdown (per level):

Parameter passing (4 integers: node, start, end, L, R)
Overlap check: 2 comparisons
Mid calculation: 1 integer operation
Two recursive calls (in case of partial overlap)
Combine operation: 1 addition/min/max

With ~log₂(n) levels and potentially 2 branches per level in the worst case, but typically much less.

Estimated Constants:

Query: ~20-30 simple operations per level
Update: ~15-20 simple operations per level (single path)
Per operation: ~20 × log₂(n) to ~30 × log₂(n) CPU operations

performance_benchmark.py
Python
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
"""
Performance benchmarking of segment tree operations.
Compares segment tree with alternative approaches.
"""
 
import time
import random
from typing import List
 
 
class SegmentTree:
    """Optimized segment tree for benchmarking."""
    
    __slots__ = ['n', 'tree']
    
    def __init__(self, arr: List[int]):
        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) >> 1
        left, right = node << 1, (node << 1) | 1
        self._build(arr, left, start, mid)
        self._build(arr, right, mid + 1, end)
        self.tree[node] = self.tree[left] + self.tree[right]
    
    def query(self, L: int, R: int) -> int:
        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) >> 1
        return (self._query(node << 1, start, mid, L, R) +
                self._query((node << 1) | 1, mid + 1, end, L, R))
    
    def update(self, idx: int, val: int):
        self._update(1, 0, self.n - 1, idx, val)
    
    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
            return
        mid = (start + end) >> 1
        if idx <= mid:
            self._update(node << 1, start, mid, idx, val)
        else:
            self._update((node << 1) | 1, mid + 1, end, idx, val)
        self.tree[node] = self.tree[node << 1] + self.tree[(node << 1) | 1]
 
 
class PrefixSums:
    """Prefix sum array for comparison."""
    
    def __init__(self, arr: List[int]):
        self.n = len(arr)
        self.arr = arr[:]
        self.prefix = [0] * (self.n + 1)
        self._rebuild()
    
    def _rebuild(self):
        for i in range(self.n):
            self.prefix[i + 1] = self.prefix[i] + self.arr[i]
    
    def query(self, L: int, R: int) -> int:
        return self.prefix[R + 1] - self.prefix[L]
    
    def update(self, idx: int, val: int):
        self.arr[idx] = val
        self._rebuild()  # O(n) rebuild
 
 
class NaiveArray:
    """Naive approach for comparison."""
    
    def __init__(self, arr: List[int]):
        self.arr = arr[:]
    
    def query(self, L: int, R: int) -> int:
        return sum(self.arr[L:R+1])
    
    def update(self, idx: int, val: int):
        self.arr[idx] = val
 
 
def benchmark():
    """Run comparative benchmarks."""
    
    print("=" * 70)
    print("PERFORMANCE BENCHMARKS")
    print("=" * 70)
    
    n = 100000
    num_queries = 10000
    num_updates = 1000
    
    arr = [random.randint(1, 1000) for _ in range(n)]
    queries = [(random.randint(0, n-1), random.randint(0, n-1)) for _ in range(num_queries)]
    queries = [(min(a, b), max(a, b)) for a, b in queries]
    updates = [(random.randint(0, n-1), random.randint(1, 1000)) for _ in range(num_updates)]
    
    print(f"\nArray size: {n:,}")
    print(f"Queries: {num_queries:,}")
    print(f"Updates: {num_updates:,}")
    
    print("\n" + "-" * 70)
    print("BUILD TIME")
    print("-" * 70)
    
    # Segment Tree
    start = time.perf_counter()
    st = SegmentTree(arr)
    st_build = time.perf_counter() - start
    print(f"Segment Tree:  {st_build*1000:.2f} ms")
    
    # Prefix Sums
    start = time.perf_counter()
    ps = PrefixSums(arr)
    ps_build = time.perf_counter() - start
    print(f"Prefix Sums:   {ps_build*1000:.2f} ms")
    
    # Naive
    start = time.perf_counter()
    na = NaiveArray(arr)
    na_build = time.perf_counter() - start
    print(f"Naive Array:   {na_build*1000:.2f} ms")
    
    print("\n" + "-" * 70)
    print("QUERY TIME (10,000 queries)")
    print("-" * 70)
    
    # Segment Tree queries
    start = time.perf_counter()
    for L, R in queries:
        st.query(L, R)
    st_query = time.perf_counter() - start
    print(f"Segment Tree:  {st_query*1000:.2f} ms ({st_query/num_queries*1e6:.2f} µs/query)")
    
    # Prefix Sums queries
    start = time.perf_counter()
    for L, R in queries:
        ps.query(L, R)
    ps_query = time.perf_counter() - start
    print(f"Prefix Sums:   {ps_query*1000:.2f} ms ({ps_query/num_queries*1e6:.2f} µs/query)")
    
    # Naive queries (sample only)
    sample_queries = queries[:100]
    start = time.perf_counter()
    for L, R in sample_queries:
        na.query(L, R)
    na_query = (time.perf_counter() - start) * (num_queries / 100)
    print(f"Naive Array:   ~{na_query*1000:.2f} ms ({na_query/num_queries*1e6:.2f} µs/query) [estimated]")
    
    print("\n" + "-" * 70)
    print("UPDATE TIME (1,000 updates)")
    print("-" * 70)
    
    # Segment Tree updates
    start = time.perf_counter()
    for idx, val in updates:
        st.update(idx, val)
    st_update = time.perf_counter() - start
    print(f"Segment Tree:  {st_update*1000:.2f} ms ({st_update/num_updates*1e6:.2f} µs/update)")
    
    # Prefix Sums updates (sample only - very slow)
    sample_updates = updates[:10]
    start = time.perf_counter()
    for idx, val in sample_updates:
        ps.update(idx, val)
    ps_update = (time.perf_counter() - start) * (num_updates / 10)
    print(f"Prefix Sums:   ~{ps_update*1000:.2f} ms ({ps_update/num_updates*1e6:.2f} µs/update) [estimated]")
    
    # Naive updates
    start = time.perf_counter()
    for idx, val in updates:
        na.update(idx, val)
    na_update = time.perf_counter() - start
    print(f"Naive Array:   {na_update*1000:.2f} ms ({na_update/num_updates*1e6:.2f} µs/update)")
    
    print("\n" + "-" * 70)
    print("SUMMARY")
    print("-" * 70)
    print("""
    For mixed workloads (queries + updates):
    • Segment Tree is the clear winner
    • O(log n) for both operations
    
    For query-only workloads:
    • Prefix Sums win with O(1) queries
    • But they break down if updates are needed
    
    For update-only workloads:
    • Naive array wins with O(1) updates
    • But they can't do fast range queries
    
    Segment Tree: The BALANCED solution
    """)
 
 
if __name__ == "__main__":
    benchmark()

When to Use Segment Trees

Based on our complexity analysis, here's a decision framework:

Use Segment Trees When:

•Binary queries + updates — You need range queries AND point updates, both frequent.
•Non-sum operations — You need min, max, GCD, or other associative operations that prefix sums can't handle.
•Range updates — With lazy propagation (covered in next module), segment trees support range updates efficiently.
•Persistent versions — Segment trees can be made persistent (immutable with history) more easily than alternatives.
•2D or higher dimensions — 2D segment trees solve 2D range query problems.

Don't Use Segment Trees When:

•Only queries, no updates — Use prefix sums (O(1) sum queries) or sparse tables (O(1) min/max/GCD queries).
•Only prefix sums needed — Fenwick trees are simpler and have smaller constants.
•Very small n — For n < 100, a naive O(n) approach might be faster due to lower overhead.
•Memory constrained — Segment trees use ~4n memory; consider alternatives if space is tight.
•Simpler problem — If the problem doesn't actually need range queries, don't overcomplicate.

Rule of Thumb

Comprehensive Complexity Summary

Let's consolidate all the complexity results in one place:

Segment Tree Complexity Summary
Operation	Time	Space	Notes
Build	O(n)	O(n)	Visit all ~2n nodes once
Point Query	O(log n)	O(log n) stack	Follow single path to leaf
Range Query	O(log n)	O(log n) stack	At most 4 nodes per level
Point Update	O(log n)	O(log n) stack	Update path from leaf to root
Range Update*	O(log n)	O(log n) stack	*With lazy propagation
Space	O(n)		4n allocation is common

Comparison: Segment Tree vs Alternatives
Data Structure	Build	Query	Update	Best For
Segment Tree	O(n)	O(log n)	O(log n)	Mixed workloads, any op
Fenwick Tree	O(n)	O(log n)	O(log n)	Prefix sums, simpler
Prefix Sums	O(n)	O(1)	O(n)	Static sum queries
Sparse Table	O(n log n)	O(1)	N/A	Static min/max/GCD
Naive Array	O(n)	O(n)	O(1)	Few queries

Summary: The Power of O(log n)

We've completed a comprehensive analysis of segment tree complexity. Here are the essential insights:

Key Takeaways

•O(n) Build — Construction visits each of the ~2n nodes exactly once, with O(1) work per node.
•O(log n) Query — Range queries visit at most O(log n) nodes because at most 2 nodes per level can have partial overlap.
•O(log n) Update — Point updates traverse a single root-to-leaf path, which has length O(log n).
•O(n) Space — We allocate 4n slots but only use ~2n, giving a 2× overhead.
•Balanced Tradeoff — Segment trees offer O(log n) for both queries and updates—better than prefix sums (O(1)/O(n)) for mixed workloads.
•Versatility — The same O(log n) complexity applies regardless of the operation (sum, min, max, GCD, etc.).

Module Complete:

Congratulations! You've now mastered the fundamentals of segment trees:

Construction — Building the tree from an array in O(n) time
Representation — Storing the tree efficiently in a flat array
Queries — Answering range queries in O(log n) time
Updates — Modifying elements in O(log n) time
Complexity — Understanding and proving the time/space bounds

These foundations prepare you for advanced topics like lazy propagation (efficient range updates), persistent segment trees, and 2D segment trees.

Module Complete