Segment Trees, Fenwick & String Matching

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

1. ◆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).

   #1
2. ↯use it when

   No updates → prefix sums. Point updates + sums → Fenwick. Min/max/gcd, or adds over a range → segment tree (+ lazy).

   #2
3. { }template

   Fenwick (1-based): update climbs i += i & -i, query strips i -= i & -i. Range sum = prefix(r + 1) - prefix(l).

   #3
4. { }template

   Segment-tree query: no overlap → identity, full overlap → tree[node], partial → both children (2*node, 2*node+1). Allocate 4 * n.

   #4
5. { }template

   KMP: mismatch → j = lps[j - 1] (repeat); match → j++; j == m → match at i - m + 1. The text index i never moves back.

   #5
6. O( )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.

   #6
7. !trap

   Fenwick index 0 never moves (0 & -0 == 0) — stay 1-based. update sets a value: add val - nums[i], not val.

   #7
8. !trap

   Equal hashes are not equal strings: verify the characters, use long, and add MOD back after subtracting.

   #8
9. ↯use it when

   "How many smaller/greater values before or after i?" → compress values to ranks, walk once, count ranks with a Fenwick tree.

   #9
10. ✦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.

    #10

Shaky on a card? Open the chapter or flip its recall cards.