Week 18 — Advanced Data Structures

Theme: The four advanced data structures that separate Senior from Staff: segment tree / Fenwick (BIT), KMP, rolling hash, monotonic deque. Each one is a tool that turns an O(n²) brute force into O(n log n) or O(n).

Schedule

  • Mon — p91 Range Sum Query Mutable (LC 307): point-update + range-sum. Two implementations: Fenwick (BIT) for sum; segment tree (iterative, 2n nodes) for generality.
  • Tue — p92 Count Smaller Numbers After Self (LC 315): BIT over coordinate-compressed values, walk right-to-left querying sum(0..v-1). Also merge-sort with index tracking.
  • Wed — p93 Implement strStr / KMP (LC 28): failure function (longest proper prefix that is also a suffix) + match loop that never backtracks i. Z-algorithm sketch as bonus.
  • Thu — p94 Repeated DNA Sequences (LC 187): polynomial rolling hash (Rabin-Karp), constant-time slide via h = (h*BASE - first*POW + new) % MOD. Hash collision discussion.
  • Fri — p95 Sliding Window Maximum (LC 239): monotonic decreasing deque holding indices; pop from back while smaller, pop from front when out of window.

Readiness Gate

  • Implement Fenwick tree from scratch in 10 min (point update + prefix sum).
  • Implement iterative segment tree from scratch in 15 min.
  • Write KMP failure function and articulate the loop invariant.
  • Write polynomial rolling hash with modular sliding update.
  • Write monotonic deque for sliding window max.

If any of these takes > 1 hint, re-do the problem.

Cross-References

What “Done” Looks Like

  • All 5 problems solved cold within ~25 min, no hints.
  • Can implement each DS without referring to notes.
  • Can articulate when to choose each one (BIT vs segment tree, KMP vs rolling hash).
  • Can cite at least one production analog per problem.