4 lessons
Tries: Trees Built From Words
Store thousands of words in a tree that shares every common prefix, and get autocomplete almost for free.
Segment Trees for Range Queries
Answer "what is the min, max or sum of this range?" and update a value, both in O(log n), on an array that keeps changing.
Fenwick Trees (Binary Indexed Trees)
The same O(log n) range-sum-with-updates power as a segment tree, in about ten lines, once you learn one bit trick.
Design Problems: Combining Structures on Purpose
The real skill interviews test with "design a ___" questions — picking two structures that cover each other's weaknesses.