Segment Tree Operations - Learning Module

Loading content...

0/276

Update Operation: Point Updates

Keeping the Tree Fresh: Efficient Updates

A segment tree would be of limited use if it could only answer queries on static data. Real-world applications need to handle dynamic data—values change, and queries must reflect those changes instantly.

The naive approach to updates would be devastating: change the array element, then rebuild the entire tree. This costs O(n) per update, negating all the benefits of the segment tree structure.

Fortunately, the segment tree structure enables point updates in O(log n) time. When a single element changes, only the nodes on the path from that element's leaf to the root need updating. Since the tree has O(log n) height, this path contains exactly O(log n) nodes.

What You Will Learn

By the end of this page, you will understand the point update algorithm, how changes propagate from leaf to root, why only O(log n) nodes need updating, and how to implement both absolute updates (set to new value) and relative updates (add/subtract a delta).

The Update Problem

Let's formalize what we're solving:

Point Update Problem: Given:

A segment tree built from array A of n elements
An index i where 0 ≤ i ≤ n-1
A new value v

Task:

Change A[i] to v
Update the segment tree so all future queries are correct
Do this in O(log n) time

What nodes are affected?

When element A[i] changes, which tree nodes need updating? Exactly those nodes whose range contains index i:

The leaf node for index i (it covers [i, i])
Its parent (covers a range containing i)
Its grandparent (covers a larger range containing i)
... up to the root (covers [0, n-1], which includes i)

Example: Update index 3 in array [1, 3, 5, 7, 9, 11]

                    [0,5]=36
                   /        \
             [0,2]=9        [3,5]=27  ← contains 3
            /      \        /       \
       [0,1]=4   [2,2]=5  [3,4]=16  [5,5]=11
       /    \              /    \         ↑
   [0,0]=1 [1,1]=3    [3,3]=7  [4,4]=9   contains 3
                         ↑
                    leaf for index 3

Nodes affected by updating index 3:

Node [3,3] = 7 (leaf)
Node [3,4] = 16 (parent)
Node [3,5] = 27 (grandparent)
Node [0,5] = 36 (root)

That's exactly 4 nodes—the height of the tree plus 1.

The Update Algorithm

The update algorithm follows the same recursive structure as construction and query, with a key difference: we only descend into the subtree containing the target index.

Algorithm Steps:

Start at the root
If current node is the target leaf (start == end == i): update the value
Otherwise, determine which child contains index i:
- If i ≤ mid: descend into left child
- If i > mid: descend into right child
After returning from the recursive call, recalculate current node's value from its children

segment_tree_update.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
"""
Segment Tree Point Update Implementation
=========================================
 
The update function modifies a single element and propagates
changes up to the root in O(log n) time.
"""
 
class SegmentTree:
    """
    Segment tree with point update support.
    """
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n) if self.n > 0 else []
        self.arr = arr[:]  # Keep a copy of the original array
        
        if self.n > 0:
            self._build(1, 0, self.n - 1)
    
    def _build(self, node, start, end):
        if start == end:
            self.tree[node] = self.arr[start]
            return
        
        mid = (start + end) // 2
        self._build(2 * node, start, mid)
        self._build(2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def update(self, index: int, value: int) -> None:
        """
        Update the element at 'index' to 'value'.
        
        Args:
            index: The index to update (0-indexed)
            value: The new value
        
        Time Complexity: O(log n)
        
        Example:
            st = SegmentTree([1, 3, 5, 7, 9, 11])
            st.update(3, 100)  # Change arr[3] from 7 to 100
        """
        if index < 0 or index >= self.n:
            raise IndexError(f"Index {index} out of bounds [0, {self.n-1}]")
        
        self.arr[index] = value  # Update our copy of the array
        self._update(1, 0, self.n - 1, index, value)
    
    def _update(self, node: int, start: int, end: int, index: int, value: int) -> None:
        """
        Recursive update helper.
        
        Args:
            node: Current node index in tree
            start, end: Range this node covers
            index: Target index to update
            value: New value for arr[index]
        """
        # Base case: reached the target leaf
        if start == end:
            # This is the leaf node for arr[index]
            self.tree[node] = value
            return
        
        mid = (start + end) // 2
        
        # Determine which child contains the target index
        if index <= mid:
            # Target is in left subtree
            self._update(2 * node, start, mid, index, value)
        else:
            # Target is in right subtree
            self._update(2 * node + 1, mid + 1, end, index, value)
        
        # After updating the child, recalculate this node
        # This is the "propagation" step
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    def query(self, L: int, R: int) -> int:
        """Query sum of [L, R]."""
        if self.n == 0 or L > R:
            return 0
        return self._query(1, 0, self.n - 1, L, R)
    
    def _query(self, node, start, end, L, R):
        if R < start or L > end:
            return 0
        if L <= start and end <= R:
            return self.tree[node]
        
        mid = (start + end) // 2
        return (self._query(2 * node, start, mid, L, R) +
                self._query(2 * node + 1, mid + 1, end, L, R))
 
 
# Demonstration with step-by-step tracing
def trace_update():
    """Trace an update step by step."""
    arr = [1, 3, 5, 7, 9, 11]
    st = SegmentTree(arr)
    
    print("=" * 60)
    print("UPDATE TRACING: Change arr[3] from 7 to 100")
    print("=" * 60)
    
    print(f"\nOriginal array: {arr}")
    print(f"Original tree root (sum): {st.tree[1]}")
    print(f"Sum of [3,5] before: {st.query(3, 5)}")
    
    print("""
    Update path for index 3:
    
    1. Start at root: node=1, [0,5]
       - index=3, mid=2
       - 3 > 2, so descend RIGHT
    
    2. At node=3, [3,5]
       - index=3, mid=4
       - 3 ≤ 4, so descend LEFT
    
    3. At node=6, [3,4]
       - index=3, mid=3
       - 3 ≤ 3, so descend LEFT
    
    4. At node=12, [3,3]
       - start=end=3=index
       - BASE CASE: set tree[12] = 100
    
    Now propagate back up:
    
    5. Return to node=6, [3,4]
       - tree[6] = tree[12] + tree[13] = 100 + 9 = 109
    
    6. Return to node=3, [3,5]
       - tree[3] = tree[6] + tree[7] = 109 + 11 = 120
    
    7. Return to node=1, [0,5]
       - tree[1] = tree[2] + tree[3] = 9 + 120 = 129
    """)
    
    st.update(3, 100)
    
    print(f"Updated array: {st.arr}")
    print(f"Updated tree root (sum): {st.tree[1]}")
    print(f"Sum of [3,5] after: {st.query(3, 5)}")
    
    # Verify
    expected = sum(arr[:3]) + 100 + sum(arr[4:])
    print(f"\nExpected new sum: 1+3+5 + 100 + 9+11 = {expected}")
    print(f"Actual: {st.tree[1]}")
    print(f"Match: {st.tree[1] == expected} ✓")
 
 
if __name__ == "__main__":
    trace_update()

Propagation: The Key Insight

The most important part of the update algorithm happens as we return from the recursive call:

self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

This single line recalculates the current node's value after its child has been updated. Because updates happen recursively:

We first update the leaf (base case)
Then recalculate the leaf's parent
Then recalculate that node's parent
... all the way up to the root

This bottom-up propagation ensures every ancestor of the modified leaf reflects the change.

Why does this work?

Each internal node's value depends only on its two children:

tree[node] = combine(tree[left_child], tree[right_child])

When we update a leaf:

Its ancestors need to be recalculated
But nodes outside this path don't need updating—their children haven't changed

The invariant: After update completes, every node's value equals the correct aggregate of its range, as if we had rebuilt the entire tree.

The efficiency: Only O(log n) nodes are updated out of the ~2n total nodes.

Think of It Like a Spreadsheet

Imagine a spreadsheet where each cell is a sum of cells below it. When you change a base cell, Excel recalculates only the cells that depend on it—not the entire sheet. Segment tree updates work the same way: change a leaf, and only its ancestors need recalculation.

Update Variants: Set, Add, and Multiply

There are different types of point updates:

1. Absolute Update (Set) Set arr[i] = v, replacing the old value entirely.

2. Relative Update (Add/Delta) Add a delta to the existing value: arr[i] = arr[i] + delta.

3. Multiplicative Update (Scale) Multiply by a factor: arr[i] = arr[i] × factor.

The algorithm structure is identical; only the leaf update logic changes.

update_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
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
"""
Different types of point updates for segment trees.
"""
 
class SegmentTreeWithVariants:
    """
    Segment tree supporting multiple update types.
    """
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n) if self.n > 0 else []
        self.arr = arr[:]
        
        if self.n > 0:
            self._build(1, 0, self.n - 1)
    
    def _build(self, node, start, end):
        if start == end:
            self.tree[node] = self.arr[start]
            return
        
        mid = (start + end) // 2
        self._build(2 * node, start, mid)
        self._build(2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    # =========================================
    # Update Type 1: SET (Absolute Update)
    # =========================================
    def set_value(self, index: int, value: int) -> None:
        """
        Set arr[index] = value.
        
        This replaces the existing value with a new one.
        """
        if index < 0 or index >= self.n:
            raise IndexError(f"Index {index} out of bounds")
        
        old_value = self.arr[index]
        self.arr[index] = value
        self._update_set(1, 0, self.n - 1, index, value)
        
        # Return the old value for logging/undo purposes
        return old_value
    
    def _update_set(self, node, start, end, index, value):
        if start == end:
            self.tree[node] = value
            return
        
        mid = (start + end) // 2
        if index <= mid:
            self._update_set(2 * node, start, mid, index, value)
        else:
            self._update_set(2 * node + 1, mid + 1, end, index, value)
        
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    # =========================================
    # Update Type 2: ADD (Relative Update)
    # =========================================
    def add_value(self, index: int, delta: int) -> None:
        """
        Set arr[index] = arr[index] + delta.
        
        This adds a delta to the existing value.
        Useful when you only know the change, not the new absolute value.
        """
        if index < 0 or index >= self.n:
            raise IndexError(f"Index {index} out of bounds")
        
        self.arr[index] += delta
        self._update_add(1, 0, self.n - 1, index, delta)
    
    def _update_add(self, node, start, end, index, delta):
        if start == end:
            self.tree[node] += delta
            return
        
        mid = (start + end) // 2
        if index <= mid:
            self._update_add(2 * node, start, mid, index, delta)
        else:
            self._update_add(2 * node + 1, mid + 1, end, index, delta)
        
        # For add updates, we can also just add delta to each ancestor
        # But recalculating from children is more general and works for min/max too
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
    
    # =========================================
    # Update Type 3: MULTIPLY (Scale Update)
    # =========================================
    def multiply_value(self, index: int, factor: int) -> None:
        """
        Set arr[index] = arr[index] * factor.
        
        This multiplies the existing value by a factor.
        """
        if index < 0 or index >= self.n:
            raise IndexError(f"Index {index} out of bounds")
        
        self.arr[index] *= factor
        # For multiply, we need to set to the new absolute value
        self._update_set(1, 0, self.n - 1, index, self.arr[index])
    
    def query(self, L: int, R: int) -> int:
        """Query sum of [L, R]."""
        if self.n == 0:
            return 0
        return self._query(1, 0, self.n - 1, L, R)
    
    def _query(self, node, start, end, L, R):
        if R < start or L > end:
            return 0
        if L <= start and end <= R:
            return self.tree[node]
        mid = (start + end) // 2
        return (self._query(2 * node, start, mid, L, R) +
                self._query(2 * node + 1, mid + 1, end, L, R))
    
    def get_value(self, index: int) -> int:
        """Get the current value at index."""
        return self.arr[index]
 
 
def demonstrate_update_variants():
    """Demonstrate different update types."""
    
    print("=" * 60)
    print("UPDATE VARIANTS DEMONSTRATION")
    print("=" * 60)
    
    arr = [10, 20, 30, 40, 50]
    st = SegmentTreeWithVariants(arr)
    
    print(f"\nInitial array: {st.arr}")
    print(f"Initial sum: {st.query(0, 4)}")
    
    # Set update
    print("\n--- SET Update ---")
    print("Setting arr[2] = 100 (was 30)")
    st.set_value(2, 100)
    print(f"Array after set: {st.arr}")
    print(f"Sum after set: {st.query(0, 4)}")
    
    # Add update
    print("\n--- ADD Update ---")
    print("Adding 25 to arr[3] (was 40)")
    st.add_value(3, 25)
    print(f"Array after add: {st.arr}")
    print(f"Sum after add: {st.query(0, 4)}")
    
    # Multiply update
    print("\n--- MULTIPLY Update ---")
    print("Multiplying arr[0] by 3 (was 10)")
    st.multiply_value(0, 3)
    print(f"Array after multiply: {st.arr}")
    print(f"Sum after multiply: {st.query(0, 4)}")
    
    # Verify
    expected = sum(st.arr)
    print(f"\nVerification:")
    print(f"  Array: {st.arr}")
    print(f"  Sum via sum(): {expected}")
    print(f"  Sum via query: {st.query(0, 4)}")
    print(f"  Match: {expected == st.query(0, 4)} ✓")
 
 
if __name__ == "__main__":
    demonstrate_update_variants()

Add Updates for Sum Trees

For sum trees specifically, add updates can be optimized: instead of recalculating from children, you can propagate the delta directly up the path (add delta to each ancestor). However, the recalculating approach is more general and works for min/max trees too.

Update for Different Tree Operations

Just like queries, updates work for any associative operation. The update algorithm remains the same—only the propagation formula changes.

update_operations.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
"""
Point updates for different segment tree operations.
"""
 
from typing import Callable, TypeVar
from math import gcd
 
T = TypeVar('T')
 
 
class GenericSegmentTree:
    """
    Generic segment tree with update support.
    """
    
    def __init__(
        self,
        arr: list,
        combine: Callable[[T, T], T],
        identity: T
    ):
        self.n = len(arr)
        self.combine = combine
        self.identity = identity
        self.tree = [identity] * (4 * self.n) if self.n > 0 else []
        self.arr = arr[:]
        
        if self.n > 0:
            self._build(1, 0, self.n - 1)
    
    def _build(self, node, start, end):
        if start == end:
            self.tree[node] = self.arr[start]
            return
        
        mid = (start + end) // 2
        self._build(2 * node, start, mid)
        self._build(2 * node + 1, mid + 1, end)
        self.tree[node] = self.combine(
            self.tree[2 * node],
            self.tree[2 * node + 1]
        )
    
    def update(self, index: int, value: T) -> None:
        """Update arr[index] to value."""
        if index < 0 or index >= self.n:
            raise IndexError(f"Index {index} out of bounds")
        
        self.arr[index] = value
        self._update(1, 0, self.n - 1, index, value)
    
    def _update(self, node, start, end, index, value):
        if start == end:
            self.tree[node] = value
            return
        
        mid = (start + end) // 2
        if index <= mid:
            self._update(2 * node, start, mid, index, value)
        else:
            self._update(2 * node + 1, mid + 1, end, index, value)
        
        # Recalculate using the combine function
        self.tree[node] = self.combine(
            self.tree[2 * node],
            self.tree[2 * node + 1]
        )
    
    def query(self, L: int, R: int) -> T:
        if self.n == 0:
            return self.identity
        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 self.identity
        if L <= start and end <= R:
            return self.tree[node]
        
        mid = (start + end) // 2
        left = self._query(2 * node, start, mid, L, R)
        right = self._query(2 * node + 1, mid + 1, end, L, R)
        return self.combine(left, right)
 
 
# Specialized implementations
class SumTree(GenericSegmentTree):
    def __init__(self, arr):
        super().__init__(arr, lambda a, b: a + b, 0)
 
 
class MinTree(GenericSegmentTree):
    def __init__(self, arr):
        super().__init__(arr, min, float('inf'))
 
 
class MaxTree(GenericSegmentTree):
    def __init__(self, arr):
        super().__init__(arr, max, float('-inf'))
 
 
class GCDTree(GenericSegmentTree):
    def __init__(self, arr):
        super().__init__(arr, gcd, 0)
 
 
class XORTree(GenericSegmentTree):
    def __init__(self, arr):
        super().__init__(arr, lambda a, b: a ^ b, 0)
 
 
def demonstrate_update_operations():
    """Demonstrate updates for different tree types."""
    
    print("=" * 60)
    print("UPDATE OPERATIONS FOR DIFFERENT TREE TYPES")
    print("=" * 60)
    
    arr = [3, 1, 4, 1, 5, 9, 2, 6]
    print(f"\nInitial array: {arr}")
    
    # Sum tree
    print("\n=== SUM TREE ===")
    st_sum = SumTree(arr)
    print(f"Initial sum [0,7]: {st_sum.query(0, 7)}")
    st_sum.update(4, 50)  # Change 5 to 50
    print(f"After arr[4] = 50: {st_sum.query(0, 7)}")
    
    # Min tree
    print("\n=== MIN TREE ===")
    st_min = MinTree(arr)
    print(f"Initial min [0,7]: {st_min.query(0, 7)}")
    st_min.update(1, 10)  # Change 1 to 10
    st_min.update(3, 10)  # Change 1 to 10
    print(f"After removing 1s: {st_min.query(0, 7)}")
    
    # Max tree
    print("\n=== MAX TREE ===")
    st_max = MaxTree(arr)
    print(f"Initial max [0,7]: {st_max.query(0, 7)}")
    st_max.update(5, 100)  # Change 9 to 100
    print(f"After arr[5] = 100: {st_max.query(0, 7)}")
    
    # GCD tree
    print("\n=== GCD TREE ===")
    gcd_arr = [12, 18, 24, 6, 36]
    st_gcd = GCDTree(gcd_arr)
    print(f"Array: {gcd_arr}")
    print(f"Initial GCD [0,4]: {st_gcd.query(0, 4)}")
    st_gcd.update(3, 15)  # Change 6 to 15
    print(f"After arr[3] = 15: {st_gcd.query(0, 4)}")
    
    # XOR tree
    print("\n=== XOR TREE ===")
    xor_arr = [1, 2, 3, 4, 5, 6, 7, 8]
    st_xor = XORTree(xor_arr)
    print(f"Array: {xor_arr}")
    print(f"Initial XOR [0,7]: {st_xor.query(0, 7)}")
    st_xor.update(0, 0)  # Cancel out the 1
    print(f"After arr[0] = 0: {st_xor.query(0, 7)}")
 
 
if __name__ == "__main__":
    demonstrate_update_operations()

Update Propagation by Operation Type
Operation	Leaf Update	Propagation	Effect
Sum	tree[leaf] = new_value	parent = left + right	All ancestor sums updated
Min	tree[leaf] = new_value	parent = min(left, right)	Minimums recalculated
Max	tree[leaf] = new_value	parent = max(left, right)	Maximums recalculated
GCD	tree[leaf] = new_value	parent = gcd(left, right)	GCDs recalculated
XOR	tree[leaf] = new_value	parent = left ^ right	XOR chain recalculated

Complexity Analysis

Let's rigorously analyze the update operation's complexity:

Time Complexity: O(log n)

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

At each level, we visit exactly ONE node
We make exactly ONE recursive call (going left OR right, never both)
After reaching the leaf, we propagate back up, again visiting one node per level

Tree height = ⌈log₂(n)⌉ Nodes visited = height + 1 = O(log n) Work per node = O(1) (comparison, recursion, and one combine operation)

Total: O(log n)

Space Complexity: O(log n) auxiliary

The recursive implementation uses the call stack:

Stack depth = tree height = O(log n)
Each stack frame stores O(1) data (node index, start, end, etc.)

The total auxiliary space is O(log n).

Comparison with Alternatives:

Method	Update Time	Query Time	Build Time	Notes
Raw Array	O(1)	O(n)	O(1)	Simple but slow queries
Prefix Sums	O(n)	O(1)	O(n)	Rebuilds needed on update
Segment Tree	O(log n)	O(log n)	O(n)	Balanced tradeoff
Fenwick Tree	O(log n)	O(log n)	O(n)	Simpler for prefix sums

The Sweet Spot

Segment trees shine when you have a mix of queries and updates. With q queries and u updates on an array of size n, segment trees give O((q + u) log n + n) total time. Prefix sums would give O(q + u·n), which is much worse when u is large.

Common Pitfalls in Updates

Watch Out For These Errors

•Forgetting to Propagate — Updating the leaf without recalculating ancestors is the most common bug. Always recalculate after the recursive call returns.
•Wrong Child Selection — Using index < mid instead of index <= mid causes off-by-one errors. Remember: left child covers [start, mid], right covers [mid+1, end].
•Not Updating the Array Copy — If you keep a copy of the original array (for get_value operations), don't forget to update it too.
•Index Out of Bounds — Always validate the index before updating. Use explicit bounds checking.
•Wrong Combine Function — Using a different combine function for updates vs. build causes inconsistency. Extract the combine function to avoid this.

update_pitfalls.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
"""
Common pitfalls in segment tree updates and how to avoid them.
"""
 
class BrokenSegmentTree:
    """Example of BROKEN update implementations."""
    
    def __init__(self, arr):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        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 broken_update_no_propagation(self, node, start, end, index, value):
        """
        BUG: Updates the leaf but doesn't propagate up!
        The ancestors retain stale values.
        """
        if start == end:
            self.tree[node] = value
            return  # BUG: No propagation!
        
        mid = (start + end) // 2
        if index <= mid:
            self.broken_update_no_propagation(2 * node, start, mid, index, value)
        else:
            self.broken_update_no_propagation(2 * node + 1, mid + 1, end, index, value)
        
        # MISSING: self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
    
    def broken_update_wrong_child(self, node, start, end, index, value):
        """
        BUG: Uses index < mid instead of index <= mid.
        This causes off-by-one errors.
        """
        if start == end:
            self.tree[node] = value
            return
        
        mid = (start + end) // 2
        if index < mid:  # BUG: Should be index <= mid
            self.broken_update_wrong_child(2 * node, start, mid, index, value)
        else:
            self.broken_update_wrong_child(2 * node + 1, mid + 1, end, index, value)
        
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
 
 
class CorrectSegmentTree:
    """Correct implementation with defensive programming."""
    
    def __init__(self, arr):
        self.n = len(arr)
        self.arr = arr[:]
        self.tree = [0] * (4 * self.n) if self.n > 0 else []
        self.combine = lambda a, b: a + b  # Extracted for consistency
        
        if self.n > 0:
            self._build(1, 0, self.n - 1)
    
    def _build(self, node, start, end):
        if start == end:
            self.tree[node] = self.arr[start]
            return
        mid = (start + end) // 2
        self._build(2 * node, start, mid)
        self._build(2 * node + 1, mid + 1, end)
        self.tree[node] = self.combine(self.tree[2 * node], self.tree[2 * node + 1])
    
    def update(self, index: int, value: int) -> None:
        """Correct update with all checks."""
        # Bounds check
        if not (0 <= index < self.n):
            raise IndexError(f"Index {index} out of range [0, {self.n})")
        
        # Update our array copy
        self.arr[index] = value
        
        # Update the tree
        self._update(1, 0, self.n - 1, index, value)
        
        # Sanity check (can remove in production)
        assert self.tree[1] == sum(self.arr), "Tree invariant violated!"
    
    def _update(self, node, start, end, index, value):
        if start == end:
            self.tree[node] = value
            return
        
        mid = (start + end) // 2
        if index <= mid:  # CORRECT: <= not <
            self._update(2 * node, start, mid, index, value)
        else:
            self._update(2 * node + 1, mid + 1, end, index, value)
        
        # CORRECT: Always propagate
        self.tree[node] = self.combine(self.tree[2 * node], self.tree[2 * node + 1])
 
 
def test_pitfalls():
    """Test to catch update bugs."""
    
    print("=" * 50)
    print("TESTING FOR COMMON PITFALLS")
    print("=" * 50)
    
    arr = [1, 2, 3, 4, 5]
    st = CorrectSegmentTree(arr)
    
    print(f"\nInitial: {arr}, sum = {st.tree[1]}")
    
    # Series of updates
    updates = [(0, 10), (2, 30), (4, 50)]
    
    for idx, val in updates:
        st.update(idx, val)
        expected = sum(st.arr)
        actual = st.tree[1]
        status = "✓" if expected == actual else "✗"
        print(f"After arr[{idx}] = {val}: sum = {actual} (expected {expected}) {status}")
    
    print("\nAll updates correct!")
 
 
if __name__ == "__main__":
    test_pitfalls()

Complete Implementation with Updates

Here's a fully-featured segment tree implementation with both queries and updates:

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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
"""
Complete Segment Tree with Build, Query, and Update
====================================================
 
A production-ready implementation supporting:
- Construction in O(n)
- Range queries in O(log n)
- Point updates in O(log n)
- Multiple operation types
"""
 
from typing import List, Callable, TypeVar, Optional
 
T = TypeVar('T')
 
 
class SegmentTree:
    """
    Complete segment tree implementation.
    
    Time Complexities:
        - Build: O(n)
        - Query: O(log n)
        - Update: O(log n)
    
    Space Complexity: O(n)
    """
    
    def __init__(
        self,
        arr: List[T],
        combine: Callable[[T, T], T] = lambda a, b: a + b,
        identity: T = 0
    ):
        """
        Build a segment tree from the input array.
        
        Args:
            arr: Input array
            combine: Binary associative function
            identity: Identity element for combine
        """
        self.n = len(arr)
        self.combine = combine
        self.identity = identity
        
        if self.n == 0:
            self.tree = []
            self.arr = []
            return
        
        self.arr = arr[:]
        self.tree = [identity] * (4 * self.n)
        self._build(1, 0, self.n - 1)
    
    def _build(self, node: int, start: int, end: int) -> None:
        """Build the tree recursively."""
        if start == end:
            self.tree[node] = self.arr[start]
            return
        
        mid = (start + end) // 2
        left, right = 2 * node, 2 * node + 1
        
        self._build(left, start, mid)
        self._build(right, mid + 1, end)
        self.tree[node] = self.combine(self.tree[left], self.tree[right])
    
    def query(self, L: int, R: int) -> T:
        """
        Query the aggregate of [L, R].
        
        Time: O(log n)
        """
        if self.n == 0:
            return self.identity
        
        L = max(0, L)
        R = min(self.n - 1, R)
        
        if L > R:
            return self.identity
        
        return self._query(1, 0, self.n - 1, L, R)
    
    def _query(self, node: int, start: int, end: int, L: int, R: int) -> T:
        """Recursive query helper."""
        if R < start or L > end:
            return self.identity
        
        if L <= start and end <= R:
            return self.tree[node]
        
        mid = (start + end) // 2
        left_result = self._query(2 * node, start, mid, L, R)
        right_result = self._query(2 * node + 1, mid + 1, end, L, R)
        
        return self.combine(left_result, right_result)
    
    def update(self, index: int, value: T) -> None:
        """
        Update arr[index] to value.
        
        Time: O(log n)
        """
        if index < 0 or index >= self.n:
            raise IndexError(f"Index {index} out of range [0, {self.n})")
        
        self.arr[index] = value
        self._update(1, 0, self.n - 1, index, value)
    
    def _update(self, node: int, start: int, end: int, index: int, value: T) -> None:
        """Recursive update helper."""
        if start == end:
            self.tree[node] = value
            return
        
        mid = (start + end) // 2
        
        if index <= mid:
            self._update(2 * node, start, mid, index, value)
        else:
            self._update(2 * node + 1, mid + 1, end, index, value)
        
        self.tree[node] = self.combine(self.tree[2 * node], self.tree[2 * node + 1])
    
    def get(self, index: int) -> T:
        """Get the current value at index. O(1)"""
        if index < 0 or index >= self.n:
            raise IndexError(f"Index {index} out of range")
        return self.arr[index]
    
    def __repr__(self) -> str:
        if self.n == 0:
            return "SegmentTree(empty)"
        return f"SegmentTree(n={self.n}, root={self.tree[1]})"
    
    def __len__(self) -> int:
        return self.n
 
 
# ============================================================
# Comprehensive Test Suite
# ============================================================
 
def run_comprehensive_tests():
    """Full test suite for segment tree with updates."""
    
    print("=" * 60)
    print("SEGMENT TREE - COMPREHENSIVE TEST SUITE")
    print("=" * 60)
    
    # Test 1: Query after multiple updates
    print("\n[1] Query after multiple updates")
    st = SegmentTree([1, 2, 3, 4, 5, 6, 7, 8])
    
    st.update(0, 10)
    st.update(3, 40)
    st.update(7, 80)
    
    expected_sum = 10 + 2 + 3 + 40 + 5 + 6 + 7 + 80
    assert st.query(0, 7) == expected_sum
    print(f"    Total sum: {st.query(0, 7)} ✓")
    
    # Test 2: Partial range queries after updates
    print("\n[2] Partial ranges after updates")
    assert st.query(0, 3) == 10 + 2 + 3 + 40
    assert st.query(4, 7) == 5 + 6 + 7 + 80
    print("    Partial ranges correct ✓")
    
    # Test 3: Min tree with updates
    print("\n[3] Min tree with updates")
    st_min = SegmentTree([5, 2, 8, 1, 9], min, float('inf'))
    assert st_min.query(0, 4) == 1
    
    st_min.update(3, 10)  # Change 1 to 10
    assert st_min.query(0, 4) == 2  # New min is 2
    print(f"    New min after update: {st_min.query(0, 4)} ✓")
    
    # Test 4: Stress test with many updates
    print("\n[4] Stress test (1000 updates + queries)")
    import random
    
    n = 1000
    arr = [random.randint(1, 100) for _ in range(n)]
    st = SegmentTree(arr)
    
    for _ in range(1000):
        # Random update
        idx = random.randint(0, n - 1)
        val = random.randint(1, 100)
        arr[idx] = val
        st.update(idx, val)
        
        # Random query
        L = random.randint(0, n - 1)
        R = random.randint(L, n - 1)
        
        expected = sum(arr[L:R+1])
        actual = st.query(L, R)
        
        assert expected == actual, f"Mismatch at [{L},{R}]"
    
    print("    1000 random operations passed ✓")
    
    # Test 5: Edge cases
    print("\n[5] Edge cases")
    
    # Single element
    st_single = SegmentTree([42])
    st_single.update(0, 100)
    assert st_single.query(0, 0) == 100
    print("    Single element update ✓")
    
    # Empty tree
    st_empty = SegmentTree([])
    assert st_empty.query(0, 0) == 0
    print("    Empty tree handled ✓")
    
    print("\n" + "=" * 60)
    print("ALL TESTS PASSED!")
    print("=" * 60)
 
 
if __name__ == "__main__":
    run_comprehensive_tests()

Summary: Mastering Point Updates

We've covered the update operation in complete detail. Here are the essential insights:

Key Takeaways

•Path-Based Updates — Only nodes on the path from the target leaf to the root need updating—all O(log n) of them.
•Bottom-Up Propagation — After updating the leaf, recalculate each ancestor as we return from the recursive calls.
•Update Variants — Set (absolute), add (delta), and multiply (scale) updates all follow the same structure.
•Operation Agnostic — The same algorithm works for sum, min, max, GCD, etc.—just use the appropriate combine function.
•O(log n) Time — We visit one node per level, and there are O(log n) levels.
•Invariant Maintenance — After update completes, the tree is in a valid state—as if it had been rebuilt from scratch.

What's Next:

Now that we've mastered point updates, the final piece is understanding time complexity in detail. The next page provides a comprehensive complexity analysis covering build time, query time, update time, and how segment trees compare to alternative data structures.

Page Complete

You now understand how to update segment trees efficiently. The ability to modify elements in O(log n) time while maintaining correct query results is what makes segment trees truly powerful for dynamic data. Next, we'll consolidate with a complete complexity analysis.