Overview

Prefix sums answer range-sum queries instantly — until a single element changes and the whole prefix array must be rebuilt. Range-query trees fix this by storing partial aggregates over blocks of the array so that both a point update and a range query touch only O(log n) blocks.

A Fenwick tree (binary indexed tree) is a remarkably short structure for prefix sums with updates, built entirely on the lowest-set-bit trick. A segment tree is more general: each node stores an aggregate (sum, min, max, gcd) for a segment, and with lazy propagation it also supports updating whole ranges at once. These appear in harder interview rounds and constantly in competitive programming.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Fenwick: update / prefix queryO(log n)
Segment tree: buildO(n)
Segment tree: update / queryO(log n)
Range update with lazy propagationO(log n)

Patterns to recognise

Point update, range query

Use it for: Range sum query – mutable.

Fenwick tree for sums; segment tree for min/max.

Counting with a BIT

Use it for: Count of smaller numbers after self, reverse pairs, inversions.

Compress values, scan the array, query how many earlier values fall in a range, then add the current one.

Range update

Use it for: Booking counts, falling squares.

Segment tree with lazy tags, or a Fenwick tree over a difference array.

Code template

Fenwick tree (binary indexed tree)
class Fenwick:
    def __init__(self, n):
        self.tree = [0] * (n + 1)

    def add(self, i, delta):            # a[i] += delta, 0-indexed
        i += 1
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & -i

    def prefix(self, i):                # sum of a[0:i]
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total

    def range_sum(self, left, right):   # sum of a[left..right]
        return self.prefix(right + 1) - self.prefix(left)

Common mistakes

  • Fenwick trees are 1-indexed internally; mixing conventions causes infinite loops at index 0.
  • Segment-tree arrays need about 4n slots when built recursively.
  • For an update that sets a value (rather than adds), add the difference from the old value.

Quick check

Three questions on Range Queries. Get all three right to earn +15 XP.

  1. A segment tree answers a range query and applies a point update in:

  2. When is a plain prefix-sum array a better choice than a segment tree?

  3. In a Fenwick tree, what does i & (-i) give you?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Range Queries?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor