Segment Tree Operations - Learning Module

Loading content...

0/276

Array-Based Segment Tree Representation

The Elegant Mapping: Tree in a Flat Array

In the previous page, we learned how to build a segment tree recursively, watching nodes materialize as the algorithm descended and ascended through the tree structure. But look at our implementation again—there's no TreeNode class, no explicit left and right pointers, no reference-based tree structure at all.

The segment tree lives entirely within a flat array.

This is one of the most elegant aspects of segment tree design. By leveraging the properties of complete binary trees, we can map every node to an array index and navigate parent-child relationships through simple arithmetic. This approach offers significant advantages: better cache locality, simpler memory management, and faster operations.

What You Will Learn

By the end of this page, you will understand the precise mathematical relationship between tree nodes and array indices, why we allocate 4n space for the array, how to navigate between parent and child nodes using only arithmetic, and the memory efficiency implications of this representation.

Complete Binary Trees and Array Storage

The ability to store a tree in an array isn't unique to segment trees—it works for any complete binary tree. But what exactly is a complete binary tree?

Definition: A complete binary tree is a binary tree in which:

Every level except possibly the last is completely filled
All nodes in the last level are as far left as possible

However, segment trees aren't always strictly complete—when n isn't a power of 2, the tree has gaps. Despite this, the array representation still works because we use a positional encoding where each node's position in the array is determined solely by its theoretical position in a complete tree of sufficient size.

The Positional Encoding Principle:

In a binary tree stored in an array (1-indexed):

Node at index i has its left child at index 2i
Node at index i has its right child at index 2i + 1
Node at index i has its parent at index i / 2 (integer division)

This means the root (index 1) has children at indices 2 and 3. Node 2 has children at 4 and 5. Node 3 has children at 6 and 7. And so on.

Array indices:    1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
Tree level:       0   1   1   2   2   2   2   3   3   3   3   3   3   3   3

Tree structure:
                        1
                      /   \
                     2     3
                    / \   / \
                   4   5 6   7
                  /\ /\ /\ /\
                 8 9...etc

Bit Manipulation View

Notice that 2i = i << 1 (left shift by 1) and 2i + 1 = (i << 1) | 1 (left shift, then set lowest bit). This means navigating the tree can be done with blazing-fast bit operations. Going to the left child shifts left and appends a 0 bit; going to the right child shifts left and appends a 1 bit.

Mapping Ranges to Array Indices

Each node in a segment tree represents a range [start, end] of the original array. But the node's index in the tree array is independent of what range it represents—it's determined purely by its position in the tree hierarchy.

Let's trace this mapping for an array of size 6:

Original array: [a₀, a₁, a₂, a₃, a₄, a₅]
Indices:          0   1   2   3   4   5

Node Index to Range Mapping (n=6)
Tree Index	Range	Level	Content
1	[0, 5]	0	Sum of all elements (root)
2	[0, 2]	1	Sum of a₀, a₁, a₂
3	[3, 5]	1	Sum of a₃, a₄, a₅
4	[0, 1]	2	Sum of a₀, a₁
5	[2, 2]	2	Just a₂
6	[3, 4]	2	Sum of a₃, a₄
7	[5, 5]	2	Just a₅
8	[0, 0]	3	Just a₀
9	[1, 1]	3	Just a₁
12	[3, 3]	3	Just a₃
13	[4, 4]	3	Just a₄

Notice the gaps:

Index 10 and 11 are not used (would be children of node 5, but node 5 is a leaf)
Index 14 and 15 are not used (would be children of node 7, but node 7 is a leaf)

These gaps occur because not all internal nodes have children at every level. When a node covers a single element, it's a leaf—no further subdivision happens, so its theoretical children are never created.

The key insight: While the tree has only ~2n meaningful nodes, the array indices can extend beyond 2n due to these gaps. This is why we allocate 4n space rather than exactly 2n.

Range Determination

During construction, each recursive call knows its range [start, end] explicitly—it's passed as parameters. We don't need to compute the range from the node index. The tree array stores only the aggregate values (sums, minimums, etc.), not the ranges themselves.

The 4n Space Requirement: A Rigorous Analysis

One of the most commonly asked questions about segment trees is: Why allocate 4n space when the tree has only ~2n nodes?

Let's analyze this rigorously.

Case 1: n is a power of 2 (n = 2^k)

When n = 2^k, the segment tree is a perfect binary tree:

Level 0: 1 node (root)
Level 1: 2 nodes
Level 2: 4 nodes
...
Level k: 2^k = n nodes (leaves)

Total nodes = 1 + 2 + 4 + ... + n = 2n - 1

Since the last used index is 2n - 1 + (n-1) = 2n - 1 + n - 1 ≈ 2n, we need about 2n space.

Case 2: n is not a power of 2

This is where things get interesting. Let's say n = 6. We need to fit 6 leaves, so we need a tree of height ⌈log₂(6)⌉ = 3.

A perfect binary tree of height 3 would have 2^4 - 1 = 15 nodes, with indices 1 through 15. But our tree isn't perfect—some leaves appear at level 2 (nodes 5 and 7), while others are at level 3 (nodes 8, 9, 12, 13).

The highest index we use depends on where the leaves land:

Node 12 (leaf for a₃) and Node 13 (leaf for a₄) are at indices 12 and 13
These are children of node 6, which covers [3, 4]

In general, for n elements, the maximum index used is bounded by:

max_index ≤ 2 × (2^⌈log₂(n)⌉) - 1 ≤ 2 × 2n - 1 = 4n - 1

Therefore, 4n is a safe upper bound for any 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
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
"""
Analysis of segment tree space requirements.
This script demonstrates why 4n is necessary and sufficient.
"""
 
import math
 
def analyze_space_requirements(n: int) -> dict:
    """
    Analyze the space needed for a segment tree with n elements.
    
    Returns a dictionary with:
    - n: input size
    - tree_height: height of the tree
    - theoretical_max_index: maximum possible index
    - actual_nodes: number of actually used nodes
    - efficiency: ratio of used nodes to allocated space
    """
    if n == 0:
        return {"n": 0, "tree_height": 0, "theoretical_max_index": 0,
                "actual_nodes": 0, "efficiency": 0.0}
    
    # Tree height (0-indexed from root)
    height = math.ceil(math.log2(n)) if n > 1 else 0
    
    # Size of a perfect binary tree with this height
    perfect_size = 2 ** (height + 1) - 1
    
    # Maximum index used (some leaves may be at second-to-last level)
    # For safety, consider the worst case where leaves extend to last level
    max_index = 2 ** (height + 1) - 1
    
    # Actual number of nodes: n leaves + (n-1) internal nodes
    actual_nodes = 2 * n - 1
    
    # If we allocate 4n space
    allocated_4n = 4 * n
    
    # Efficiency
    efficiency = actual_nodes / allocated_4n if allocated_4n > 0 else 0
    
    return {
        "n": n,
        "tree_height": height,
        "perfect_tree_size": perfect_size,
        "max_index_possible": max_index,
        "actual_nodes": actual_nodes,
        "allocated_4n": allocated_4n,
        "fits_in_2n": max_index <= 2 * n,
        "fits_in_4n": max_index <= 4 * n,
        "efficiency": f"{efficiency:.2%}"
    }
 
 
def demonstrate_space_analysis():
    """Show space analysis for various array sizes."""
    
    print("=" * 70)
    print("SEGMENT TREE SPACE ANALYSIS")
    print("=" * 70)
    
    test_cases = [1, 2, 3, 4, 5, 6, 7, 8, 10, 15, 16, 17, 100, 1000]
    
    print(f"\n{'n':>6} {'Height':>7} {'Perfect':>8} {'MaxIdx':>8} "
          f"{'Actual':>8} {'4n':>6} {'Fits 2n':>8} {'Effic':>8}")
    print("-" * 70)
    
    for n in test_cases:
        result = analyze_space_requirements(n)
        print(f"{result['n']:>6} {result['tree_height']:>7} "
              f"{result['perfect_tree_size']:>8} {result['max_index_possible']:>8} "
              f"{result['actual_nodes']:>8} {result['allocated_4n']:>6} "
              f"{'Yes' if result['fits_in_2n'] else 'No':>8} "
              f"{result['efficiency']:>8}")
    
    print("\n" + "=" * 70)
    print("KEY OBSERVATIONS:")
    print("=" * 70)
    print("""
    1. When n is a power of 2, the tree fits in 2n space
    2. When n is NOT a power of 2, we may need up to 4n space
    3. 4n is always sufficient for ANY value of n
    4. The efficiency (actual_nodes / 4n) ranges from ~25% to ~50%
    5. If space is critical, use 2^⌈log₂(n)⌉ × 2 for tighter bound
    """)
 
 
def find_maximum_index_empirically(n: int) -> int:
    """
    Build an actual segment tree and find the maximum index used.
    This validates our theoretical analysis.
    """
    if n == 0:
        return 0
    
    max_idx_seen = 0
    
    def build(node: int, start: int, end: int):
        nonlocal max_idx_seen
        max_idx_seen = max(max_idx_seen, node)
        
        if start == end:
            return
        
        mid = (start + end) // 2
        build(2 * node, start, mid)
        build(2 * node + 1, mid + 1, end)
    
    build(1, 0, n - 1)
    return max_idx_seen
 
 
def validate_4n_bound():
    """Empirically verify that 4n is always sufficient."""
    print("\nVALIDATING 4n BOUND EMPIRICALLY")
    print("-" * 40)
    
    for n in range(1, 1001):
        max_idx = find_maximum_index_empirically(n)
        if max_idx > 4 * n:
            print(f"FAILED for n={n}: max_idx={max_idx}, 4n={4*n}")
            return False
    
    print("✓ Verified: max_index ≤ 4n for all n from 1 to 1000")
    return True
 
 
if __name__ == "__main__":
    demonstrate_space_analysis()
    print()
    validate_4n_bound()

Tighter Space Bound

If memory is critical, you can compute a tighter bound: allocate 2 × 2^⌈log₂(n)⌉ space. For n=6, this is 2 × 8 = 16 (instead of 24 with 4n). For n=1000, this is 2 × 1024 = 2048 (instead of 4000). However, 4n is simpler to compute and only about 2× larger than optimal.

Navigating the Tree with Arithmetic

The array representation enables navigation without pointers:

Core Navigation Formulas (1-indexed):

Operation	Formula	Bit Operation
Left child of node i	2i	i << 1
Right child of node i	2i + 1	(i << 1) \| 1
Parent of node i	i / 2	i >> 1
Is i a left child?	i is even	(i & 1) == 0
Is i a right child?	i is odd	(i & 1) == 1
Sibling of node i	i is even ? i+1 : i-1	i ^ 1
Level of node i	⌊log₂(i)⌋	Most significant bit position

tree_navigation.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
"""
Efficient tree navigation using array indices.
All operations are O(1) using simple arithmetic.
"""
 
class TreeNavigation:
    """
    Utility class demonstrating tree navigation formulas.
    All indices are 1-based (root at index 1).
    """
    
    @staticmethod
    def left_child(i: int) -> int:
        """Get index of left child. O(1)"""
        return 2 * i  # Or: i << 1
    
    @staticmethod
    def right_child(i: int) -> int:
        """Get index of right child. O(1)"""
        return 2 * i + 1  # Or: (i << 1) | 1
    
    @staticmethod
    def parent(i: int) -> int:
        """Get index of parent. O(1)"""
        return i // 2  # Or: i >> 1
    
    @staticmethod
    def is_left_child(i: int) -> bool:
        """Check if node is a left child. O(1)"""
        return i % 2 == 0  # Or: (i & 1) == 0
    
    @staticmethod
    def is_right_child(i: int) -> bool:
        """Check if node is a right child. O(1)"""
        return i % 2 == 1  # Or: (i & 1) == 1
    
    @staticmethod
    def sibling(i: int) -> int:
        """
        Get index of sibling node. O(1)
        XOR with 1 flips the last bit: even <-> odd.
        """
        return i ^ 1  # 2 -> 3, 3 -> 2, 4 -> 5, 5 -> 4, etc.
    
    @staticmethod
    def level(i: int) -> int:
        """
        Get the level of node i (root is level 0). O(log i)
        This is the position of the most significant bit.
        """
        if i <= 0:
            return -1
        return i.bit_length() - 1
    
    @staticmethod
    def is_root(i: int) -> bool:
        """Check if node is the root. O(1)"""
        return i == 1
    
    @staticmethod
    def path_from_root(i: int) -> list:
        """
        Get the path of indices from root to node i.
        O(log i) time, O(log i) space.
        """
        path = []
        while i >= 1:
            path.append(i)
            i //= 2
        return path[::-1]  # Reverse to start from root
 
 
def demonstrate_navigation():
    """Show navigation operations in action."""
    nav = TreeNavigation()
    
    print("=" * 50)
    print("TREE NAVIGATION DEMONSTRATION")
    print("=" * 50)
    
    print("\nTree structure (indices only):")
    print("""
              1
            /   \
           2     3
          / \   / \
         4   5 6   7
        /\ /\ /\ /\
       8 9... etc
    """)
    
    test_nodes = [1, 2, 3, 4, 7, 12]
    
    for node in test_nodes:
        print(f"\nNode {node}:")
        print(f"  Left child:  {nav.left_child(node)}")
        print(f"  Right child: {nav.right_child(node)}")
        print(f"  Parent:      {nav.parent(node)}")
        print(f"  Level:       {nav.level(node)}")
        print(f"  Is left:     {nav.is_left_child(node)}")
        print(f"  Is right:    {nav.is_right_child(node)}")
        print(f"  Sibling:     {nav.sibling(node)}")
        print(f"  Path:        {' -> '.join(map(str, nav.path_from_root(node)))}")
    
    # Verify relationships
    print("\n" + "=" * 50)
    print("VERIFICATION")
    print("=" * 50)
    
    print("\nParent-child relationships:")
    for i in range(1, 8):
        left = nav.left_child(i)
        right = nav.right_child(i)
        print(f"  {i} -> left: {left}, right: {right}")
        assert nav.parent(left) == i, "Left child's parent should be i"
        assert nav.parent(right) == i, "Right child's parent should be i"
    print("  All parent-child relationships verified! ✓")
    
    print("\nSibling relationships:")
    pairs = [(2, 3), (4, 5), (6, 7), (8, 9)]
    for a, b in pairs:
        assert nav.sibling(a) == b
        assert nav.sibling(b) == a
    print("  All sibling relationships verified! ✓")
 
 
if __name__ == "__main__":
    demonstrate_navigation()

Why Bit Operations?

In competitive programming and performance-critical code, you'll often see i << 1 instead of 2 * i. Modern compilers optimize both to the same machine code, but the bit notation makes the binary tree structure explicit: shifting left extends the path, and the last bit determines left (0) vs right (1) branch.

Visualizing the Array-to-Tree Mapping

Let's create a comprehensive visualization that shows how the segment tree array maps to the conceptual tree structure:

visualize_mapping.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
"""
Visualization of segment tree array to tree mapping.
Shows both the array layout and the tree structure.
"""
 
class SegmentTreeVisualizer:
    """
    A segment tree implementation with visualization capabilities.
    """
    
    def __init__(self, arr):
        self.n = len(arr)
        self.arr = arr
        self.tree = [None] * (4 * self.n) if self.n > 0 else []
        self.ranges = [None] * (4 * self.n) if self.n > 0 else []
        
        if self.n > 0:
            self._build(1, 0, self.n - 1)
    
    def _build(self, node, start, end):
        # Store the range this node covers
        self.ranges[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 show_array_layout(self):
        """Display the tree as a flat array."""
        print("\n" + "=" * 60)
        print("ARRAY LAYOUT")
        print("=" * 60)
        print(f"\nOriginal array: {self.arr}")
        print(f"Array indices:  {list(range(self.n))}")
        print()
        
        print("Segment tree array (non-null entries):")
        print(f"{'Index':<8} {'Value':<10} {'Range':<15} {'Type':<10}")
        print("-" * 45)
        
        for i in range(1, len(self.tree)):
            if self.tree[i] is not None:
                r = self.ranges[i]
                range_str = f"[{r[0]}, {r[1]}]"
                node_type = "Leaf" if r[0] == r[1] else "Internal"
                if i == 1:
                    node_type = "Root"
                print(f"{i:<8} {self.tree[i]:<10} {range_str:<15} {node_type:<10}")
    
    def show_tree_structure(self):
        """Display the tree structure with levels."""
        print("\n" + "=" * 60)
        print("TREE STRUCTURE (by level)")
        print("=" * 60)
        
        # Find maximum level
        max_level = 0
        for i in range(1, len(self.tree)):
            if self.tree[i] is not None:
                level = (i).bit_length() - 1
                max_level = max(max_level, level)
        
        for level in range(max_level + 1):
            start_idx = 2 ** level
            end_idx = 2 ** (level + 1)
            
            nodes_at_level = []
            for i in range(start_idx, end_idx):
                if i < len(self.tree) and self.tree[i] is not None:
                    r = self.ranges[i]
                    nodes_at_level.append(f"[{i}]={self.tree[i]} ({r[0]},{r[1]})")
            
            if nodes_at_level:
                print(f"\nLevel {level}:")
                for node in nodes_at_level:
                    print(f"    {node}")
    
    def show_parent_child_relationships(self):
        """Show parent-child connections."""
        print("\n" + "=" * 60)
        print("PARENT-CHILD RELATIONSHIPS")
        print("=" * 60)
        
        for i in range(1, len(self.tree)):
            if self.tree[i] is not None and self.ranges[i][0] != self.ranges[i][1]:
                # This is an internal node
                left = 2 * i
                right = 2 * i + 1
                
                left_val = self.tree[left] if left < len(self.tree) else None
                right_val = self.tree[right] if right < len(self.tree) else None
                
                if left_val is not None and right_val is not None:
                    print(f"\n  Node {i} (value={self.tree[i]}, range={self.ranges[i]}):")
                    print(f"    ├─ Left child:  Node {left} (value={left_val})")
                    print(f"    └─ Right child: Node {right} (value={right_val})")
                    print(f"    Verification: {left_val} + {right_val} = {left_val + right_val}")
 
 
def demonstrate_visualization():
    """Complete visualization demonstration."""
    
    # Example array
    arr = [1, 3, 5, 7, 9, 11]
    
    print("=" * 60)
    print("SEGMENT TREE VISUALIZATION")
    print("=" * 60)
    
    vis = SegmentTreeVisualizer(arr)
    
    vis.show_array_layout()
    vis.show_tree_structure()
    vis.show_parent_child_relationships()
    
    # ASCII art representation
    print("\n" + "=" * 60)
    print("ASCII TREE REPRESENTATION")
    print("=" * 60)
    print("""
                          [1]=36
                        [0,5]
                       /     \
                  [2]=9       [3]=27
                 [0,2]        [3,5]
                /     \      /     \
            [4]=4   [5]=5  [6]=16  [7]=11
           [0,1]   [2,2]  [3,4]   [5,5]
           /   \          /   \
       [8]=1 [9]=3   [12]=7 [13]=9
       [0,0] [1,1]   [3,3]  [4,4]
       
    Note: Nodes 10, 11, 14, 15 don't exist
          (their would-be parents are leaves)
    """)
 
 
if __name__ == "__main__":
    demonstrate_visualization()

Memory Layout and Cache Efficiency

The array representation isn't just elegant—it's also efficient. Let's understand why:

Cache Locality

When we traverse from root to a leaf, we access indices: 1 → 2 or 3 → 4,5,6, or 7 → etc. These indices are relatively close together in memory, especially at lower levels. Compare this to a pointer-based tree where each node could be allocated anywhere in the heap.

Memory Overhead

With pointers:

Each node needs: value (8 bytes) + left pointer (8 bytes) + right pointer (8 bytes) = 24 bytes minimum
For n=1000 elements: ~2000 nodes × 24 bytes = ~48KB

With array:

Each node needs: value only (8 bytes)
For n=1000 elements: 4000 slots × 8 bytes = 32KB
Plus, contiguous memory = better cache behavior

Memory Comparison: Array vs Pointer Representation
Aspect	Array Representation	Pointer Representation
Memory per node	Value only (~8 bytes)	Value + 2 pointers (~24 bytes)
Total for n=1000	~32KB (4n slots)	~48KB (2n nodes × 24)
Cache locality	Excellent (contiguous)	Poor (scattered heap)
Allocation	Single array	Many small allocations
Navigation cost	Arithmetic (O(1))	Pointer dereference (O(1) but cache miss)
Flexibility	Fixed size	Dynamic

Modern CPU Considerations

Modern CPUs prefetch sequential memory access patterns. When traversing the segment tree array, the CPU can predict and prefetch upcoming indices. With scattered pointer-based nodes, each access is a potential cache miss. For large trees, this difference can be substantial—array-based trees can be 2-3× faster in practice.

Alternative Representations

While the 1-indexed array is most common, you'll encounter variations:

1. Pointer-Based Segment Trees

Useful when:

The tree structure changes dynamically
Memory is allocated incrementally
You need to support more complex operations (like persistent segment trees)

2. Implicit Segment Trees

For very sparse data or huge ranges (like [0, 10^9]):

Nodes are created on-demand
Uses hash maps or dynamic allocation
Query range: O(log n), but with larger constants

3. Recursive Call-Based (No Explicit Tree)

Some implementations don't store intermediate values explicitly:

Recompute values on each query
Saves memory at the cost of query time
Rarely used in practice

pointer_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
"""
Pointer-based segment tree implementation for comparison.
This approach is more flexible but less cache-efficient.
"""
 
class TreeNode:
    """A node in the pointer-based segment tree."""
    
    __slots__ = ['value', 'left', 'right', 'start', 'end']
    
    def __init__(self, start: int, end: int):
        self.value = 0
        self.left = None   # Left child pointer
        self.right = None  # Right child pointer
        self.start = start
        self.end = end
 
 
class PointerSegmentTree:
    """
    Segment tree using explicit node objects and pointers.
    
    Advantages:
    - More intuitive structure
    - Can easily extend with additional node attributes
    - Supports dynamic modifications
    
    Disadvantages:
    - Higher memory overhead (pointers)
    - Worse cache locality
    - More complex memory management
    """
    
    def __init__(self, arr):
        self.n = len(arr)
        self.root = self._build(arr, 0, self.n - 1) if self.n > 0 else None
    
    def _build(self, arr, start, end) -> TreeNode:
        """Recursively build the tree."""
        node = TreeNode(start, end)
        
        if start == end:
            node.value = arr[start]
            return node
        
        mid = (start + end) // 2
        node.left = self._build(arr, start, mid)
        node.right = self._build(arr, mid + 1, end)
        node.value = node.left.value + node.right.value
        
        return node
    
    def print_tree(self, node=None, indent=""):
        """Print the tree structure."""
        if node is None:
            node = self.root
        
        if node is None:
            print("Empty tree")
            return
        
        print(f"{indent}[{node.start},{node.end}] = {node.value}")
        
        if node.left:
            print(f"{indent}├── Left:")
            self.print_tree(node.left, indent + "│   ")
        
        if node.right:
            print(f"{indent}└── Right:")
            self.print_tree(node.right, indent + "    ")
 
 
# Comparison
def compare_implementations():
    """Compare array-based vs pointer-based implementations."""
    import sys
    
    arr = [1, 3, 5, 7, 9, 11]
    
    print("=" * 50)
    print("IMPLEMENTATION COMPARISON")
    print("=" * 50)
    
    # Pointer-based
    print("\nPointer-based tree structure:")
    ptr_tree = PointerSegmentTree(arr)
    ptr_tree.print_tree()
    
    # Memory estimate (rough)
    node_count = 2 * len(arr) - 1
    ptr_memory = node_count * (8 + 8 + 8 + 8 + 8)  # value + 2 ptrs + 2 ints
    arr_memory = 4 * len(arr) * 8  # 4n slots, 8 bytes each
    
    print(f"\nMemory estimates (n={len(arr)}):")
    print(f"  Pointer-based: ~{ptr_memory} bytes")
    print(f"  Array-based:   ~{arr_memory} bytes")
 
 
if __name__ == "__main__":
    compare_implementations()

When to Use Pointer-Based Trees

Unless you need dynamic tree modifications or are implementing persistent segment trees, stick with the array representation. It's simpler, faster, and uses less memory. The pointer-based approach is primarily useful in advanced scenarios like persistent data structures or when the tree topology changes during execution.

Practical Considerations and Common Pitfalls

When implementing segment trees in practice, watch out for these common issues:

Common Pitfalls

•Array Size Underallocation — Allocating 2n or 3n instead of 4n causes index-out-of-bounds errors for non-power-of-2 sizes. Always use 4n or the precise formula.
•0-Based vs 1-Based Confusion — Mixing conventions leads to incorrect child/parent calculations. Choose one and stick with it.
•Integer Overflow — For sum queries, internal nodes can exceed the input value range. In C++, use long long; in Java, use long.
•Off-by-One Errors — The range [start, end] is inclusive. Forgetting this causes subtle bugs in range calculations.
•Forgetting Base Case — Not handling the n=0 case crashes when building from an empty array.

Best Practices

•Use 1-Based Indexing — Cleaner formulas, consistent with most references.
•Always Allocate 4n — Simple rule that always works. Optimize later if needed.
•Test with Various Sizes — Powers of 2, one less, one more. These expose edge cases.
•Verify Root Value — After construction, check that tree[1] equals the aggregate of the entire array.
•Comment Range Parameters — Document that start and end are inclusive bounds.

Summary: Mastering the Array Representation

We've explored the array-based representation of segment trees in depth. Here are the essential takeaways:

Key Takeaways

•Binary Tree in a Flat Array — Each node at index i has children at 2i and 2i+1, enabling pointer-free navigation.
•4n Space Bound — Due to gaps from non-power-of-2 sizes, we need up to 4n array slots, though only ~2n are actually used.
•Efficient Navigation — Parent/child relationships are computed with simple arithmetic or bit operations in O(1).
•Better Performance — Contiguous memory provides excellent cache locality compared to pointer-based trees.
•Range-to-Index Independence — The range a node represents is tracked during recursion, not stored with the node.
•Practical Simplicity — The array representation is simpler to implement, debug, and maintain than pointer alternatives.

What's Next:

Now that we understand both construction and representation, we're ready for the most important operation: querying. The next page explores how to efficiently combine ranges to answer queries like "What is the sum of elements from index 2 to 7?" in O(log n) time.

Page Complete

You now have a complete understanding of how segment trees are stored in arrays. The elegant mapping from tree nodes to array indices enables efficient, cache-friendly operations. Next, we'll see how to leverage this structure for lightning-fast range queries.