Lesson 41 · Hard mode

Range queries with updates — O(log n)

📖 Walk me through it — plain English

Say you have an array of numbers and you keep asking two kinds of questions: "what's the answer over this stretch of the array — say the max (or sum) of positions 1 through 2?" and "actually, change the number at position 3 to something new." A range query means combining the values across a contiguous slice. An update means changing one value. If you recompute the slice from scratch every time, each query costs O(n) — you touch every element. A segment tree lets you do both the query and the update in O(log n), meaning the work only grows like the number of times you can halve n, not like n itself.

The trick: precompute the answer for chunks of the array and store them in a tree. The bottom row (the leaves) holds your actual values. Each parent node stores the combined answer for its two children — here we use op = max, so a parent holds the max of its two kids. The root at the top holds the answer for the whole array. To answer a query you only need to read a handful of these precomputed chunks instead of every element.

Analogy: imagine a company org chart where every manager keeps a sticky note showing the highest salary anywhere under them. The CEO's note covers everyone. If you want the top salary in one department, you read a few managers' notes instead of polling every employee. When one person gets a raise, only their chain of managers up to the CEO need to update their notes — that chain is short, about log n people deep.

This code stores the whole tree flat in one array t of size 2n. The leaves (your data) sit at indices n through 2n-1. For any node at index i, its two children are at 2*i and 2*i+1, and its parent is at i // 2 (integer divide). No pointers needed — the math gives you the family tree.

Let's build a tree for data = [3, 5, 9, 1] with op = max, so n = 4 and t has 8 slots. We fill the leaves at indices 4..7, then walk parents upward, each one taking the max of its two children.

Step 1 · Copy the data into the leaf slots t[4..7]. Indices 0..3 of the array become tree indices 4..7. Slots 1, 2, 3 (the internal nodes) are still empty.

index: 0 1 2 3 4 5 6 7

Step 2 · Fill internal nodes from index n-1=3 down to 1. Node 3 = max(t[6], t[7]) = max(9, 1) = 9. Node 2 = max(t[4], t[5]) = max(3, 5) = 5.

index: 0 1 2 3 4 5 6 7

Step 3 · Finish at the root, node 1 = max(t[2], t[3]) = max(5, 9) = 9. The root now holds the max of the entire array. The tree is built.

index: 0 1 2 3 4 5 6 7

Step 4 · Now query the max over array positions [1, 2] (the values 5 and 9; answer should be 9). The code sets l = 1 + n = 5 and r = 2 + n + 1 = 7. Note r is one-past-the-end, so the half-open window we scan is leaves [5, 7), i.e. indices 5 and 6 — exactly the two values we want.

l=5, r=7, res = -inf

Step 5 · Loop while l < r. l = 5 is odd (l & 1 is true), meaning leaf 5 is a right child not covered by its parent's range, so we fold it in: res = max(-inf, t[5]=5) = 5, then l becomes 6. r = 7 is also odd (r & 1 true), so step r down to 6 and fold leaf t[6]: res = max(5, t[6]=9) = 9. Now both pointers move up: l //= 2 → 3, r //= 2 → 3.

folded t[5]=5 then t[6]=9 · res = 9 · l=3, r=3

Step 6 · Now l = 3 and r = 3, so l < r is false and the loop stops. Return res = 9 — the max over positions [1, 2]. We touched only 2 nodes, not the whole array.

Why it's O(log n): the build touches each of the 2n nodes once, so building is O(n). For a query, the two pointers l and r start at the leaf row and climb one level per loop iteration (l //= 2, r //= 2). The tree has only about log n levels, and at each level we fold in at most one node on the left and one on the right, so a query touches O(log n) nodes. An update is the same idea in reverse: set the leaf, then walk up the parent chain recomputing each ancestor — again about log n steps. The op just has to be associative (grouping doesn't change the result, like max, min, sum, gcd, or XOR), so combining precomputed chunks gives the same answer as combining the raw elements.

Prefix sums give O(1) range queries but can't handle updates efficiently. Segment trees and Fenwick trees give O(log n) for both. Pick Fenwick for sum-like operations (simpler); segment tree for anything else.

Fenwick tree (BIT) — prefix sums with updates

class Fenwick:
    def __init__(self, n):
        self.t = [0] * (n + 1)   # 1-indexed

    def update(self, i, delta):
        i += 1
        while i < len(self.t):
            self.t[i] += delta
            i += i & -i                # add lowest set bit

    def prefix_sum(self, i):    # sum of [0..i] inclusive
        i += 1; s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i                # strip lowest set bit
        return s

    def range_sum(self, l, r):
        return self.prefix_sum(r) - (self.prefix_sum(l - 1) if l > 0 else 0)

Both update and query: O(log n). The bit-tricks (i & -i) traverse the implicit tree.

Segment tree — general associative op

class SegTree:
    def __init__(self, data, op=max, ident=float('-inf')):
        n = len(data)
        self.n = n; self.op = op; self.ident = ident
        self.t = [ident] * (2 * n)
        for i, v in enumerate(data):
            self.t[n + i] = v
        for i in range(n - 1, 0, -1):
            self.t[i] = op(self.t[2*i], self.t[2*i+1])

    def update(self, i, v):
        i += self.n
        self.t[i] = v
        while i > 1:
            i //= 2
            self.t[i] = self.op(self.t[2*i], self.t[2*i+1])

    def query(self, l, r):           # inclusive l, inclusive r
        res = self.ident
        l += self.n; r += self.n + 1
        while l < r:
            if l & 1: res = self.op(res, self.t[l]); l += 1
            if r & 1: r -= 1; res = self.op(res, self.t[r])
            l //= 2; r //= 2
        return res

Works for any associative op: max, min, sum, gcd, XOR. For range UPDATES (add 5 to all of [l..r]), add lazy propagation.

Range sum queries — prefix sums are the segment-tree warm-up:

→ Going deeper: Segment trees sometimes use bitmask DP — bitwise fluency from Bit manipulation helps. See Bit manipulation.

→ Going deeper: Segment trees complement interval DP on mutable arrays. See DP — interval, bitmask & tree.