Segment Tree & Fenwick Tree

Suppose you have an array and you keep asking "what is the sum of elements from index l to r?" — and between those questions the array keeps changing. A plain prefix-sum array answers each query in O(1), but every update forces you to rebuild it in O(n). A segment tree gives you both fast queries and fast updates: O(log n) each.

Intuition

Think of the array as a long shelf of books, split in half, then each half split in half again, all the way down to single books. At every split you write a sticky note with the total weight of everything below it. Now if someone asks for the weight of a middle stretch of the shelf, you do not weigh every book — you grab a handful of sticky notes that together cover exactly that stretch. Because the shelf halves each level, you only ever need about log n notes.

That is the whole trick: precompute partial sums in a tree so a query reads a logarithmic number of nodes instead of scanning the range.

Walk through it

The animation builds a sum segment tree over a = [1, 3, 5, 7]. First the leaves appear, each holding one element. Then each internal node lights up as the sum of its two children: [0..1] becomes 1 + 3 = 4, [2..3] becomes 5 + 7 = 12, and the root [0..3] becomes 4 + 12 = 16 — the total.

Then we answer sum(1..2). We descend from the root. A node that is fully inside [1..2] is taken whole (we read its stored value and stop). A node fully outside contributes 0. A node that partially overlaps is split and we recurse into both children. Watch the path: the query lands on leaf [1] = 3 and leaf [2] = 5, skips the two leaves that fall outside, and combines 3 + 5 = 8.

The code, line by line

def build(node, lo, hi):
    if lo == hi:                # leaf: one element
        tree[node] = a[lo]
        return
    mid = (lo + hi) // 2
    build(2 * node, lo, mid)        # left child
    build(2 * node + 1, mid + 1, hi)  # right child
    tree[node] = tree[2 * node] + tree[2 * node + 1]
 
def query(node, lo, hi, l, r):
    if r < lo or hi < l:        # no overlap
        return 0
    if l <= lo and hi <= r:     # node fully inside [l, r]
        return tree[node]
    mid = (lo + hi) // 2        # partial: split and recurse
    return (query(2 * node, lo, mid, l, r) +
            query(2 * node + 1, mid + 1, hi, l, r))

• tree is a flat array using the classic 1-based heap layout: the children of node k are 2*k and 2*k+1. The root is node 1.
• build fills the tree bottom-up. The base case (lo == hi) copies a single element into a leaf; every internal node is the sum of its two children (line 8). One pass touches each node once, so building is O(n).
• query has three cases. No overlap (line 11) returns the identity 0. Total overlap (line 13) returns the node's stored sum — this is where we prune and avoid descending further. Partial overlap splits at mid and recurses into both halves (lines 16–17), combining their results.
• A point update (not animated) is symmetric: change one leaf, then walk back up to the root re-summing each parent — also O(log n).

Complexity

The payoff is the comparison with a prefix-sum array: prefix sums query in O(1) but update in O(n) (you must rebuild the suffix). A segment tree balances both at O(log n), which wins decisively when queries and updates are interleaved.

When to use / pitfalls

Practice