← Range Queries & Strings · guided lesson
Segment Trees, Fenwick & String Matching
the story
Fenwick tree (binary indexed tree)
Every tool here exists because something was too slow or broke without it. Here is what.
Adaptive data compression (arithmetic coding) keeps a table of how often each symbol has appeared, and for every symbol it codes it must both update the table and read a running total. Boris Ryabko described this structure in 1989, in a paper on fast adaptive ("on-line") codes, with a further version in 1992. Peter Fenwick described it in 1994 as the "binary indexed tree": one array, where each operation's cost depends on the 1-bits of the index. His name stuck — today almost everyone calls it a Fenwick tree.
the problem it solved
Keep cumulative frequencies correct while they change on every symbol: update and prefix-sum both in O(log n), in a single array.
why it matters: without it
Every "sum or count so far, while values keep changing" question would cost O(n) on one side — reads or writes — and slow down as the data grows.
sources: P. M. Fenwick, A New Data Structure for Cumulative Frequency Tables, Software: Practice and Experience 24(3), 1994 ↗ · P. M. Fenwick, A New Data Structure for Cumulative Probability Tables, Tech. Report 88, University of Auckland (1993) ↗ · B. Ya. Ryabko, A fast on-line code, Doklady Akademii Nauk SSSR 306(3), 1989 (Math-Net.Ru) ↗ · Fenwick tree — history ↗
also in this chapter: Segment tree · Lazy propagation (range updates on a segment tree) · KMP and the prefix function (lps) · Z-function (Z-algorithm) · Rabin–Karp rolling hash
the idea
The idea in 30 seconds
Range queries: store sums of blocks of the array, so any range is glued together from a few blocks instead of n single values.
Fenwick tree and segment tree keep those blocks fresh after updates in O(log n), where a prefix-sum array would need O(n).
String matching: when a comparison fails, reuse what you already matched (KMP, Z) or compare cheap fingerprints first (Rabin–Karp) instead of starting over.
picture this
A server dashboard never adds up a month of raw request logs when you open it. It keeps per-hour, per-day and per-week rollups, so "requests from the 3rd to the 20th" is a couple of weekly totals plus a few daily ones. A late correction to one hour only fixes that hour, its day and its week. Fenwick and segment trees are exactly these rollups, packed into an array.
watch it
Prefix sums recap
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Prefix sums recap
One O(n) pass, then any range is a single subtraction.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Fenwick tree: climb on update, strip bits on query
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Fenwick tree: climb on update, strip bits on query
Each tree cell owns a block of nums (shown under it). Watch an update touch only log n cells.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 8
Read it once. Say it out loud once. Bas.
Prefix sums answer range sums in O(1): sum(l..r) = prefix[r+1] − prefix[l]. But one update forces O(n) rebuilding — fine only when the array never changes.
key idea 2 of 8
Read it once. Say it out loud once. Bas.
Fenwick tree (BIT): tree[i] holds the sum of the lowbit(i) = i & -i values ending at i (1-based). Query strips the lowest bit (i -= i & -i), update climbs (i += i & -i). Both O(log n), ~10 lines.
key idea 3 of 8
Read it once. Say it out loud once. Bas.
Segment tree: a binary tree where every node stores the answer for a segment. Any range splits into at most ~2 nodes per level, so query and update are O(log n). It works for any associative combine: sum, min, max, gcd.
key idea 4 of 8
Read it once. Say it out loud once. Bas.
Lazy propagation lets a segment tree add to a whole range in O(log n): stop at fully covered nodes and leave an IOU (lazy[node]) for the children.
key idea 5 of 8
Read it once. Say it out loud once. Bas.
Coordinate compression + Fenwick turns "how many earlier/later values are smaller?" into prefix-count queries over ranks — the engine behind counting inversions.
key idea 6 of 8
Read it once. Say it out loud once. Bas.
KMP prefix function: lps[i] = longest proper prefix of p[0..i] that is also its suffix. On a mismatch, jump to that border instead of restarting — the text pointer never moves back, so search is O(n + m).
key idea 7 of 8
Read it once. Say it out loud once. Bas.
Z-algorithm: z[i] = how far s[i..] matches the start of s. On pattern + '#' + text, any z[i] == m is a match. Also O(n + m).
key idea 8 of 8
Read it once. Say it out loud once. Bas.
Rabin–Karp: hash each window and slide the hash in O(1). Equal hashes must still be verified (collisions exist), so it's O(n + m) expected, O(n·m) worst case.
spot the pattern
When you see this, think this
Many range-sum queries, no updates
Prefix sums (Hashing & Prefix Sums chapter) — don't overbuild
Range queries mixed with point updates, n and q up to ~10⁵
Fenwick tree (sums) or segment tree (min/max/anything)
"Add v to every element in [l, r]" plus range queries
Lazy segment tree (or difference array if there are no queries in between)
"How many elements to the left/right are smaller/greater?", inversions, reverse pairs
Coordinate compression + Fenwick, or merge-sort counting
+3 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Fenwick with index 0:
0 & -0 == 0, soi += i & -inever moves — infinite loop. Shift to 1-based. - Fenwick
updatethat sets a value: the tree stores sums, so add the differenceval − nums[i]and keep a copy of nums.
quick check
One question. No pressure.
In a Fenwick tree, which indices does prefix(13) read? (13 = 1101₂)
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Range Sum Query - Mutable
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Fenwick tree: what does i & -i give, and which way does each loop move?
Question 1: Fenwick tree: what does i & -i give, and which way does each loop move?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.