Range Queries: Prefix Sums, Fenwick Trees, Segment Trees and Beyond

Many problems ask for an aggregate over a range of an array (a sum, minimum or maximum), often combined with updates to the array. The right structure depends on how many queries and updates you expect. This chapter gives you a ladder: prefix sums when nothing changes, a Fenwick tree when values change and you need sums, a segment tree for general range queries and range updates, and sparse tables for fast static minimum queries. It ends with ideas that appear at the hard end of interviews: sweep lines, difference arrays and amortised tricks.

1. Choosing the structure

Interviews usually stop at prefix sums and a Fenwick or segment tree. Know the ladder, and pick the simplest rung that fits.

2. Prefix sums and difference arrays

Prefix sums answer static range sums in $O(1)$ after an $O(n)$ build, as in the arrays chapter.

The difference array is the mirror image: to add v to every element in [l, r], do diff[l] += v and diff[r + 1] -= v. A single pass of prefix sums over diff reconstructs the final array. It turns many range updates into $O(1)$ each.

def apply_range_updates(n, updates):
    """updates: (left, right, value) triples; returns the final array of length n starting from zeros."""
    diff = [0] * (n + 1)
    for l, r, v in updates:
        diff[l] += v
        diff[r + 1] -= v
    result, running = [], 0
    for i in range(n):
        running += diff[i]
        result.append(running)
    return result

assert apply_range_updates(5, [(1, 3, 2), (2, 4, 3), (0, 2, -2)]) == [-2, 0, 3, 5, 3]

This solves car pooling, corporate flight bookings, range addition and meeting rooms in $O(n+q)$ instead of $O(nq)$. A 2D version works on grids.

3. Fenwick tree (binary indexed tree)

A Fenwick tree stores partial sums so that both point update and prefix sum run in $O(\log n)$, with very little code. Each index i is responsible for a block of the array whose length is the lowest set bit of i.

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

    def update(self, i, delta):                    # add delta at position i (1-indexed)
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i                            # move to the next block that covers i

    def prefix_sum(self, i):                       # sum of positions 1..i
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i                            # strip the lowest set bit
        return total

    def range_sum(self, left, right):              # inclusive, 1-indexed
        return self.prefix_sum(right) - self.prefix_sum(left - 1)

ft = FenwickTree(8)
for i, v in enumerate([3, 2, -1, 6, 5, 4, -3, 3], start=1):
    ft.update(i, v)
assert ft.prefix_sum(4) == 10
assert ft.range_sum(3, 6) == 14
ft.update(4, 5)                                    # nums[4] becomes 11
assert ft.range_sum(3, 6) == 19

Why it works. i & -i isolates the lowest set bit. The update walks up, adding the lowest bit each time, visiting every block that contains i. The query walks down, removing the lowest bit each time, summing disjoint blocks that together cover 1..i. Both take at most $\log n$ steps because each step changes a bit.

Range sum query with point updates is exactly this. A common refinement is building the tree in $O(n)$ instead of $n$ updates. Use it to count inversions and count smaller numbers after self: process values in order and use the tree as a frequency table over compressed ranks.

def count_smaller_after_self(nums):
    ranks = {v: i + 1 for i, v in enumerate(sorted(set(nums)))}       # coordinate compression
    ft = FenwickTree(len(ranks))
    result = []
    for x in reversed(nums):
        r = ranks[x]
        result.append(ft.prefix_sum(r - 1))                            # how many smaller values seen so far (to the right)
        ft.update(r, 1)
    return result[::-1]

assert count_smaller_after_self([5, 2, 6, 1]) == [2, 1, 1, 0]
assert count_smaller_after_self([-1]) == [0]

Coordinate compression (mapping large or negative values to ranks 1..k) is a standard preparation step for Fenwick and segment trees.

4. Segment tree

A segment tree is a binary tree in which each node stores an aggregate (sum, minimum, maximum, gcd, any associative merge) of a range of the array. The leaves are the elements. A query decomposes the range into at most $O(\log n)$ nodes, and an update changes one leaf and recomputes its ancestors.

An iterative bottom-up implementation with an array of size 2n is short and fast:

class SegmentTree:
    def __init__(self, nums, merge=lambda a, b: a + b, identity=0):
        self.n = len(nums)
        self.merge, self.identity = merge, identity
        self.tree = [identity] * self.n + list(nums)
        for i in range(self.n - 1, 0, -1):                    # build parents from children
            self.tree[i] = merge(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, value):                                # set nums[i] = value (0-indexed)
        i += self.n
        self.tree[i] = value
        while i > 1:
            i //= 2
            self.tree[i] = self.merge(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, left, right):                              # inclusive range [left, right]
        result_left, result_right = self.identity, self.identity
        l, r = left + self.n, right + self.n + 1
        while l < r:
            if l & 1:
                result_left = self.merge(result_left, self.tree[l]); l += 1
            if r & 1:
                r -= 1; result_right = self.merge(self.tree[r], result_right)
            l //= 2; r //= 2
        return self.merge(result_left, result_right)

nums = [1, 3, 5, 7, 9, 11]
st = SegmentTree(nums)
assert st.query(1, 3) == 15 and st.query(0, 5) == 36
st.update(1, 10)
assert st.query(1, 3) == 22

mn = SegmentTree([5, 2, 8, 1, 9], merge=min, identity=float("inf"))
assert mn.query(0, 2) == 2 and mn.query(2, 4) == 1
mn.update(3, 10)
assert mn.query(2, 4) == 8

Changing the merge function and identity gives range minimum, maximum, gcd, or any associative operation. Fenwick trees only handle operations with an inverse (like sum), which is why segment trees are more general.

Time $O(n)$ to build, $O(\log n)$ per query or update. Space $O(n)$.

Lazy propagation (range updates)

If you must add a value to a whole range and still query ranges quickly, store pending updates ("lazy" tags) at nodes and push them down only when needed. This is a harder topic and rarely required in interviews, but you should know the idea: an update on a range marks the O(log n) covering nodes and defers the work to their children until a later query or update visits them.

5. Sparse table: static range minimum in $O(1)$

If the array never changes, a sparse table precomputes the minimum over every range of length $2^k$ starting at each index. A query for any range takes the minimum of two overlapping precomputed blocks, giving $O(1)$ per query after $O(n\log n)$ preprocessing. It works for idempotent operations (min, max, gcd), where overlap does no harm.

class SparseTable:
    def __init__(self, nums):
        self.table = [list(nums)]
        j = 1
        while (1 << j) <= len(nums):
            prev = self.table[-1]
            half = 1 << (j - 1)
            self.table.append([min(prev[i], prev[i + half]) for i in range(len(nums) - (1 << j) + 1)])
            j += 1

    def query_min(self, left, right):                  # inclusive
        k = (right - left + 1).bit_length() - 1        # the largest power of two that fits
        return min(self.table[k][left], self.table[k][right - (1 << k) + 1])

sp = SparseTable([4, 6, 1, 5, 7, 3])
assert sp.query_min(0, 5) == 1
assert sp.query_min(3, 5) == 3
assert sp.query_min(1, 1) == 6

It is the standard tool for range minimum queries that underlie lowest-common-ancestor algorithms.

6. Sweep line

A sweep line processes events sorted by position, updating a running state. It turns geometric or interval problems into one sorted pass.

Skyline problem (outline of overlapping buildings), maximum overlap of intervals, the number of airplanes in the sky and meeting rooms are sweeps. The simplest form turns each interval into two events, +1 at the start and -1 at the end, sorts them, and tracks a running count.

def max_overlap(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
    events.sort(key=lambda e: (e[0], e[1]))           # at the same time, ends (-1) come before starts (+1)
    current = best = 0
    for _, delta in events:
        current += delta
        best = max(best, current)
    return best

assert max_overlap([(1, 4), (2, 5), (7, 9)]) == 2
assert max_overlap([(1, 3), (3, 5)]) == 1            # touching intervals do not overlap
assert max_overlap([]) == 0

Sorting ends before starts at equal times implements "half-open" intervals. Whether touching intervals overlap is a requirement to confirm.

7. Other advanced structures worth knowing by name

You will rarely implement these in an interview, but recognising them shows breadth.

• Monotonic queue / deque for sliding window extremes (stacks chapter).
• Union-find with rank for dynamic connectivity (graphs chapter).
• Balanced binary search trees (AVL, red-black) and skip lists for ordered maps with $O(\log n)$ operations. Python has no built-in, but the sortedcontainers package provides a SortedList. In an interview, if you need an ordered structure with insertion, say "I would use a balanced tree or a sorted container", and implement only if asked.
• Bloom filters: a probabilistic set with no false negatives and a tunable false positive rate, in very little memory.
• LRU and LFU caches (design chapter).
• Tries and suffix arrays or automata for string problems.
• Heaps with lazy deletion for sliding window medians.
• Sqrt decomposition: split the array into blocks of size $\sqrt{n}$, giving $O(\sqrt{n})$ queries and updates with simple code, as a fallback when a segment tree is overkill.

import bisect

class SortedListSimple:
    """A minimal ordered multiset: O(log n) search, O(n) insert, adequate for a few thousand items."""
    def __init__(self):
        self.a = []

    def add(self, x):
        bisect.insort(self.a, x)

    def remove(self, x):
        i = bisect.bisect_left(self.a, x)
        if i < len(self.a) and self.a[i] == x:
            self.a.pop(i)

    def count_less_than(self, x):
        return bisect.bisect_left(self.a, x)

sl = SortedListSimple()
for v in (5, 1, 3, 3):
    sl.add(v)
assert sl.count_less_than(4) == 3
sl.remove(3)
assert sl.count_less_than(4) == 2

8. Recognising range-query problems

Ask: "Do I repeatedly need an aggregate over a contiguous range, and does the array change?"

• Many queries, no changes: prefix sums or a sparse table.
• Many range updates, one final read: a difference array.
• Interleaved point updates and range sums: Fenwick tree.
• Interleaved updates and min or max queries: segment tree.
• "How many elements before me are smaller/larger" over an arrival order: Fenwick tree with coordinate compression.
• Counting something along a timeline of events: sweep line.

9. Common mistakes

• Off-by-one with 1-indexed Fenwick trees. Keep one convention. Index 0 is not usable in a Fenwick tree.
• Using a Fenwick tree for min or max with updates, where it does not work directly.
• Forgetting coordinate compression when values are large or negative.
• Allocating a segment tree of the wrong size. The iterative form needs 2n, and the recursive form up to 4n.
• Mixing inclusive and exclusive ranges in queries.
• Sorting events incorrectly at ties in a sweep line.
• Using a plain list as a priority or ordered structure with $O(n)$ insertions on large inputs.
• Reaching for a segment tree when prefix sums suffice. The simplest correct structure is the best answer.

10. Practice set

1. Range sum query immutable and 2D immutable (prefix sums).
2. Range sum query mutable (Fenwick tree and segment tree).
3. Count of smaller numbers after self, count of range sum, reverse pairs.
4. Corporate flight bookings, car pooling, range addition (difference array).
5. The skyline problem, my calendar I, II and III (sweep and interval structures).
6. Sliding window maximum (monotonic deque), range minimum query (sparse table).
7. Number of longest increasing subsequences, Russian doll envelopes (Fenwick or segment tree).
8. Falling squares, rectangle area II (coordinate compression and sweep).
9. Online stock span, data stream as disjoint intervals.
10. Longest increasing subsequence in $O(n\log n)$ using a Fenwick tree for maximum.