Building a Segment Tree from Array - Segment Tree Construction & Operations | OneNoughtOne

0/361

Data Structures & AlgorithmsSegment Tree Construction & Operations

Segment Tree Construction & Operations

LevelAdvanced

Duration75 mins

TopicSegment Tree Construction & Operations

1 / 5

Building a Segment Tree from Array

From Array to Tree: The Construction Journey

In the previous module, we discovered why segment trees exist—their ability to answer range queries and handle point updates in O(log n) time, something neither simple arrays nor prefix sums can achieve when both query and update operations are required. Now comes the moment of truth: how do we actually build one?

The construction of a segment tree is where theory meets implementation. It's the process of transforming a flat, linear array into a hierarchical tree structure where each node captures aggregate information about a range of the original array. This transformation is not merely mechanical—it embodies a profound divide-and-conquer strategy that forms the backbone of segment tree efficiency.

What You Will Learn

By the end of this page, you will understand the complete construction algorithm for segment trees, including the recursive decomposition strategy, how to compute internal node values, the relationship between tree structure and array indices, and the initialization process that turns O(n) preprocessing into O(log n) queries.

The Fundamental Insight Behind Construction

Before diving into code, let's crystallize the core insight that makes segment tree construction possible:

Every range can be recursively decomposed into two halves.

This might seem trivial, but its implications are profound. Consider a range [0, 7] covering 8 elements:

[0, 7] = [0, 3] ∪ [4, 7]
[0, 3] = [0, 1] ∪ [2, 3]
[4, 7] = [4, 5] ∪ [6, 7]
[0, 1] = [0, 0] ∪ [1, 1]
... and so on

This binary decomposition creates a complete binary tree structure where:

Leaf nodes represent individual elements (ranges of size 1)
Internal nodes represent the combination of their children's ranges
The root represents the entire array

The Tree Height

Since we're dividing by 2 at each level, a segment tree for n elements has height ⌈log₂(n)⌉. This logarithmic height is the source of O(log n) query time—we never need to traverse more than this many levels.

What does each node store?

Each node in the segment tree stores the aggregate value for its range, determined by the specific operation:

Query Type	Node Value	Combination Function
Range Sum	Sum of elements in range	`node = left + right`
Range Min	Minimum element in range	`node = min(left, right)`
Range Max	Maximum element in range	`node = max(left, right)`
Range GCD	GCD of elements in range	`node = gcd(left, right)`
Range XOR	XOR of elements in range	`node = left ^ right`

The construction process is operation-agnostic in its structure—only the combination function changes. This makes segment trees remarkably versatile.

Visual Construction Walkthrough

Let's trace through the construction of a segment tree for Range Sum queries. Consider the input array:

array = [1, 3, 5, 7, 9, 11]
indices:  0  1  2  3  4  5

We'll build a tree where each node stores the sum of its range.

Segment Tree Construction Steps
Step	Range	Computation	Node Value
Leaf	[0,0]	array[0]	1
Leaf	[1,1]	array[1]	3
Leaf	[2,2]	array[2]	5
Leaf	[3,3]	array[3]	7
Leaf	[4,4]	array[4]	9
Leaf	[5,5]	array[5]	11
Internal	[0,1]	1 + 3	4
Internal	[2,2]	5 (single element)	5
Internal	[3,4]	7 + 9	16
Internal	[5,5]	11 (single element)	11
Internal	[0,2]	4 + 5	9
Internal	[3,5]	16 + 11	27
Root	[0,5]	9 + 27	36

The resulting tree structure (shown with ranges and values):

                    [0,5]=36
                   /        
             [0,2]=9        [3,5]=27
            /      \        /       
       [0,1]=4   [2,2]=5  [3,4]=16  [5,5]=11
       /    \              /    
   [0,0]=1 [1,1]=3    [3,3]=7  [4,4]=9

Notice the patterns:

Leaf nodes correspond to individual array elements
Each internal node's value equals the sum of its children
The root (36) equals the sum of the entire array (1+3+5+7+9+11)
The tree isn't perfectly balanced because 6 isn't a power of 2, but that's perfectly fine

Non-Power-of-Two Sizes

When the array size isn't a power of 2, the tree becomes slightly unbalanced. Some leaf nodes appear at the second-to-last level while others are at the last level. The algorithms handle this naturally through their recursive structure—no special cases needed.

The Recursive Build Algorithm

The construction algorithm follows directly from the divide-and-conquer insight. We define a recursive function build(node, start, end) that:

Base case: If start == end (single element), the node is a leaf—store array[start]
Recursive case: Otherwise, find the midpoint, build left and right children, then combine

The algorithm naturally mirrors the tree structure it creates.

segment_tree_build.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
class SegmentTree:
    """
    A segment tree for range sum queries.
    This implementation uses a recursive build approach.
    """
    
    def __init__(self, arr):
        """
        Initialize and build the segment tree from the input array.
        
        Args:
            arr: The input array (list of numbers)
        
        Time Complexity: O(n) where n = len(arr)
        Space Complexity: O(n) for the tree storage
        """
        self.n = len(arr)
        self.arr = arr
        
        # Allocate space for the segment tree
        # A segment tree for n elements needs at most 4n space
        # (This is explained in detail in the next page)
        self.tree = [0] * (4 * self.n)
        
        # Build the tree starting from root (node index 1)
        # covering the full range [0, n-1]
        if self.n > 0:
            self._build(1, 0, self.n - 1)
    
    def _build(self, node, start, end):
        """
        Recursively build the segment tree.
        
        Args:
            node: Current node index in the tree array
            start: Left boundary of the range (inclusive)
            end: Right boundary of the range (inclusive)
        
        This function fills tree[node] with the aggregate value
        for the range [start, end].
        """
        # Base case: leaf node (single element)
        if start == end:
            # A leaf node stores the array element itself
            self.tree[node] = self.arr[start]
            return
        
        # Recursive case: internal node
        # Find the midpoint to divide the range
        mid = (start + end) // 2
        
        # Left child covers [start, mid]
        # Right child covers [mid+1, end]
        left_child = 2 * node
        right_child = 2 * node + 1
        
        # Recursively build left and right subtrees
        self._build(left_child, start, mid)
        self._build(right_child, mid + 1, end)
        
        # Internal node value = combination of children
        # For range sum queries, this is addition
        self.tree[node] = self.tree[left_child] + self.tree[right_child]
 
 
# Example usage demonstrating construction
def demonstrate_construction():
    """
    Walk through the construction process step by step.
    """
    arr = [1, 3, 5, 7, 9, 11]
    print(f"Input array: {arr}")
    print(f"Array length: {len(arr)}")
    
    # Build the segment tree
    st = SegmentTree(arr)
    
    # Display the tree contents
    print("
Segment tree array (non-zero values):")
    for i, val in enumerate(st.tree):
        if val != 0:
            print(f"  tree[{i}] = {val}")
    
    # The root (tree[1]) should contain the sum of all elements
    print(f"
Root value (tree[1]): {st.tree[1]}")
    print(f"Sum of array: {sum(arr)}")
    print(f"Match: {st.tree[1] == sum(arr)}")
 
 
if __name__ == "__main__":
    demonstrate_construction()

Understanding the recursion flow:

Let's trace _build(1, 0, 5) for our example array [1, 3, 5, 7, 9, 11]:

_build(1, 0, 5)  → mid=2
  ├── _build(2, 0, 2)  → mid=1
  │     ├── _build(4, 0, 1)  → mid=0
  │     │     ├── _build(8, 0, 0)  → leaf, tree[8]=1
  │     │     └── _build(9, 1, 1)  → leaf, tree[9]=3
  │     │     → tree[4] = 1 + 3 = 4
  │     └── _build(5, 2, 2)  → leaf, tree[5]=5
  │     → tree[2] = 4 + 5 = 9
  └── _build(3, 3, 5)  → mid=4
        ├── _build(6, 3, 4)  → mid=3
        │     ├── _build(12, 3, 3)  → leaf, tree[12]=7
        │     └── _build(13, 4, 4)  → leaf, tree[13]=9
        │     → tree[6] = 7 + 9 = 16
        └── _build(7, 5, 5)  → leaf, tree[7]=11
        → tree[3] = 16 + 11 = 27
  → tree[1] = 9 + 27 = 36

Each node is visited exactly once, and the work at each node (excluding recursive calls) is O(1). With n leaves and approximately n-1 internal nodes, the total time is O(n).

The Combination Function: Heart of the Tree

The line self.tree[node] = self.tree[left] + self.tree[right] is the soul of the segment tree. This combination function determines what queries the tree can answer.

A segment tree can support any operation that is associative—meaning (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c). This property is crucial because it allows us to combine arbitrary contiguous ranges in any order and get the same result.

Operations Suitable for Segment Trees

•Addition (Sum Queries) — combine(a, b) = a + b — The most common use case
•Minimum — combine(a, b) = min(a, b) — Range minimum queries (RMQ)
•Maximum — combine(a, b) = max(a, b) — Range maximum queries
•GCD — combine(a, b) = gcd(a, b) — Greatest common divisor queries
•LCM — combine(a, b) = lcm(a, b) — Least common multiple queries
•Bitwise OR — combine(a, b) = a | b — Useful for flag combinations
•Bitwise AND — combine(a, b) = a & b — Intersection of bit patterns
•Bitwise XOR — combine(a, b) = a ^ b — Parity and toggle queries
•Multiplication — combine(a, b) = a × b — Product queries (watch for overflow)

segment_tree_variants.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
"""
Segment Tree Variants: Different Combination Functions
 
This module demonstrates how to build segment trees for
various query types by simply changing the combination function.
"""
 
class SegmentTreeMin:
    """Segment tree for Range Minimum Queries (RMQ)."""
    
    def __init__(self, arr):
        self.n = len(arr)
        self.arr = arr
        self.tree = [float('inf')] * (4 * self.n)  # Identity for min
        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
        left_child, right_child = 2 * node, 2 * node + 1
        
        self._build(left_child, start, mid)
        self._build(right_child, mid + 1, end)
        
        # Combination function: minimum
        self.tree[node] = min(self.tree[left_child], self.tree[right_child])
 
 
class SegmentTreeMax:
    """Segment tree for Range Maximum Queries."""
    
    def __init__(self, arr):
        self.n = len(arr)
        self.arr = arr
        self.tree = [float('-inf')] * (4 * self.n)  # Identity for max
        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
        left_child, right_child = 2 * node, 2 * node + 1
        
        self._build(left_child, start, mid)
        self._build(right_child, mid + 1, end)
        
        # Combination function: maximum
        self.tree[node] = max(self.tree[left_child], self.tree[right_child])
 
 
class SegmentTreeGCD:
    """Segment tree for Range GCD Queries."""
    
    def __init__(self, arr):
        from math import gcd
        self.gcd = gcd
        self.n = len(arr)
        self.arr = arr
        self.tree = [0] * (4 * self.n)  # Identity for gcd (gcd(x, 0) = x)
        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
        left_child, right_child = 2 * node, 2 * node + 1
        
        self._build(left_child, start, mid)
        self._build(right_child, mid + 1, end)
        
        # Combination function: GCD
        self.tree[node] = self.gcd(self.tree[left_child], self.tree[right_child])
 
 
class SegmentTreeXOR:
    """Segment tree for Range XOR Queries."""
    
    def __init__(self, arr):
        self.n = len(arr)
        self.arr = arr
        self.tree = [0] * (4 * self.n)  # Identity for XOR
        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
        left_child, right_child = 2 * node, 2 * node + 1
        
        self._build(left_child, start, mid)
        self._build(right_child, mid + 1, end)
        
        # Combination function: XOR
        self.tree[node] = self.tree[left_child] ^ self.tree[right_child]
 
 
# Demonstration
def demonstrate_variants():
    arr = [12, 6, 18, 9, 15, 3]
    print(f"Input array: {arr}")
    
    st_min = SegmentTreeMin(arr)
    st_max = SegmentTreeMax(arr)
    st_gcd = SegmentTreeGCD(arr)
    st_xor = SegmentTreeXOR(arr)
    
    print(f"
Range [0, 5] results:")
    print(f"  Min: {st_min.tree[1]} (expected: {min(arr)})")
    print(f"  Max: {st_max.tree[1]} (expected: {max(arr)})")
    from math import gcd
    from functools import reduce
    print(f"  GCD: {st_gcd.tree[1]} (expected: {reduce(gcd, arr)})")
    print(f"  XOR: {st_xor.tree[1]} (expected: {reduce(lambda x, y: x ^ y, arr)})")
 
 
if __name__ == "__main__":
    demonstrate_variants()

Non-Associative Operations Don't Work

Operations like subtraction and division are NOT associative. (a - b) - c ≠ a - (b - c). Segment trees cannot directly support range subtraction or division queries. If you need these, you must reformulate the problem (e.g., subtraction can be done via sum queries of carefully designed ranges).

Indexing Conventions: 0-Based vs 1-Based

You'll encounter two common indexing conventions for segment trees:

1-Based Indexing (Root at index 1)

Left child of node i is at 2*i
Right child of node i is at 2*i + 1
Parent of node i is at i // 2
Tree[0] is unused

0-Based Indexing (Root at index 0)

Left child of node i is at 2*i + 1
Right child of node i is at 2*i + 2
Parent of node i is at (i - 1) // 2
All indices are used

1-Based (Recommended)

•Cleaner formulas (just 2i, 2i+1)
•Widely used in competitive programming
•Bit manipulation: left = i << 1, right = (i << 1) | 1
•One unused array slot (tree[0])
•More intuitive parent/child relationships

0-Based (Alternative)

•No wasted space
•Consistent with most language conventions
•Slightly more complex formulas
•Used in some textbooks
•Requires +1/-1 adjustments

indexing_comparison.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
"""
Comparison of 1-based and 0-based indexing in segment trees.
Both implementations produce functionally identical trees.
"""
 
class SegmentTree1Based:
    """Segment tree using 1-based indexing (root at index 1)."""
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        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
        # 1-based: left = 2*node, right = 2*node + 1
        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]
 
 
class SegmentTree0Based:
    """Segment tree using 0-based indexing (root at index 0)."""
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        if self.n > 0:
            self._build(arr, 0, 0, self.n - 1)
    
    def _build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
            return
        
        mid = (start + end) // 2
        # 0-based: left = 2*node + 1, right = 2*node + 2
        self._build(arr, 2 * node + 1, start, mid)
        self._build(arr, 2 * node + 2, mid + 1, end)
        self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]
 
 
# Verify both produce the same results
arr = [1, 3, 5, 7, 9, 11]
st1 = SegmentTree1Based(arr)
st0 = SegmentTree0Based(arr)
 
print("1-Based (root at tree[1]):", st1.tree[1])
print("0-Based (root at tree[0]):", st0.tree[0])
print("Both equal sum:", sum(arr))

Our Convention

Throughout this module, we use 1-based indexing for the tree array. This matches most competitive programming resources and produces cleaner code. The root is at tree[1], its children at tree[2] and tree[3], and so on.

Handling Edge Cases in Construction

Robust segment tree construction must handle several edge cases gracefully:

1. Empty Array An empty array produces an empty tree. We should check for n == 0 before building.

2. Single Element With n == 1, the tree has only one node (the root), which is also a leaf. The range is [0, 0].

3. Array Size Not a Power of 2 This is the common case. The tree is slightly unbalanced, but the algorithms handle it naturally.

4. Large Values and Overflow For sum queries, internal nodes can hold values much larger than individual elements. Consider using long long (C++) or being aware of Python's arbitrary precision integers.

robust_segment_tree.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
"""
A robust segment tree implementation handling all edge cases.
"""
 
class RobustSegmentTree:
    """
    Production-quality segment tree with comprehensive edge case handling.
    """
    
    def __init__(self, arr, combine=lambda a, b: a + b, identity=0):
        """
        Initialize segment tree with custom operation.
        
        Args:
            arr: Input array (can be empty)
            combine: Binary function to combine two values
            identity: Identity element for the operation
                     (0 for sum, inf for min, -inf for max)
        """
        self.combine = combine
        self.identity = identity
        
        # Handle empty array
        if not arr:
            self.n = 0
            self.tree = []
            return
        
        self.n = len(arr)
        self.arr = arr[:]  # Create a copy
        
        # Allocate tree with safety margin
        self.tree = [identity] * (4 * self.n)
        
        # Build the tree
        self._build(1, 0, self.n - 1)
    
    def _build(self, node, start, end):
        """Build segment tree recursively."""
        # Base case: single element (leaf)
        if start == end:
            self.tree[node] = self.arr[start]
            return
        
        mid = (start + end) // 2
        left_child = 2 * node
        right_child = 2 * node + 1
        
        # Build children
        self._build(left_child, start, mid)
        self._build(right_child, mid + 1, end)
        
        # Combine children values
        self.tree[node] = self.combine(
            self.tree[left_child],
            self.tree[right_child]
        )
    
    def is_empty(self):
        """Check if the tree is empty."""
        return self.n == 0
    
    def size(self):
        """Return the number of elements in the original array."""
        return self.n
    
    def root_value(self):
        """Return the aggregate of the entire array."""
        if self.is_empty():
            return self.identity
        return self.tree[1]
 
 
# Edge case demonstrations
def test_edge_cases():
    print("=== Edge Case Testing ===
")
    
    # Empty array
    empty_tree = RobustSegmentTree([])
    print(f"Empty array:")
    print(f"  Size: {empty_tree.size()}")
    print(f"  Is empty: {empty_tree.is_empty()}")
    print(f"  Root value: {empty_tree.root_value()}")
    
    # Single element
    single = RobustSegmentTree([42])
    print(f"
Single element [42]:")
    print(f"  Size: {single.size()}")
    print(f"  Root value: {single.root_value()}")
    
    # Non-power-of-2 size
    odd_size = RobustSegmentTree([1, 2, 3, 4, 5])
    print(f"
Odd size array [1,2,3,4,5]:")
    print(f"  Size: {odd_size.size()}")
    print(f"  Root value: {odd_size.root_value()} (sum = 15)")
    
    # Large values (Python handles this automatically)
    large_values = RobustSegmentTree([10**18, 10**18, 10**18])
    print(f"
Large values [10^18, 10^18, 10^18]:")
    print(f"  Root value: {large_values.root_value()}")
    print(f"  Expected: {3 * 10**18}")
    
    # Custom operation: minimum
    min_tree = RobustSegmentTree(
        [5, 2, 8, 1, 9],
        combine=min,
        identity=float('inf')
    )
    print(f"
Min tree [5,2,8,1,9]:")
    print(f"  Root value (min): {min_tree.root_value()}")
 
 
if __name__ == "__main__":
    test_edge_cases()

Time and Space Complexity Analysis

Understanding the construction complexity is essential for making informed decisions about when to use segment trees.

Time Complexity: O(n)

The build function visits each node exactly once. For a segment tree with n leaves:

Number of leaf nodes: n
Number of internal nodes: at most n - 1
Total nodes: at most 2n - 1 (actually slightly more due to tree structure)

At each node, we perform O(1) work (combine operation), so total time is O(n).

Space Complexity: O(n)

We allocate a tree array of size 4n. Why 4n? The detailed analysis is in the next page, but briefly:

The tree has at most 2n - 1 meaningful nodes
Due to the array representation, we need extra space for gaps
4n is a safe upper bound that works for any n

Construction Complexity Summary
Aspect	Complexity	Notes
Time (Build)	O(n)	Each node visited once
Space (Tree)	O(n)	4n allocation is common
Auxiliary Space	O(log n)	Recursion stack depth
Combine Operation	O(1)	Assumed constant-time

The 4n Space Bound

The factor of 4 might seem wasteful, but it's a practical choice that avoids complex calculations. In the next page, we'll explore the array representation in depth and see exactly why 4n suffices and how to calculate tighter bounds if memory is critical.

Complete Implementation with Testing

Let's consolidate everything into a complete, well-documented implementation:

segment_tree_complete.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
"""
Complete Segment Tree Implementation
====================================
 
A production-ready segment tree supporting:
- Range Sum Queries (default)
- Custom combine operations
- Construction, Query, and Update operations
 
Author: DSA Learning Module
"""
 
from typing import List, Callable, TypeVar
 
T = TypeVar('T')
 
 
class SegmentTree:
    """
    A flexible segment tree implementation.
    
    The segment tree is a binary tree where each node stores
    aggregate information about a range of the original array.
    
    Attributes:
        n: Size of the original array
        tree: Array storing the segment tree nodes
        combine: Binary function to combine two values
        identity: Identity element for the combine operation
    """
    
    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 operation
            identity: Identity element (e.g., 0 for +, inf for min)
        
        Time Complexity: O(n)
        Space Complexity: O(n)
        """
        self.combine = combine
        self.identity = identity
        self.n = len(arr)
        
        if self.n == 0:
            self.tree = []
            return
        
        # Allocate tree storage (4n is a safe upper bound)
        self.tree = [identity] * (4 * self.n)
        
        # Build the tree (root at index 1)
        self._build(arr, 1, 0, self.n - 1)
    
    def _build(self, arr: List[T], node: int, start: int, end: int) -> None:
        """
        Recursively construct the segment tree.
        
        Args:
            arr: Original input array
            node: Current node index in tree
            start: Left boundary of current range
            end: Right boundary of current range
        """
        # Base case: leaf node
        if start == end:
            self.tree[node] = arr[start]
            return
        
        # Recursive case: build children first
        mid = (start + end) // 2
        left_child = 2 * node
        right_child = 2 * node + 1
        
        self._build(arr, left_child, start, mid)
        self._build(arr, right_child, mid + 1, end)
        
        # Current node = combination of children
        self.tree[node] = self.combine(
            self.tree[left_child],
            self.tree[right_child]
        )
    
    def __repr__(self) -> str:
        if self.n == 0:
            return "SegmentTree(empty)"
        return f"SegmentTree(n={self.n}, root={self.tree[1]})"
 
 
# ============================================================
# Test Suite for Segment Tree Construction
# ============================================================
 
def test_construction():
    """Comprehensive tests for segment tree construction."""
    
    print("=" * 60)
    print("SEGMENT TREE CONSTRUCTION TESTS")
    print("=" * 60)
    
    # Test 1: Basic sum tree
    print("
[Test 1] Basic Sum Tree")
    arr = [1, 3, 5, 7, 9, 11]
    st = SegmentTree(arr)
    expected_sum = sum(arr)
    assert st.tree[1] == expected_sum, f"Root should be {expected_sum}"
    print(f"  Array: {arr}")
    print(f"  Root (total sum): {st.tree[1]} ✓")
    
    # Test 2: Power of 2 size
    print("
[Test 2] Power of 2 Size")
    arr_pow2 = [1, 2, 3, 4, 5, 6, 7, 8]
    st_pow2 = SegmentTree(arr_pow2)
    assert st_pow2.tree[1] == 36
    print(f"  Array (n=8): {arr_pow2}")
    print(f"  Root: {st_pow2.tree[1]} ✓")
    
    # Test 3: Non-power of 2 size
    print("
[Test 3] Non-Power of 2 Size")
    arr_npow2 = [1, 2, 3, 4, 5, 6, 7]
    st_npow2 = SegmentTree(arr_npow2)
    assert st_npow2.tree[1] == 28
    print(f"  Array (n=7): {arr_npow2}")
    print(f"  Root: {st_npow2.tree[1]} ✓")
    
    # Test 4: Single element
    print("
[Test 4] Single Element")
    st_single = SegmentTree([42])
    assert st_single.tree[1] == 42
    print(f"  Array: [42]")
    print(f"  Root: {st_single.tree[1]} ✓")
    
    # Test 5: Empty array
    print("
[Test 5] Empty Array")
    st_empty = SegmentTree([])
    assert st_empty.n == 0
    print(f"  Array: []")
    print(f"  Tree is empty: {len(st_empty.tree) == 0} ✓")
    
    # Test 6: Min tree
    print("
[Test 6] Minimum Query Tree")
    arr_min = [5, 2, 8, 1, 9, 3]
    st_min = SegmentTree(arr_min, combine=min, identity=float('inf'))
    assert st_min.tree[1] == 1
    print(f"  Array: {arr_min}")
    print(f"  Root (min): {st_min.tree[1]} ✓")
    
    # Test 7: Max tree
    print("
[Test 7] Maximum Query Tree")
    arr_max = [5, 2, 8, 1, 9, 3]
    st_max = SegmentTree(arr_max, combine=max, identity=float('-inf'))
    assert st_max.tree[1] == 9
    print(f"  Array: {arr_max}")
    print(f"  Root (max): {st_max.tree[1]} ✓")
    
    # Test 8: GCD tree
    print("
[Test 8] GCD Query Tree")
    from math import gcd
    arr_gcd = [12, 18, 24, 6]
    st_gcd = SegmentTree(arr_gcd, combine=gcd, identity=0)
    assert st_gcd.tree[1] == 6
    print(f"  Array: {arr_gcd}")
    print(f"  Root (GCD): {st_gcd.tree[1]} ✓")
    
    # Test 9: Large values
    print("
[Test 9] Large Values")
    arr_large = [10**15, 10**15, 10**15]
    st_large = SegmentTree(arr_large)
    assert st_large.tree[1] == 3 * 10**15
    print(f"  Array: [10^15, 10^15, 10^15]")
    print(f"  Root: {st_large.tree[1]} ✓")
    
    # Test 10: Negative values
    print("
[Test 10] Negative Values")
    arr_neg = [-5, 3, -2, 8, -1]
    st_neg = SegmentTree(arr_neg)
    assert st_neg.tree[1] == 3
    print(f"  Array: {arr_neg}")
    print(f"  Root: {st_neg.tree[1]} ✓")
    
    print("
" + "=" * 60)
    print("ALL CONSTRUCTION TESTS PASSED!")
    print("=" * 60)
 
 
if __name__ == "__main__":
    test_construction()

Summary: Building the Foundation

We've explored the construction of segment trees from first principles. Let's consolidate the key insights:

Key Takeaways

•Divide-and-Conquer Structure — Every range decomposes into two halves, creating a binary tree where leaves are array elements and internal nodes are aggregates.
•Recursive Build Algorithm — Start at the root covering the full range. For each node: if it's a leaf, store the element; otherwise, build children and combine their values.
•Flexible Combination Function — The same structure supports sum, min, max, GCD, XOR, and any associative operation by changing only the combine function.
•1-Based Indexing — Using root at index 1 simplifies child calculations: left = 2i, right = 2i+1.
•O(n) Construction Time — Each of the ~2n nodes is visited exactly once with O(1) work per node.
•O(n) Space — Allocating 4n array slots provides a safe upper bound for any array size.

What's Next:

Now that we can build a segment tree, we need to understand the array representation in detail. The next page explores how the tree maps to a flat array, why we need 4n space, and how to navigate between parent and child nodes efficiently.

Page Complete

You now understand how to build a segment tree from an array. The recursive algorithm transforms an O(n) preprocessing step into the foundation for O(log n) queries and updates. Next, we'll explore the array-based representation that makes this efficiency possible.