Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 63 ยท Data Structures in Contest Practice

Fenwick and Segment Trees for Contests

Write short iterative Fenwick and segment trees, count inversions, understand lazy propagation, and know when a sparse table is the better choice.

Prefix sums answer range questions instantly, but only while the array never changes. The moment a problem says "update position i, then ask about a range", you need a structure that supports both operations in O(log n). Two of them cover almost every contest problem of this kind: the Fenwick tree (also called a binary indexed tree) and the segment tree.

This lesson is about the contest versions: short, iterative, and easy to type from memory. If you want the theory and the recursive forms, read Fenwick Tree, Segment Trees and Sparse Table in the DSA tutorial.

Choosing the structure first

Ask three questions before you type anything:

  1. Does the data change between queries? If not, a prefix sum (sums) or a sparse table (min, max, gcd) is simpler and faster.
  2. What is the combine operation? Sum, count and xor can be undone (subtraction), so a Fenwick tree works. Min, max and gcd cannot be undone, so you need a segment tree.
  3. Are updates single points or whole ranges? Range updates with range queries need lazy propagation or a trick with two Fenwick trees.
flowchart TD
    A["Range query problem"] --> B{"Does the array change?"}
    B -- "No" --> C{"Sum-like?"}
    C -- "Yes" --> D["Prefix sums"]
    C -- "No (min, max, gcd)" --> E["Sparse table"]
    B -- "Yes" --> F{"Operation can be undone?"}
    F -- "Yes (sum, xor, count)" --> G["Fenwick tree"]
    F -- "No (min, max, gcd)" --> H["Segment tree"]

A quick decision tree for range-query problems.

The Fenwick tree

A Fenwick tree stores an array tree of size n + 1 where tree[i] holds the sum of a block of elements that ends at position i. The length of that block is the lowest set bit of i, which you get as i & -i. Positions are 1-based here, because index 0 would have a block of length zero.

Two loops do all the work:

  • Update walks upward: i += i & -i.
  • Prefix query walks downward: i -= i & -i.

Each loop runs at most about log2(n) times, because every step adds or clears one bit. A range sum is a difference of two prefixes, the same trick you know from prefix sums.

Python A Fenwick tree with a brute-force check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The printed tree array shows the block structure: tree[8] holds the whole sum, tree[4] holds positions 1 to 4, and every odd index holds just its own value.

Counting inversions with a Fenwick tree

A classic use is counting inversions: pairs i < j with a[i] > a[j]. Scan from left to right. For each value, count how many earlier values are larger, then record the value. If the Fenwick tree counts how many times each value has been seen, "earlier values larger than x" is seen_so_far - prefix(x).

Values can be huge, so first apply coordinate compression (see Sorting, Events and Sweeps): replace each value by its rank among the sorted distinct values.

Python Counting inversions in O(n log n)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The iterative segment tree

A segment tree handles any operation that is associative: combine(combine(a, b), c) == combine(a, combine(b, c)). The compact iterative version stores the tree in one array of size 2n. The leaves live at positions n to 2n - 1, and the parent of node i is i // 2. There is no recursion and no padding to a power of two.

  • Build: for i from n - 1 down to 1, set t[i] = combine(t[2*i], t[2*i + 1]).
  • Point update: set the leaf t[i + n], then walk up recomputing parents.
  • Query on the half-open range [l, r): move l and r up the tree together. If l is a right child, take t[l] and move on; if r is a right child, take t[r - 1].

That works for any n and for min, max, sum and gcd. If the operation is not commutative (for example string concatenation or matrix multiplication), keep a left result and a right result and combine them in order, as the code below does.

Python A generic iterative segment tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In Python, a segment tree with 10^5 to 2 * 10^5 operations is realistic, but the constant factor is large. Avoid passing combine as a function when speed matters: write the sum or min directly into the loops, and prefer a Fenwick tree whenever the operation allows it, because it does less work per step.

Range updates and lazy propagation

Suppose you must add a value to every element of a range and also ask for range sums. Updating each element costs O(n). Lazy propagation postpones the work: a node that is completely covered by an update stores a pending "add v to everything below me" tag and stops. When a later query or update must look inside that node, it first pushes the tag down to its two children, and only then continues.

You need to decide three things for each problem:

  • What the tag is (an addition, an assignment, a multiplier plus an addition).
  • How a tag changes the node's stored value (for a sum with +v: add v * length).
  • How two tags compose when a second update arrives before the first was pushed.

The recursive structure is the same every time, so many contestants keep one tested template and change only those three pieces. You rarely need to write lazy trees early in training, so treat this section as a map of where the technique lives.

For the common special case "range add, point query", a plain Fenwick tree over the difference array is enough: add v at l and -v at r + 1, and the value of a position is the prefix sum of the differences. A pair of Fenwick trees even handles "range add, range sum", but at that point most people switch to a lazy tree.

When a sparse table wins

If nothing changes, a sparse table answers range-minimum (or maximum, or gcd) queries in O(1) after O(n log n) preprocessing. The idea: table[k][i] stores the answer for the 2^k elements starting at i. For a query [l, r) take k = floor(log2(r - l)) and combine the two overlapping blocks table[k][l] and table[k][r - 2^k]. Overlap is harmless for min, max and gcd because they are idempotent (min(x, x) = x). It is wrong for sums.

Python A sparse table for range minimum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Contest advice

  • Fix an index convention (1-based Fenwick, 0-based half-open segment tree) and never mix them in one program.
  • Test with a brute force on tiny random arrays, as every example here does. See Stress Testing with a Brute Force.
  • Offline problems are often easier: sort queries, sweep, and use a Fenwick tree as the "active set" counter.
  • In Python, memory for 2 * 10^5 integers is fine, but 4 * n recursive trees with tuples can be slow. Prefer flat lists.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does a Fenwick tree use 1-based indexes?

    The block length of position i is i & -i. For i = 0 that is 0, so the update loop would never move. Starting at 1 avoids this.
  2. 2. Which operation cannot be answered by a plain Fenwick prefix-query trick?

    A range is the difference of two prefixes, which requires an inverse operation. Sum, xor and counts have one; minimum does not, so use a segment tree.
  3. 3. In the iterative segment tree, where are the leaves stored?

    The array has size 2n. Leaves occupy the second half, and the parent of node i is i // 2.
  4. 4. Why is a sparse table wrong for range sums?

    Min, max and gcd are idempotent, so overlap does no harm. Sums are not, so the overlapping trick would give a wrong answer.

Summary

  • Use prefix sums for static sums, a sparse table for static min or max, a Fenwick tree for changing sums, counts and xors, and a segment tree for changing min, max or gcd.
  • A Fenwick update walks up with i += i & -i; a query walks down with i -= i & -i.
  • Counting inversions is a Fenwick tree over compressed values.
  • The iterative segment tree uses an array of size 2n with leaves at n to 2n - 1 and half-open queries.
  • Lazy propagation stores pending tags on fully covered nodes and pushes them down when needed.
  • Always compare your structure with a brute force on small random inputs.

Next: Graph Problems: Modeling and Traversal