Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Segment trees: combine child ranges after updates

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A segment tree stores an aggregate for each interval in a binary partition of an array. For sums, each internal node equals the sum of its children. A point update changes one leaf and recomputes its ancestors; a half-open range query combines only nodes intersecting the requested interval. Both cost O(log n), while building takes O(n) and storage is O(n). The same shape can support other associative aggregates with an identity value, but the combine operation and update contract must match. Lazy propagation is a separate extension for efficient updates over whole ranges.

Operational case

A maintenance dashboard starts with job counts 47, 31, 26, and 58. The range [1, 4) totals 115. A corrected day index 2 becomes 29, so the range is 118. The point-update method replaces the old value; unlike the Fenwick example's add method, it does not accept a delta. The root stores the total for all days, but a caller may query only the bounded window. If two writers update different days concurrently, the tree still needs synchronization to prevent lost parent recomputations.

Working Python program

python
job_counts = [47, 31, 26, 58]
leaf_count = len(job_counts)
tree = [0] * (2 * leaf_count)
tree[leaf_count:] = job_counts
for position in range(leaf_count - 1, 0, -1):
    tree[position] = tree[2 * position] + tree[2 * position + 1]

def range_sum(left, right):
    left += leaf_count
    right += leaf_count
    total = 0
    while left < right:
        if left & 1:
            total += tree[left]
            left += 1
        if right & 1:
            right -= 1
            total += tree[right]
        left //= 2
        right //= 2
    return total

def replace(day_index, new_count):
    position = leaf_count + day_index
    tree[position] = new_count
    while position > 1:
        position //= 2
        tree[position] = tree[2 * position] + tree[2 * position + 1]

print(range_sum(1, 4))
replace(2, 29)
print(range_sum(1, 4))

Output

Output
115
118

Time, space, and tradeoff

The iterative array uses 2n slots for n positive-length inputs and builds in O(n) time. Queries and point replacements touch O(log n) nodes. A production wrapper must reject empty input or define its identity-only tree and validate 0 <= left <= right <= n. This storage layout works for a non-power-of-two n because parent sums still cover the corresponding leaves under the iterative query algorithm. Choose a simpler prefix array when data is immutable; a more complex tree is justified by repeated updates.

Common Mistakes

  • Do not confuse replace with add-delta semantics.
  • Do not query outside the half-open array bounds.
  • Do not claim this point-update tree already supports range updates.

Connected lessons

Sparse coordinate segment tree: allocate only visited paths extends this operation contract.

Lazy segment tree: add to a range and query its minimum adds a related operation contract.

Square-root blocks: update one capacity and sum a range extends this range-query decision.

Segment tree beats: cap a range while retaining its sum adds a distinct structure contract to compare.

Range XOR bases: merge linear spans in a segment tree examines a related structure with a different operation boundary.

Affine lazy segment trees: compose range calibration before summing examines a related structure with a different operation boundary.

Maximum-subarray segment trees: preserve the crossing burst examines a related structure with a different operation boundary.

Editable substring fingerprints: join hashes in a segment tree examines a related structure with a different operation boundary.

data structures
range-query-structures
Storage details