Advanced Data Structures

Segment Trees & Fenwick Trees

Range queries with point updates in O(log n).

Hard, optional depth, about 120 minutes to practise.

1Understand

The idea

When an array changes and you also need range sums (or minimums), precompute partial answers over blocks whose sizes are powers of two. Both an update and a range query touch only O(log n) blocks. A Fenwick tree does this for sums in a few lines; a segment tree handles any associative operation.

Intuition

When an array changes and you also need range aggregates, precompute partial answers over blocks whose sizes are powers of two. Both an update and a range query touch O(log n) blocks.

A Fenwick (BIT) handles prefix sums with very little code; a segment tree supports any associative operation (sum, min, gcd) and easy range updates with lazy propagation.

Prefer these over rebuilding a prefix array when the problem mixes updates and queries.

What you will be able to do

  • Implement a Fenwick tree
  • Map values to ranks (coordinate compression)

When to use it

  • Range sum / min with updates in between
  • Count smaller elements after self
  • Many queries on a changing array

2See it

Walkthrough

Fenwick range sum

a = [1, 3, 5, 7] (1-indexed BIT), prefix walks along lowbit.

1 / 4

i
1
3
5
7
0123

BIT[i] stores sum of a responsible range ending at i. Build by point-add each value.

def add(i, delta): ... i += lowbit(i)

Live template

Line 1 active

1def update(i, delta):
2 i += 1
3 while i <= n: tree[i] += delta; i += i & -i
4def query(i): # sum of a[0..i]
5 i += 1; s = 0
6 while i > 0: s += tree[i]; i -= i & -i
7 return s

Complexity: time O(log n) per op, space O(n)

Build O(n), query/update O(log n). Recomputing sums each time is O(n) per query. Prefix arrays are O(1) query but O(n) update, wrong when both operations appear. Fenwick is less flexible than a segment tree but faster to implement for sums.

Read the walkthrough as text

Fenwick range sum. Array [1,3,5,7] (1-indexed tree).

  1. Build by updating each position's value into the BIT.
  2. Prefix sum to index 3: walk index 3 → 2 → 0, summing nodes, gets 1+3+5=9.
  3. Range sum [2,4] = prefix(4), prefix(1).
  4. Point update index 2 by +2: add 2 along 2 → 4 → ....

Segment tree stores a full binary tree over the array; query splits the range into O(log n) nodes.

3Recognise it

Kinds of problems (5)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Range sum with point updates

    Example. Sum on [l,r] with updates between queries.

    How. Fenwick tree on prefix sums; range sum = query(r)−query(l−1).

  • Range minimum / maximum

    Example. Segment tree for min on range with updates.

    How. Build tree; query merges min children; point update rewrites leaf upward.

  • Count inversions / smaller after self

    Example. Reverse pairs count.

    How. Fenwick on compressed ranks while scanning right to left.

  • Coordinate compression

    Example. Map large values to 0..k−1 for Fenwick.

    How. Sort unique values; rank[i] = index in sorted list.

  • Lazy propagation for range updates

    Example. Add v to entire segment [l,r].

    How. Segment tree with lazy tag push down on query/update path.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • 1-indexing

    Why it happens. Array is 0-indexed so Fenwick should match.

    How it fails. update(0, x) without i+=1, updates index 0 in tree which is unused slot.

    Fix. Internally use i+1 for user index i in update/query loops.

  • Static prefix sums

    Why it happens. Rebuild prefix array after each update is still O(n) per query total.

    How it fails. q updates each rebuild prefix, O(nq) instead of O(q log n).

    Fix. Point update Fenwick in O(log n); range sum from two queries.

  • Update vs set

    Why it happens. add(idx, newVal) feels like setting cell to newVal.

    How it fails. Set nums[i]=5 from old 3 with add(i,5), tree has 8 at i instead of 5.

    Fix. Point set: add(i, newVal - oldVal) or delta from current value.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons