Chapter 13 · Advanced Data Structures

Segment Tree & Fenwick Tree

Answer "sum (or min) of this range?" and "change one element" in O(log n) each. The segment tree splits a query into a few whole blocks; the Fenwick tree, also called a Binary Indexed Tree (BIT), jumps through its blocks by flipping the lowest 1-bit of the index.

How to read this

Segment tree

  • Each box is a node that stores the sum (or min) of the slice [l..r] written above it. The root covers everything; leaves cover one element. Node k's children are 2k and 2k + 1.
  • During a query every visited node gets a verdict: green = fully inside, use its stored value whole; yellow = partial overlap, split and recurse; gray = outside, contributes the identity (0 for sum, ∞ for min). The green nodes at the end are the decomposition of the range.
  • The small orange number under a node is what that call returned.
  • An update walks down to one leaf (blue), rewrites it (red), then recombines every ancestor on the way back up.

Fenwick tree (BIT)

  • Each horizontal bar is one cell T[j]. It stores the sum of A(j − LowBit(j) .. j], so its length is the lowest 1-bit of j: odd j cover 1 cell, j = 4 covers 4, j = 8 covers 8.
  • The register under the array shows the bit trick: i, its two's complement −i, and i AND −i, which isolates the lowest 1-bit (highlighted).
  • Prefix subtracts that bit (i ← i − LowBit(i)) and walks left; update adds it (i ← i + LowBit(i)) and climbs to bigger blocks. Either way at most ⌊log₂ n⌋ + 1 steps.

Try this

  1. Segment tree on 2, 5, 1, 4, 9, 3, query [1..4]. The decomposition is [1..1], [2..2], [3..4] → 5 + 1 + 13 = 19, and only 9 nodes are visited.
  2. Switch to range min and query [1..4] again: same nodes, answer 1. Only the combine rule and the identity (∞ instead of 0) changed.
  3. Load 16 numbers and query [1..14]. Count the yellow (partial) nodes on each level: never more than 2, which is why a query is O(log n).
  4. Fenwick on 3, 2, −1, 6, 5, 4, −3, 3: Prefix(6) visits 6 → 4 → 0 and returns 9 + 10 = 19. Prefix(7) visits 7 → 6 → 4 → 0: three steps because 7 = 111 has three 1-bits.
  5. Fenwick: add 2 to A[3]. It touches T[3], T[4], T[8] (3 → 4 → 8 → 16 > n). Then Prefix(6) is 21.

Go deeper

📖 Lesson 13 · Segment tree 📖 Lesson 13 · Fenwick tree 🏟️ Chapter 13 Arena 🧩 Arena: fenwick-range-sum 🧩 Arena: segment-tree-range-min 🎮 Prefix sums (patterns) 🎮 Union-Find 🎮 Heap lab