Segment Tree

Why not brute force?

A naive range-sum query scans the whole range — O(n) per query. A segment tree precomputes sums over halves recursively, so any range query becomes O(log n). Each node stores the aggregate of a sub-range; leaves are single elements.

Build & query

Store the tree in an array of size 4n. build fills bottom-up, query recurses only into overlapping halves.

tree = [0] * (4 * n)

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

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

Output:

build(1, 0, n-1)
query(1, 0, n-1, 2, 5)  # sum of arr[2..5]

Point update

Updating one element only touches the O(log n) nodes on the path from root to that leaf, then fixes sums on the way back up.

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

When to reach for it

Use a segment tree when you need many range queries interleaved with updates — range-sum, range-min/max, or even range-GCD. If updates never happen, a simple prefix-sum array is O(1) per query and simpler.