How It Works

This chapter builds a segment tree for the array a = [5, 3, 7, 9, 6, 4, 1, 2] and traces, step by step, how a range-sum query and a point update move through it. It then shows the iterative bottom-up variant and the idea behind lazy propagation for range updates.

Step 1: build the tree

The most common layout numbers nodes from 1 and gives node k the children 2k and 2k+1. Elements go into the leaves, and each parent stores the sum of its two children.

                 [0,8) 37
           /                  \
      [0,4) 24              [4,8) 13
      /      \              /      \
  [0,2) 8  [2,4) 16    [4,6) 10  [6,8) 3
   /  \     /  \        /  \      /  \
  5    3   7    9      6    4    1    2

There are 2n - 1 nodes and each one is computed once, so building takes O(n).

Step 2: query the range [2, 6)

We want a[2] + a[3] + a[4] + a[5]. Starting at the root, every node falls into one of three cases:

• The node's range does not overlap the query: return the identity, 0.
• The node's range lies completely inside the query: return the stored value.
• The ranges partly overlap: recurse into both children and add the results.

The answer is 26, and indeed 7 + 9 + 6 + 4 = 26. The query was covered by exactly two nodes, [2,4) and [4,6). On each level at most two nodes are "partial" and recurse further, so the number of visited nodes is O(log n).

Step 3: point update a[3] = 0

When a[3] changes from 9 to 0, fix the leaf [3,4) and recompute only its ancestors:

• [3,4): 9 becomes 0
• [2,4): 16 becomes 7 + 0 = 7
• [0,4): 24 becomes 8 + 7 = 15
• [0,8): 37 becomes 15 + 13 = 28

Only one leaf-to-root path changed: log2 8 + 1 = 4 nodes. Translating the three steps directly into recursive functions gives:

a = [5, 3, 7, 9, 6, 4, 1, 2]
n = len(a)
tree = [0] * (4 * n)

def build(node, lo, hi):
    if hi - lo == 1:
        tree[node] = a[lo]
        return
    mid = (lo + hi) // 2
    build(2 * node, lo, mid)
    build(2 * node + 1, mid, hi)
    tree[node] = tree[2 * node] + tree[2 * node + 1]

def query(node, lo, hi, l, r):
    if r <= lo or hi <= l:          # disjoint
        return 0
    if l <= lo and hi <= r:         # fully inside
        return tree[node]
    mid = (lo + hi) // 2            # partial overlap
    return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid, hi, l, r)

def update(node, lo, hi, i, value):
    if hi - lo == 1:
        tree[node] = value
        return
    mid = (lo + hi) // 2
    if i < mid:
        update(2 * node, lo, mid, i, value)
    else:
        update(2 * node + 1, mid, hi, i, value)
    tree[node] = tree[2 * node] + tree[2 * node + 1]

build(1, 0, n)
print(query(1, 0, n, 2, 6))   # 26
update(1, 0, n, 3, 0)
print(query(1, 0, n, 2, 6))   # 17

When n is not a power of two the tree becomes slightly lopsided and node numbers can exceed 2n, which is why the array is allocated with 4n slots.

The iterative bottom-up variant

The same work can be done without recursion. Put the elements in the second half of an array of size 2n, tree[n..2n), then compute tree[i] = tree[2i] + tree[2i+1] for i from n-1 down to 1. A query starts at the two ends lo = l + n and hi = r + n and climbs toward the root, adding only the nodes that sit on the boundary.

a = [5, 3, 7, 9, 6, 4, 1, 2]
n = len(a)
tree = [0] * n + a
for i in range(n - 1, 0, -1):
    tree[i] = tree[2 * i] + tree[2 * i + 1]

lo, hi, total = 2 + n, 6 + n, 0
while lo < hi:
    if lo & 1:                 # lo is a right child: take it, step right
        total += tree[lo]; lo += 1
    if hi & 1:                 # hi is a right child: take its left neighbor
        hi -= 1; total += tree[hi]
    print(f"lo={lo} hi={hi} total={total}")
    lo //= 2; hi //= 2
print(total)                   # 26

Range updates and lazy propagation

Handling "add 2 to every element of [0,4)" as four point updates costs O(k log n). Lazy propagation instead stops at nodes that are fully covered by the update and leaves them a note (the lazy value) saying "my children still owe +2".

add +2 to [0,4)
  [0,4): 24 + 2 * 4 = 32, lazy = 2   (children untouched)
  [0,8): 32 + 13 = 45

later, a query for [2,4) passes through [0,4) and pushes the note down
  [0,2): 8 + 2 * 2 = 12, lazy = 2
  [2,4): 16 + 2 * 2 = 20, lazy = 2
  [0,4): lazy = 0

A note is only resolved when some operation needs to descend below that node, so range updates also finish in O(log n). The full code appears in the practice problems chapter.

Summary

A segment tree stores the sum of every halved range; queries descend according to overlap, and updates recompute a single leaf-to-root path. The iterative variant does the same job with a 2n array and short loops, while lazy propagation defers range updates and pushes them to children only when needed.