Segment Trees, Fenwick & String Matching

Precompute a little structure once, then answer every query in O(log n) — or match a pattern without ever looking back.

advanced~90 min7 simulations7 problems

▶ guided lesson ⚡ 1-minute summary ↻ 15 recall cards

before this: Hashing · Tree Recursion · Bits · Arrays & Strings

Section

01 · why it exists

Why this exists, and the weight it carries

since1989 · 1994

Fenwick tree (binary indexed tree)

Boris Ryabko (1989, 1992); Peter M. Fenwick, University of Auckland (1994)

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 solvedKeep cumulative frequencies correct while they change on every symbol: update and prefix-sum both in O(log n), in a single array.

its jobs today

Adaptive compression, the job it was built for: an arithmetic coder updates one symbol's count and reads a running total for every symbol it encodes.
Live counts and ranks: "how many orders so far cost less than ₹500?" or a player's rank while scores keep changing — a Fenwick tree over compressed values answers each in O(log n).
Counting inversions — how far a list is from sorted, e.g. how much two rankings disagree — in O(n log n).

the weight it carries

Illustrative: 1 lakh (10⁵) values and 1 lakh calls, half updates and half range sums. Plain array: each sum may read 10⁵ values → 5·10⁴ × 10⁵ = 5·10⁹ steps. Prefix-sum array: each update rewrites up to 10⁵ prefixes → also 5·10⁹. Fenwick: ⌊log₂ 10⁵⌋ + 1 = 17 steps per loop → 5·10⁴ × 17 + 5·10⁴ × 2 × 17 = 2,550,000 — about 2,000× less, in one int[100001].

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.

when · why · how

when: Point updates mixed with prefix or range sums and counts; "how many smaller/greater values have I seen?" (with coordinate compression).
why: O(log n) per update and per query in about 10 lines and one O(n) array, versus O(1)/O(n) for a prefix array and O(n)/O(1) for a plain array. Ranges need an invertible operation (sum, count, XOR).
how: int[] tree = new int[n + 1]; update: for (int i = idx + 1; i <= n; i += i & -i) tree[i] += delta; prefix: for (int i = idx + 1; i > 0; i -= i & -i) sum += tree[i];

since1977

Segment tree

Jon Louis Bentley (Carnegie Mellon University)

In 1977 Victor Klee studied how fast you can compute the total length covered by n intervals on a line. The same year Jon Bentley solved the 2D version — the area of a union of n rectangles — in O(n log n): sweep a vertical line across the plane and keep the line's covered length in a new structure, the segment tree. He wrote it up in unpublished 1977 notes at Carnegie Mellon, and the segment tree became a standard tool of computational geometry. The array-based version that interviews use for range sums and minimums grew out of the same idea; we found no single paper that introduced it.

the problem it solvedAnswer questions about many overlapping intervals while they change — first covered length and area, later sums and minimums over any range — in O(log n) per step.

its jobs today

Computational geometry, its first job: sweep a line across rectangles (overlapping windows on a screen, map tiles) and keep the covered length to get the total area.
Range min/max/sum over a changing series: the cheapest fare between day 3 and day 20 while prices update, or peak CPU inside a time window on a monitoring chart.
One template for many questions: swap the combine function and its identity (sum/0, min/+∞, max/−∞, gcd/0) and the same code answers a different query.

the weight it carries

Illustrative: 10 lakh (10⁶) readings and 1 lakh (10⁵) range-minimum queries mixed with updates. Scanning each range: up to 10⁶ reads per query → up to 10¹¹. Segment tree: ⌈log₂ 10⁶⌉ = 20 levels × at most 4 nodes per level → ≤ 80 nodes per query → 8·10⁶ in total. Memory: a 4n int[] = 4·10⁶ ints ≈ 16 MB.

without it

Range min/max with updates would need an O(n) scan per query — 10⁶ steps instead of about 80 at this size.

when · why · how

when: Range min/max/gcd (anything a Fenwick tree can't subtract) with updates, or range updates mixed with range queries.
why: O(n) build and O(log n) per query and update for any associative combine; it costs about 4n memory and more code than a Fenwick tree.
how: int[] tree = new int[4 * n]; children of node are 2 * node and 2 * node + 1; query: no overlap → identity, full overlap → tree[node], partial → combine both children.

since?

Lazy propagation (range updates on a segment tree)

We found no single paper that introduced lazy tags on segment trees. Postponing work on a subtree until someone needs it is standard textbook and programming-contest practice, so we credit no inventor.

its jobs today

Bookings along a route: a train seat booked from stop 3 to stop 9 occupies legs 3..8. "Add 1 to legs 3..8" and "what is the busiest leg in 2..7?" are a range add and a range max.
Bulk edits on a timeline: shift every value in a date range (a price change, a time-zone fix) and still answer range sums and maxima fast.

the weight it carries

Illustrative: n = 1 lakh (10⁵) values and 1 lakh operations "add v to every element of [l, r]". Without lazy tags a full-range add rewrites all 2n − 1 ≈ 2·10⁵ nodes → up to 2·10¹⁰ node writes. With lazy tags: at most about 4 nodes per level × ⌈log₂ 10⁵⌉ = 17 levels = 68 per operation → about 6.8·10⁶.

without it

A range update would touch every element of the range — O(n) each — so bulk updates over big ranges would crawl.

when · why · how

when: "Add v to (or set) every element in [l, r]" mixed with range sum/min/max queries.
why: Range update and range query both become O(log n), at the price of a second 4n array and a careful push before every descent.
how: apply(node) adds v × length to tree[node] and v to lazy[node]; push(node) applies lazy[node] to both children and clears it; call push before visiting children in both add and query.

since1969–70 (found) · 1977 (published)

KMP and the prefix function (lps)

James H. Morris Jr., Donald E. Knuth and Vaughan R. Pratt

Summer 1969: James Morris was writing a text editor for the CDC 6400 and wanted a search that never backs up in the text file. His routine was hard for others to follow — months later, other programmers' "fixes" had turned it into "a shambles", as the 1977 paper recalls. Early 1970: Donald Knuth reached the same idea from automata theory (Stephen Cook's theorem), and Vaughan Pratt made its running time independent of the alphabet size. Morris recognised it as his own; Morris and Pratt wrote a 1970 report, and all three published it together in 1977.

the problem it solvedFind a pattern in text in O(n + m) time while reading the text strictly left to right, never going back.

its jobs today

Find without going back, the job Morris built it for: scan a file or a network stream once, left to right, even when you can't re-read what already went past.
Its many-pattern cousin, Aho–Corasick (1975), adds KMP-style failure links to a trie, so one pass finds thousands of keywords — the core of multi-keyword search and signature scanning.
String structure: borders and periods — is a log line or a DNA read one block repeated? what is the longest prefix that is also a suffix?

the weight it carries

Illustrative: search a 10 lakh-character (about 1 MB) log for a 1,000-character pattern, worst case (text "aaa…a", pattern "aa…ab"). Naive: (10⁶ − 10³ + 1) × 10³ ≈ 10⁹ comparisons. KMP: at most 2 × 10⁶ for the scan plus 2 × 10³ for the lps table ≈ 2,002,000 — about 500× fewer, with a 1,000-int table.

without it

Worst-case search would be O(n·m), and stream scanners would have to buffer and re-read old input.

when · why · how

when: Pattern search with a guaranteed linear bound; the longest prefix that is also a suffix; periods and repetitions; glued-string tricks.
why: O(n + m) worst case with O(m) extra space and no hashing risk; the price is a subtle table you must build correctly.
how: Build lps with len = lps[len - 1] on a mismatch and len++ on a match; search with the same loop over the text: j = lps[j - 1] on a mismatch, j == m → match at i - m + 1.

since1997 (popularised)

Z-function (Z-algorithm)

Dan Gusfield, UC Davis — Algorithms on Strings, Trees, and Sequences

Dan Gusfield's 1997 textbook Algorithms on Strings, Trees, and Sequences opens with "fundamental preprocessing". For every position i it computes Zᵢ, the length of the longest substring starting at i that matches a prefix of the string — all of them in linear time, using a box [l, r]. Written for computer science and computational biology, the book made Z-values a standard first linear-time matching algorithm. The idea is older than the book; we could not confirm who first wrote it down, so we credit Gusfield only as its popularizer.

the problem it solvedCompare every position of a string with the string's own start in O(n) total — which turns pattern search into one pass over pattern + '#' + text.

its jobs today

Pattern search by gluing: z on pattern + '#' + text marks every match in O(n + m), with no failure table to reason about.
"How far does each position agree with the start?" in one pass — periods, repeated blocks and many contest string problems reduce to it.
Exact matching in computational biology, the audience of Gusfield's book: DNA and protein strings are long, so linear time matters.

the weight it carries

Illustrative: the same 10 lakh-character log and 1,000-character pattern. Z on the glued string (1,001,001 characters) does at most about 2 × 1,001,001 ≈ 2·10⁶ comparisons — like KMP — but stores 1,001,001 ints (≈ 4 MB), where KMP's lps needs only 1,000 (≈ 4 KB).

without it

You would reach for KMP's subtler failure table, or a quadratic "compare from the start at every i" loop.

when · why · how

when: Pattern search where you can glue strings, "how much of the prefix matches at each position", periods and repeats.
why: O(n + m) worst case and often easier to get right than lps; it needs O(n + m) memory for the glued string and the z array.
how: if (i < r) z[i] = Math.min(r - i, z[i - l]); while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++; if (i + z[i] > r) { l = i; r = i + z[i]; }

since1987

Rabin–Karp rolling hash

Richard M. Karp and Michael O. Rabin

In March 1987 Richard Karp and Michael Rabin published "Efficient randomized pattern-matching algorithms" in the IBM Journal of Research and Development. Their idea: replace a long string by a short fingerprint — a number computed from its characters — and compare fingerprints instead of strings. A window's fingerprint can be updated as the window slides by one character, so the search needs only a fixed amount of memory. The 2003 winnowing paper calls it apparently the earliest form of fingerprinting based on k-grams — the idea behind modern copy detection.

the problem it solvedCompare many substrings, or find a pattern, with O(1) work per position instead of O(m), using very little memory.

its jobs today

File sync: rsync slides a rolling checksum over a file to find blocks the other side already has, so only the changed parts travel over the network.
Plagiarism and duplicate detection: hash every k-character window of documents or code and compare fingerprints (MOSS uses this winnowing idea).
Substring equality in O(1) after O(n) prefix hashes — the engine of "binary search on the length + hashing" problems like Longest Duplicate Substring.

the weight it carries

Illustrative: Longest Duplicate Substring on 30,000 characters, checking one length L = 10,000. Real substrings in a HashSet: (30,000 − 10,000 + 1) × 10,000 ≈ 2·10⁸ characters copied and hashed. Rolling hash: 10,000 steps for the first window + 20,000 O(1) slides = 30,000 — about 6,700× less; the binary search needs only ⌈log₂ 30,000⌉ = 15 such lengths.

without it

Every substring comparison would cost O(length), and sync tools would have to compare blocks byte by byte at every offset.

when · why · how

when: Many same-length substring comparisons, longest duplicate or common substring with binary search, or many patterns of one length.
why: O(1) per slide, so O(n + m) expected; collisions make the worst case O(n·m), so always verify on equal hashes (or use two moduli).
how: long arithmetic, MOD = 1_000_000_007L, BASE = 131; slide with h = (h - c * high % MOD + MOD) % MOD; h = (h * BASE + next) % MOD; and confirm a hit with regionMatches.

02 · plain english

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.

03 · remember

What you must know

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.
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.
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.
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.
Coordinate compression + Fenwick turns "how many earlier/later values are smaller?" into prefix-count queries over ranks — the engine behind counting inversions.
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).
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).
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.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Prefix sums recap

One O(n) pass, then any range is a single subtraction.

loading simulation…

javajava.util.*

1class NumArray {2    private final int[] prefix; // prefix[i] = nums[0] + ... + nums[i-1]3 4    public NumArray(int[] nums) {5        prefix = new int[nums.length + 1]; // prefix[0] = 0 (the empty sum)6        for (int i = 0; i < nums.length; i++)7            prefix[i + 1] = prefix[i] + nums[i];8    }9 10    public int sumRange(int left, int right) {11        return prefix[right + 1] - prefix[left]; // all up to right, minus all before left12    }13}

sim

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.

loading simulation…

javajava.util.*

1class NumArray {2    private final int[] nums; // current values, so "set" can become "add delta"3    private final int[] tree; // 1-indexed Fenwick tree (BIT)4 5    public NumArray(int[] nums) {6        this.nums = nums.clone();7        tree = new int[nums.length + 1];8        for (int i = 0; i < nums.length; i++) add(i + 1, nums[i]);9    }10 11    public void update(int index, int val) {12        int delta = val - nums[index];13        nums[index] = val;14        add(index + 1, delta);15    }16 17    public int sumRange(int left, int right) {18        return prefix(right + 1) - prefix(left);19    }20 21    private void add(int i, int delta) {22        for (; i < tree.length; i += i & -i) // climb to the next node that covers i23            tree[i] += delta;24    }25 26    private int prefix(int i) { // sum of the first i values27        int sum = 0;28        for (; i > 0; i -= i & -i) // strip the lowest set bit29            sum += tree[i];30        return sum;31    }32}

sim

Segment tree in 3D

Built bottom-up, then a query stops at green nodes (fully inside) and grey nodes (fully outside).

loading simulation…

javajava.util.*

1class NumArray {2    private final int n;3    private final int[] tree; // tree[node] = sum of its segment; children are 2*node, 2*node+14 5    public NumArray(int[] nums) {6        n = nums.length;7        tree = new int[4 * Math.max(1, n)];8        if (n > 0) build(nums, 1, 0, n - 1);9    }10 11    private void build(int[] nums, int node, int lo, int hi) {12        if (lo == hi) { tree[node] = nums[lo]; return; }13        int mid = (lo + hi) >>> 1;14        build(nums, 2 * node, lo, mid);15        build(nums, 2 * node + 1, mid + 1, hi);16        tree[node] = tree[2 * node] + tree[2 * node + 1];17    }18 19    public void update(int index, int val) {20        update(1, 0, n - 1, index, val);21    }22 23    private void update(int node, int lo, int hi, int index, int val) {24        if (lo == hi) { tree[node] = val; return; }25        int mid = (lo + hi) >>> 1;26        if (index <= mid) update(2 * node, lo, mid, index, val);27        else update(2 * node + 1, mid + 1, hi, index, val);28        tree[node] = tree[2 * node] + tree[2 * node + 1]; // re-sum on the way back up29    }30 31    public int sumRange(int left, int right) {32        return query(1, 0, n - 1, left, right);33    }34 35    private int query(int node, int lo, int hi, int left, int right) {36        if (right < lo || hi < left) return 0;            // no overlap37        if (left <= lo && hi <= right) return tree[node]; // full overlap38        int mid = (lo + hi) >>> 1;                        // partial: ask both children39        return query(2 * node, lo, mid, left, right) + query(2 * node + 1, mid + 1, hi, left, right);40    }41}

sim

Lazy propagation: add to a range now, pay the children later

A range add stops at fully covered nodes and leaves an IOU. The IOU moves down only when a later add or query must look inside.

loading simulation…

javajava.util.*

1class LazySegmentTree {2    private final int n;3    private final long[] tree; // tree[node] = sum of the node's segment4    private final long[] lazy; // lazy[node] = an add still owed to both children5 6    LazySegmentTree(int n) {7        this.n = n;8        tree = new long[4 * Math.max(1, n)];9        lazy = new long[4 * Math.max(1, n)];10    }11 12    void rangeAdd(int left, int right, long val) { add(1, 0, n - 1, left, right, val); }13 14    long rangeSum(int left, int right) { return query(1, 0, n - 1, left, right); }15 16    private void apply(int node, int lo, int hi, long val) {17        tree[node] += val * (hi - lo + 1); // every element in [lo, hi] grows by val18        lazy[node] += val;                 // an IOU: the children still owe this add19    }20 21    private void push(int node, int lo, int hi) {22        if (lazy[node] == 0) return;23        int mid = (lo + hi) >>> 1;24        apply(2 * node, lo, mid, lazy[node]);         // pay the IOU to both children25        apply(2 * node + 1, mid + 1, hi, lazy[node]);26        lazy[node] = 0;27    }28 29    private void add(int node, int lo, int hi, int left, int right, long val) {30        if (right < lo || hi < left) return;                                  // no overlap31        if (left <= lo && hi <= right) { apply(node, lo, hi, val); return; } // full overlap: stop, be lazy32        push(node, lo, hi);                                                   // partial: settle the IOU first33        int mid = (lo + hi) >>> 1;34        add(2 * node, lo, mid, left, right, val);35        add(2 * node + 1, mid + 1, hi, left, right, val);36        tree[node] = tree[2 * node] + tree[2 * node + 1];                     // re-sum on the way up37    }38 39    private long query(int node, int lo, int hi, int left, int right) {40        if (right < lo || hi < left) return 0;41        if (left <= lo && hi <= right) return tree[node]; // already includes every add above it42        push(node, lo, hi);                               // children must be up to date before we read them43        int mid = (lo + hi) >>> 1;44        return query(2 * node, lo, mid, left, right) + query(2 * node + 1, mid + 1, hi, left, right);45    }46}

sim

KMP prefix function (lps)

The matching prefix and suffix are highlighted. On a mismatch, len falls back through shorter borders.

loading simulation…

javajava.util.*

1class Solution {2    public String longestPrefix(String s) {3        int n = s.length();4        int[] lps = new int[n]; // lps[i] = longest proper prefix of s[0..i] that is also its suffix5        for (int i = 1, len = 0; i < n; i++) {6            while (len > 0 && s.charAt(i) != s.charAt(len))7                len = lps[len - 1];                  // shrink to the next shorter border8            if (s.charAt(i) == s.charAt(len)) len++; // the border grows by one9            lps[i] = len;10        }11        return s.substring(0, lps[n - 1]);12    }13}

sim

KMP search — the pattern slides, i never goes back

The pattern row slides under the text by its own lps table.

loading simulation…

javajava.util.*

1class Solution {2    public int strStr(String haystack, String needle) {3        int m = needle.length();4        if (m == 0) return 0;5        int[] lps = prefixFunction(needle); // lps[j] = longest proper border of needle[0..j]6        for (int i = 0, j = 0; i < haystack.length(); i++) { // i never moves backwards7            while (j > 0 && haystack.charAt(i) != needle.charAt(j))8                j = lps[j - 1];                              // fall back, keep what still matches9            if (haystack.charAt(i) == needle.charAt(j)) j++;10            if (j == m) return i - m + 1;11        }12        return -1;13    }14 15    private int[] prefixFunction(String p) {16        int[] lps = new int[p.length()];17        for (int i = 1, len = 0; i < p.length(); i++) {18            while (len > 0 && p.charAt(i) != p.charAt(len)) len = lps[len - 1];19            if (p.charAt(i) == p.charAt(len)) len++;20            lps[i] = len;21        }22        return lps;23    }24}

sim

Rabin–Karp rolling hash

Drop the left char, add the right char: the window hash updates in O(1).

loading simulation…

javajava.util.*

1class Solution {2    private static final long MOD = 1_000_000_007L, BASE = 131;3 4    public int strStr(String haystack, String needle) {5        int n = haystack.length(), m = needle.length();6        if (m > n) return -1;7        long target = 0, window = 0, high = 1; // high = BASE^(m-1) mod MOD8        for (int i = 0; i < m; i++) {9            target = (target * BASE + needle.charAt(i)) % MOD;10            window = (window * BASE + haystack.charAt(i)) % MOD;11            if (i > 0) high = high * BASE % MOD;12        }13        for (int i = 0; ; i++) {14            if (window == target && haystack.startsWith(needle, i)) return i; // verify: hashes can collide15            if (i + m >= n) return -1;16            window = (window - haystack.charAt(i) * high % MOD + MOD) % MOD; // drop the left char17            window = (window * BASE + haystack.charAt(i + m)) % MOD;         // add the right char18        }19    }20}

05 · cost

Time & space, explained

Range-sum structures (n = array length)
	Build	Point update	Range sum	Space	why
Plain array, loop per query	O(n)	O(1)	O(n)	O(n)	Updates are a single write, but every query walks the whole range.
Prefix-sum array	O(n)	O(n)	O(1)	O(n)	One subtraction per query, but changing nums[i] shifts every prefix after i.
Sqrt decomposition	O(n)	O(1)	O(√n)	O(n)	√n chunks of √n values: a query sums ≤ √n chunks plus ≤ 2√n loose values.
Fenwick tree (BIT)	O(n log n) or O(n)	O(log n)	O(log n)	O(n)	Each loop adds or strips one bit of i, so it runs at most ⌊log₂ n⌋+1 times. A smarter build pushes each node to its parent once → O(n).
Segment tree	O(n)	O(log n)	O(log n)	O(n) (4n array)	2n−1 nodes built once. A query visits at most 4 nodes per level across ~log₂ n levels.
Segment tree + lazy propagation	O(n)	O(log n) per range add	O(log n)	O(n)	A range add stops at O(log n) fully covered nodes and parks the rest in lazy[] until someone looks deeper.

String matching (text length n, pattern length m)
	Preprocess	Search	Extra space	why
Naive (try every start)	—	O(n·m) worst	O(1)	Text "aaaa…a" with pattern "aa…ab" re-compares almost all m characters at each of n starts.
KMP	O(m)	O(n)	O(m)	The text pointer only moves forward; each fallback undoes an earlier step, so total work ≤ 2n.
Z-algorithm on pattern#text	—	O(n + m)	O(n + m)	The right edge r of the Z-box only moves right; every comparison either moves r or ends a position.
Rabin–Karp	O(m)	O(n + m) expected, O(n·m) worst	O(1)	O(1) per slide; characters are only compared on hash equality, which is rare unless you're unlucky (or the input is adversarial).
`String.indexOf` (JDK)	—	O(n·m) worst	O(1)	The JDK uses a straightforward (heavily optimised) scan, not KMP — great in practice, quadratic in theory.

06 · java

Raw vs Collections Framework

Range sums: a hand-rolled prefix array vs the library

javaprefix array (exclusive, long)java.util.*

1class PrefixRaw {2    /** prefix[i] = a[0] + ... + a[i-1]; long avoids overflow when many ints add up. */3    static long[] prefixSums(int[] a) {4        long[] prefix = new long[a.length + 1];5        for (int i = 0; i < a.length; i++) prefix[i + 1] = prefix[i] + a[i];6        return prefix;7    }8 9    /** Sum of a[left..right], inclusive, in O(1). */10    static long rangeSum(long[] prefix, int left, int right) {11        return prefix[right + 1] - prefix[left];12    }13}

javaArrays.parallelPrefixjava.util.*

1class PrefixLibrary {2    /** Inclusive running sums in place: out[i] = a[0] + ... + a[i]. */3    static long[] runningSums(int[] a) {4        long[] out = Arrays.stream(a).asLongStream().toArray(); // widen to long first5        Arrays.parallelPrefix(out, Long::sum);                     // library prefix scan6        return out;7    }8}

The extra leading 0 (prefix[0] = 0) removes every if (left == 0) special case.
Use long for prefix sums: 10⁵ values of 10⁹ overflow int long before you notice.
Arrays.parallelPrefix(arr, Long::sum) computes inclusive running sums in place. Handy, but interviewers usually want the 2-line loop.

Fenwick tree — the JDK has no equivalent

javareusable Fenwick (0-based API)java.util.*

1class Fenwick {2    private final long[] tree; // 1-indexed internally; callers use 0-based indices3 4    Fenwick(int n) {5        tree = new long[n + 1];6    }7 8    /** O(n) build: push each node's total to its parent once. */9    Fenwick(int[] nums) {10        this(nums.length);11        for (int i = 1; i <= nums.length; i++) {12            tree[i] += nums[i - 1];13            int parent = i + (i & -i);14            if (parent < tree.length) tree[parent] += tree[i];15        }16    }17 18    void add(int index, long delta) {           // nums[index] += delta19        for (int i = index + 1; i < tree.length; i += i & -i) tree[i] += delta;20    }21 22    long prefixSum(int index) {                 // nums[0] + ... + nums[index]23        long sum = 0;24        for (int i = index + 1; i > 0; i -= i & -i) sum += tree[i];25        return sum;26    }27 28    long rangeSum(int left, int right) {29        return prefixSum(right) - (left == 0 ? 0 : prefixSum(left - 1));30    }31}

There is no Fenwick or segment tree in java.util. You write them yourself — so practice until the ~15 lines are automatic.
TreeMap.headMap(k).size() looks like a rank query but is linear in the number of keys below k: the sub-map view counts by iterating. A Fenwick tree over compressed values does it in O(log n).
Keep the tree 1-indexed inside (i & -i is 0 at index 0, which would loop forever) and expose 0-based methods.
Integer.lowestOneBit(i) is the readable name for i & -i.

Lazy propagation: range add + range sum

javalazy segment treejava.util.*

1class LazySegmentTree {2    private final int n;3    private final long[] tree; // tree[node] = sum of the node's segment4    private final long[] lazy; // lazy[node] = an add still owed to both children5 6    LazySegmentTree(int n) {7        this.n = n;8        tree = new long[4 * Math.max(1, n)];9        lazy = new long[4 * Math.max(1, n)];10    }11 12    void rangeAdd(int left, int right, long val) { add(1, 0, n - 1, left, right, val); }13 14    long rangeSum(int left, int right) { return query(1, 0, n - 1, left, right); }15 16    private void apply(int node, int lo, int hi, long val) {17        tree[node] += val * (hi - lo + 1); // every element in [lo, hi] grows by val18        lazy[node] += val;                 // an IOU: the children still owe this add19    }20 21    private void push(int node, int lo, int hi) {22        if (lazy[node] == 0) return;23        int mid = (lo + hi) >>> 1;24        apply(2 * node, lo, mid, lazy[node]);         // pay the IOU to both children25        apply(2 * node + 1, mid + 1, hi, lazy[node]);26        lazy[node] = 0;27    }28 29    private void add(int node, int lo, int hi, int left, int right, long val) {30        if (right < lo || hi < left) return;                                  // no overlap31        if (left <= lo && hi <= right) { apply(node, lo, hi, val); return; } // full overlap: stop, be lazy32        push(node, lo, hi);                                                   // partial: settle the IOU first33        int mid = (lo + hi) >>> 1;34        add(2 * node, lo, mid, left, right, val);35        add(2 * node + 1, mid + 1, hi, left, right, val);36        tree[node] = tree[2 * node] + tree[2 * node + 1];                     // re-sum on the way up37    }38 39    private long query(int node, int lo, int hi, int left, int right) {40        if (right < lo || hi < left) return 0;41        if (left <= lo && hi <= right) return tree[node]; // already includes every add above it42        push(node, lo, hi);                               // children must be up to date before we read them43        int mid = (lo + hi) >>> 1;44        return query(2 * node, lo, mid, left, right) + query(2 * node + 1, mid + 1, hi, left, right);45    }46}

apply updates a node and writes the IOU (lazy[node]); push pays the IOU to both children just before you visit them.
A node's tree value is always correct for its own segment; only its descendants may be behind. That's why a fully covered node can answer a query without pushing.
Allocate 4 * n: a recursive segment tree on n leaves can use indices up to just under 4n.
Swap + for Math.min / Math.max (and the identity 0 for ±∞) to get range-min / range-max trees. For range add + range max, apply adds val to the node's max (not val × length).

String search: KMP by hand vs `String` methods

javaprefix functionjava.util.*

1class PrefixFunction {2    /** lps[i] = length of the longest proper prefix of p[0..i] that is also a suffix of it. */3    static int[] prefixFunction(String p) {4        int[] lps = new int[p.length()];5        for (int i = 1, len = 0; i < p.length(); i++) {6            while (len > 0 && p.charAt(i) != p.charAt(len)) len = lps[len - 1];7            if (p.charAt(i) == p.charAt(len)) len++;8            lps[i] = len;9        }10        return lps;11    }12}

javaindexOf / contains / regionMatchesjava.util.*

1class LibrarySearch {2    static List<Integer> allMatches(String text, String pattern) {3        List<Integer> starts = new ArrayList<>();4        for (int i = text.indexOf(pattern); i >= 0; i = text.indexOf(pattern, i + 1))5            starts.add(i);                         // overlapping matches included6        return starts;7    }8 9    static boolean demo() {10        String t = "abracadabra";11        return t.contains("cad")                   // true12                && t.indexOf("abra") == 0          // first match13                && t.lastIndexOf("abra") == 7      // last match14                && t.startsWith("cad", 4)          // match at a given offset15                && t.regionMatches(0, "xabrax", 1, 4); // compare slices without substring()16    }17}

In a real codebase use indexOf / contains — they're fast in practice. In an interview, the algorithm is usually the question.
s.startsWith(p, offset) and regionMatches compare in place — no substring() copies (each copy is O(length)).
String.hashCode() is itself a polynomial hash (base 31) — the same idea as Rabin–Karp, but it can't be rolled.

Z-function

javaZ arrayjava.util.*

1class ZFunction {2    /** z[i] = length of the longest common prefix of s and s.substring(i); z[0] = 0 by convention. */3    static int[] zFunction(String s) {4        int n = s.length();5        int[] z = new int[n];6        for (int i = 1, l = 0, r = 0; i < n; i++) {      // [l, r) is the rightmost match box7            if (i < r) z[i] = Math.min(r - i, z[i - l]);8            while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;9            if (i + z[i] > r) { l = i; r = i + z[i]; }10        }11        return z;12    }13}

Convention: z[0] = 0 (some books use n). Never rely on z[0].
Z and the prefix function carry the same information and can be converted into each other — learn one deeply, recognise the other.

Java API you will actually use
call	does	cost
`Arrays.parallelPrefix(long[] a, Long::sum)`	In-place inclusive running sums	O(n)
`i & -i / Integer.lowestOneBit(i)`	Lowest set bit — the Fenwick step size	O(1)
`Arrays.stream(a).distinct().sorted().toArray()`	Sorted distinct values for coordinate compression	O(n log n)
`Arrays.binarySearch(sorted, x)`	Rank of x after compression (index, ≥ 0 if present)	O(log n)
`s.indexOf(p) / s.indexOf(p, from)`	First match (from an offset); −1 if none	O(n·m) worst
`s.contains(p)`	indexOf(p) >= 0	O(n·m) worst
`s.startsWith(p, offset)`	Does p occur exactly at offset? (no copy)	O(m)
`a.regionMatches(i, b, j, len)`	Compare two slices without substring()	O(len)
`new StringBuilder(s).reverse()`	Reversed copy (palindrome tricks)	O(n)

Range sums, array never changes

→ Prefix-sum array

O(1) per query, trivial code.

Point updates + prefix/range sums

→ Fenwick tree

O(log n) both ways, smallest code, tiny constant.

Range min/max/gcd, or anything Fenwick can't invert

→ Segment tree

Works for any associative combine; Fenwick needs subtraction to get ranges.

Add to a whole range + range sums

→ Segment tree with lazy propagation

O(log n) range updates (or two Fenwicks if you know the trick).

Count smaller / greater elements seen so far

→ Coordinate compression + Fenwick

Rank queries in O(log n); merge sort is the alternative.

Find a pattern in text, guaranteed linear

→ KMP (or Z on pattern#text)

O(n + m) worst case, no hashing risk.

Compare many substrings for equality fast

→ Rabin–Karp / prefix hashes

O(1) per substring after O(n) preprocessing; verify on equal hashes.

07 · recognise

Spot the pattern

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

Find a pattern in a string, or "longest prefix that is also a suffix"

KMP prefix function

Periodic / repeated strings, shortest palindrome by adding a prefix

Prefix function on a cleverly glued string (s + '#' + reverse(s))

"Longest duplicate substring", many substring equality checks

Binary search on length + Rabin–Karp hashing

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

Fenwick with index 0: 0 & -0 == 0, so i += i & -i never moves — infinite loop. Shift to 1-based.
Fenwick update that sets a value: the tree stores sums, so add the difference val − nums[i] and keep a copy of nums.
Segment tree array of size 2n for a recursive tree: indices can exceed it. Use 4n.
Forgetting push before recursing in a lazy tree — children read stale sums.
Rabin–Karp without verifying on equal hashes: collisions will eventually give a wrong answer.
Negative values after modular subtraction: in Java % keeps the sign, so add MOD before the final % MOD (or use Math.floorMod).
KMP: resetting j = 0 on a mismatch instead of j = lps[j−1] while i keeps moving forward — that is not even the naive algorithm (which would move back), and it misses matches that start inside the failed attempt, like "aab" in "aaab".
Using int for big prefix sums or hashes: hash * BASE overflows int instantly — use long.

tricks

Memorise the Fenwick pair as a rhyme: query strips (i -= i & -i), update climbs (i += i & -i).
Say the segment-tree query as three cases out loud: no overlap → 0, full overlap → node value, partial → ask both children.
For KMP, write the prefix-function loop first; search is the same loop run over the text.
Before reaching for these structures, ask: are there updates? If not, prefix sums are enough and the interviewer will prefer them.
When stuck on a string problem, try gluing strings together (p + '#' + t, s + s, s + '#' + reverse(s)) and running a prefix/Z function on the result.
Test with: one element, all equal values, negatives, an update to the same index twice, pattern longer than text, pattern equal to text.

09 · why & how

Questions you might be too shy to ask

Why does i & -i give the lowest set bit?

In two's complement, -i = ~i + 1. Flipping all bits then adding 1 turns the trailing zeros back to zeros and the lowest 1 back to 1, while every higher bit is the opposite of i. AND keeps only that one shared bit. Example: 12 = 1100, −12 = …0100, so 12 & −12 = 0100 = 4.

Which values does tree[i] actually hold? Show me one.

tree[i] is the sum of the last i & -i values ending at position i (1-based). tree[7]: 7 & −7 = 1, so just position 7. tree[6]: 6 & −6 = 2, so positions 5–6. tree[4]: positions 1–4. So prefix(7) = tree[7] + tree[6] + tree[4]: three blocks glued together, not seven values. With n = 8, an update at 5 climbs tree[5] → tree[6] → tree[8] (5 + 1 = 6, 6 + 2 = 8), exactly the blocks that contain position 5.

Why is the range sum prefix(right + 1) - prefix(left)? Where did the +1 come from?

prefix(i) means "the sum of the first i values", i.e. indices 0..i−1. Indices 0..right are the first right + 1 values. Subtract the first left values (0..left−1), and what's left is exactly left..right. Example: left = 2, right = 4 → prefix(5) − prefix(2) = (0..4) − (0..1) = 2..4.

Fenwick or segment tree — which should I learn first?

Learn Fenwick for sums: it's ~10 lines and hard to get wrong. Learn the segment tree next because it handles min/max/gcd and range updates. If an interviewer just says "range sum with updates", either is a great answer.

Why can't a Fenwick tree do range minimum?

A Fenwick tree answers prefix queries. A range sum is prefix(right + 1) − prefix(left), which needs subtraction to cut away the part before left. Min has no "un-min", so you can't cut that part away. A segment tree combines exact blocks of the range, so it never needs to undo anything.

What is coordinate compression and when do I need it?

Replace each value by its rank among the sorted distinct values (e.g. [100, −7, 100, 42] → [3, 1, 3, 2]). Do it when values are huge or negative but you only care about their order — it shrinks the Fenwick tree to n slots.

I'll never remember segment-tree code under pressure. What do I actually memorise?

Only three facts: children of node are 2*node and 2*node+1; allocate 4*n; and the query's three cases (no overlap → identity, full overlap → tree[node], partial → combine both children). Build and update follow from those. Write it once from these facts every few days and it stops being scary — bas itna yaad rakho.

In lps, why must the prefix be proper?

Proper means "not the whole string itself". Every string is its own prefix and its own suffix, so without that rule lps[i] would always be i + 1 and tell you nothing. For "abab" the proper answer is 2 ("ab" at the start and at the end): on a mismatch after "abab", KMP keeps those 2 matched letters and continues from there.

Why does KMP run in O(n) when there's a while loop inside a for loop?

j goes up by at most 1 per character of the text (n times in total), and every fallback makes j strictly smaller. You can't go down more than you went up, so all fallbacks together cost at most n. That's amortised analysis, same as ArrayList growth.

KMP or Z — which one should I learn?

Both are O(n + m). Learn the prefix function (KMP) deeply: it answers borders, periods and search, and its table is only O(m). Recognise Z as the friendlier alternative when you can glue pattern + '#' + text and memory isn't tight.

Why the '#' in pattern + '#' + text for the Z-algorithm?

It's a wall. '#' appears in neither string, so no match can run across it. Then no z[i] can be bigger than m, and z[i] == m means exactly "the whole pattern starts here". Without the wall, a match could run from the pattern part into the text and give fake answers. Pick any character the input never uses.

Is Rabin–Karp safe to use in an interview?

Yes, if you verify the characters whenever the hashes match. Then the answer is always correct; only the running time depends on luck. Say it out loud: "O(n + m) expected; worst case O(n·m) if many collisions." Use a large prime modulus (1e9+7) and long arithmetic.

Rabin–Karp uses BASE = 131 and MOD = 1_000_000_007. Can I pick any numbers?

Almost, with two rules. The base should be bigger than every character code (131 is above all ASCII codes), so different strings give different polynomials before the mod. The modulus should be a large prime, so hash values spread out and collisions stay rare. Keep everything in long: a hash below 10⁹ times 131 is about 1.3·10¹¹, too big for int but easy for long.

Do interviews really ask segment trees?

Less often than arrays, graphs or DP. Candidates do report them in some hard rounds and online assessments (community interview reports, not official lists), and 307 or 315 are reported as follow-ups. The same reports mention KMP-style string questions (28, 214, 459) more often than segment trees.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#307
Range Sum Query - Mutablemust-do
MediumAdobeBloombergGoogleAmazon
#315
Count of Smaller Numbers After Selfmust-do
HardGoogleBloombergMicrosoftAmazonMeta
#28
Find the Index of the First Occurrence in a Stringmust-do
EasyTCSBloombergMicrosoftGoogleAmazon+1
#459
Repeated Substring Pattern
EasyGoogleAmazonTCSBloombergMeta+1
#1392
Longest Happy Prefixmust-do
HardAppleAmazonGoogleMicrosoftMeta
#214
Shortest Palindrome
HardBloombergGoogleUberMicrosoftAmazon
#1044
Longest Duplicate Substring
HardByteDance / TikTokGoogleAmazonGoldman SachsMeta

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#303
Range Sum Query - Immutable
Easyin Hashing
The static baseline: prefix sums answer range sums in O(1). Fenwick and segment trees exist to keep that speed when values change.
#493
Reverse Pairs
Hardin Sorting
Count Smaller's twin: walk right to left and count with a Fenwick tree over ranks — or count during merge sort.

11 · revise

The whole chapter on one screen

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

what it is
Range queries: keep block sums so any range is a few blocks. Strings: never re-read matched text (KMP, Z), or compare cheap hashes first (Rabin–Karp).
use it when
No updates → prefix sums. Point updates + sums → Fenwick. Min/max/gcd, or adds over a range → segment tree (+ lazy).
template
Fenwick (1-based): update climbs i += i & -i, query strips i -= i & -i. Range sum = prefix(r + 1) - prefix(l).
template
Segment-tree query: no overlap → identity, full overlap → tree[node], partial → both children (2*node, 2*node+1). Allocate 4 * n.
template
KMP: mismatch → j = lps[j - 1] (repeat); match → j++; j == m → match at i - m + 1. The text index i never moves back.
cost
Fenwick and segment tree: O(log n) per update and query, O(n) memory. KMP and Z: O(n + m). Rabin–Karp: O(n + m) expected, O(n·m) worst.
trap
Fenwick index 0 never moves (0 & -0 == 0) — stay 1-based. update sets a value: add val - nums[i], not val.
trap
Equal hashes are not equal strings: verify the characters, use long, and add MOD back after subtracting.
use it when
"How many smaller/greater values before or after i?" → compress values to ranks, walk once, count ranks with a Fenwick tree.
pro tip
Stuck on a string problem? Glue strings — p + '#' + t, s + s, s + '#' + reverse(s) — and run the prefix or Z function on the result.

12 · recall

Flip, remember, repeat

card 1 / 15

recall

Fenwick tree: what does i & -i give, and which way does each loop move?

tap or Space to flip ↻

Question 1: Fenwick tree: what does i & -i give, and which way does each loop move?

13 · check yourself

Quick quiz

In a Fenwick tree, which indices does prefix(13) read? (13 = 1101₂)
Why can't you answer range-min queries with a plain Fenwick tree?
A segment tree query finds a node whose segment lies completely inside [left, right]. What does it do?
In a lazy segment tree, when must you call push(node)?
What is the lps (prefix function) array of "abab"?
KMP has a while loop inside a for loop. Why is the search still O(n)?
With the convention z[0] = 0, what is the Z array of "aabxaab"?
In Rabin–Karp, two windows have equal hashes. What must you do?
You need "add v to every element in [l, r]" and "sum of [l, r]", both 10⁵ times. Best tool?
Why glue s + '#' + reverse(s) in Shortest Palindrome?

0/0 correct · 10 left

14 · learn more