How It Works

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.