Advanced Data Structures

Why this module exists

Arrays, maps, stacks, and queues cover 80% of problems. But the remaining 20% often unlock interviews: prefix structures and log-time updates. This module focuses on:

1. Trie (prefix tree) — fast prefix queries and autocomplete
2. Fenwick tree — fast range sums with point updates

1) Trie (Prefix Tree)

A trie stores characters node by node. Each path from root to a node represents a prefix.

Operations:

• Insert: O(L)
• Search: O(L)
• StartsWith: O(L)

Why it matters:

• Autocomplete
• Spell check
• Prefix-based filters

2) Fenwick Tree (Binary Indexed Tree)

Fenwick supports:

• Point updates: O(log n)
• Prefix sums: O(log n)
• Range sum: prefix(r) - prefix(l-1)

Key idea:

• Use the lowest set bit to jump upward.
• Tree is 1-indexed internally.

Interview signals

• You can trade memory for speed (Trie).
• You know how to support updates and queries efficiently (Fenwick).

Problems in this module

• Trie Prefix Search — implement Insert/Search/StartsWith
• Fenwick Range Sum — range sums with updates