4.13.4 — Tries, Segment Trees & Fenwick Trees

Three specialised trees, each existing because a general-purpose structure fails at one specific question.

• A hash map cannot answer "which stored words start with pay". The trie can.
• A prefix-sum array (Chapter 4.2) answers range sums in O(1), but if a value changes you must rebuild the whole array in O(n). The segment tree and Fenwick tree keep both operations at O(\log n).

1. The trie: a tree whose edges are characters

A trie (from "retrieval", pronounced "try" by most people to distinguish it from "tree") stores strings by putting one character on each edge, so a path from the root spells a prefix.

A trie holding car, card, care and cat. Shared prefixes share a path, so ca exists once. The dashed ring marks a node where a complete word ends — necessary because car is a word and also a prefix of card, which a node's position alone cannot tell you.

class TrieNode {
  children = new Map<string, TrieNode>();     // (1)
  isWord = false;                             // (2)
}

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {                                       // (3)
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.isWord = true;                                            // (4)
  }

  private walk(prefix: string): TrieNode | null {                  // (5)
    let node = this.root;
    for (const ch of prefix) {
      const next = node.children.get(ch);
      if (!next) return null;
      node = next;
    }
    return node;
  }

  has(word: string): boolean       { return this.walk(word)?.isWord ?? false; }   // (6)
  hasPrefix(prefix: string): boolean { return this.walk(prefix) !== null; }       // (7)
}

1. A map from the next character to the child node. For a fixed lowercase alphabet you can use a 26-slot array instead, which is faster but wastes memory on sparse tries.
2. This flag is what makes car and card both storable. Without it, you could not tell a complete word from a prefix on the way to a longer one.
3. Walk down, creating nodes as needed. One node per character, and existing prefixes are reused for free.
4. Mark the end.
5. walk is the shared engine: follow the characters, return the node you land on or null.
6. A word exists if the walk succeeds and the landing node is flagged.
7. A prefix exists if the walk merely succeeds. The single flag check is the entire difference between the two queries, and that is what a hash map cannot replicate.

The complexity is the point. Insert and lookup are O(L) where L is the length of the word — independent of how many words are stored. A trie with ten words and a trie with ten million words look up a five-letter word in the same five steps. A hash map is also roughly O(L), since it must hash the whole string, so on exact lookup they tie. The trie wins on everything prefix-shaped:

• Autocomplete — walk to the prefix node, then collect every word below it. Chapter 11.11 builds a full autocomplete service on this.
• Longest matching prefix — walk until you fall off, remembering the last flagged node. This is how IP routing tables work (Chapter 5.3): a router holds prefixes like 192.168.0.0/16 and must find the longest one matching a destination address.
• Word-search and word-break problems — Chapter 4.15.

The cost is memory, and it is substantial. Every node holds a map or an array. For a 26-letter alphabet with array children, one node is 26 pointers — 208 bytes on a 64-bit machine — to store one character. A dictionary of 100,000 English words can easily consume tens of megabytes. Three standard mitigations:

• Compressed trie (also called a radix tree or Patricia trie): collapse any chain of single-child nodes into one node holding the whole substring. car/cart becomes root → "car" → "t" rather than four nodes. This is what real IP routing tables and etcd's key store use.
• Map children instead of arrays when the alphabet is large or the trie is sparse, trading a pointer chase for much less waste.
• DAWG (directed acyclic word graph): merge identical suffix structures as well as prefixes, so running and jumping share one ing ending. Much smaller, but you can no longer attach per-word data to a node.

2. The problem segment trees solve

Chapter 4.2's prefix sum answers "sum of range i to j" in O(1) after an O(n) build. Perfect — until a value changes. Updating nums[3] invalidates every prefix entry from index 4 onward, so the update is O(n).

So there are two extremes and neither is good when you need both operations:

Approach	Range query	Point update
plain array, loop the range	O(n)	O(1)
prefix sum array	O(1)	O(n)
segment tree	O(\log n)	O(\log n)

A segment tree balances them. The idea: build a binary tree over the array where each node stores the answer for one contiguous range. The root covers the whole array, its children cover the two halves, and the leaves cover single elements.

A segment tree over [1,2,3,4,5,6,7,8]. Every node holds the sum of its range. A query for indices 2 through 5 does not touch the leaves at all — it finds two already-computed nodes whose ranges exactly tile the request.

class SegmentTree {
  private tree: number[];                                  // (1)
  private n: number;

  constructor(nums: number[]) {
    this.n = nums.length;
    this.tree = new Array(4 * this.n).fill(0);             // (2)
    this.build(nums, 1, 0, this.n - 1);
  }

  private build(nums: number[], node: number, lo: number, hi: number): void {
    if (lo === hi) { this.tree[node] = nums[lo]; return; } // (3)
    const mid = (lo + hi) >> 1;                            // (4)
    this.build(nums, node * 2,     lo,      mid);          // (5)
    this.build(nums, node * 2 + 1, mid + 1, hi);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];   // (6)
  }

  query(l: number, r: number, node = 1, lo = 0, hi = this.n - 1): number {
    if (r < lo || hi < l) return 0;                        // (7)  no overlap
    if (l <= lo && hi <= r) return this.tree[node];        // (8)  fully inside — the win
    const mid = (lo + hi) >> 1;                            // (9)  partial — split
    return this.query(l, r, node * 2,     lo,      mid)
         + this.query(l, r, node * 2 + 1, mid + 1, hi);
  }

  update(i: number, value: number, node = 1, lo = 0, hi = this.n - 1): void {
    if (lo === hi) { this.tree[node] = value; return; }    // (10)
    const mid = (lo + hi) >> 1;
    if (i <= mid) this.update(i, value, node * 2, lo, mid);            // (11)
    else          this.update(i, value, node * 2 + 1, mid + 1, hi);
    this.tree[node] = this.tree[node * 2] + this.tree[node * 2 + 1];   // (12)
  }
}

1. The tree lives in a flat array, using the same implicit-child trick as the heap in Chapter 4.16: node k's children are 2k and 2k+1. No node objects, no pointers, excellent cache behaviour.
2. Why 4n? The tree has n leaves, so about 2n nodes if n is a power of two. When it is not, the recursion pads out to the next power of two and the indices can spread further, and 4n is the safe bound everyone uses. It wastes memory and removes an entire class of bugs.
3. A leaf covers one index and stores that element.
4. >> 1 is integer division by 2 (Chapter 1.3 covers shifts).
5. Build both halves first.
6. A node's value is combined from its children. This is post-order (Chapter 4.13.1) and it is the only line that knows we are computing sums — swap + for Math.min and you have a range-minimum tree, with nothing else changed.
7. This node's range is entirely outside the request. Return the identity value for the operation — 0 for sum, Infinity for minimum. Returning the wrong identity here is the classic bug.
8. This node's range is entirely inside the request, so its stored answer is exactly what we need and we stop. This line is why the query is O(\log n): it prunes whole subtrees.
9. Partial overlap, so ask both children and combine.
10. Update walks to the leaf and writes the new value.
11. Only one side can contain index i, so only one branch is taken — that is the O(\log n).
12. Then recompute every ancestor on the way back up. The path from leaf to root is \log n long.

Why the query is O(\log n) and not O(n). At each level of the tree, at most four nodes can be in the "partial overlap" state — two near the left edge of the query range and two near the right. Everything in between is fully inside and stops at line 8; everything outside stops at line 7. So the recursion touches O(1) nodes per level over \log n levels. That argument is the standard follow-up question, and it is the part people cannot produce from memorised code.

What else a segment tree does. Replace the combine function and you get range minimum, range maximum, range GCD, or a count of elements satisfying some property. The requirement is that the operation be associative — that (a op b) op c equals a op (b op c) — because the tree combines in whatever grouping its structure dictates. Sum, min, max and GCD all qualify. Subtraction does not, which is why there is no "range difference" tree.

Lazy propagation extends this to range updates ("add 5 to every element from i to j"). Instead of updating every leaf, mark the covering node with a pending change and push it down only when a later query needs to look inside. That keeps range updates at O(\log n) too. It is worth knowing the name and the idea; the implementation is fiddly and rarely required outside competitive programming.

3. Fenwick tree: the same job in a quarter of the code

A Fenwick tree or binary indexed tree does prefix sums with point updates, both in O(\log n), using a single array of size n and about eight lines of code. It handles less than a segment tree — prefix sums and anything derivable from them, not arbitrary associative operations — but for the sum case it is smaller, faster and much shorter to write correctly under time pressure.

class Fenwick {
  private tree: number[];
  constructor(size: number) { this.tree = new Array(size + 1).fill(0); }   // (1)

  add(i: number, delta: number): void {          // (2)
    for (let k = i + 1; k < this.tree.length; k += k & -k) this.tree[k] += delta;   // (3)
  }

  prefixSum(i: number): number {                 // (4)
    let total = 0;
    for (let k = i + 1; k > 0; k -= k & -k) total += this.tree[k];                  // (5)
    return total;
  }

  rangeSum(l: number, r: number): number { return this.prefixSum(r) - this.prefixSum(l - 1); }  // (6)
}

1. One-indexed internally, which is what makes the bit arithmetic work, so the array is one longer than the data.
2. add adjusts a position by a delta rather than setting a value. To set a value you add newValue − oldValue, which means you have to keep the original array alongside.
3. and 5. k & -k is the whole algorithm. In two's complement (Chapter 1.3), -k is ~k + 1, and ANDing that with k isolates the lowest set bit. For k = 12 (binary 1100), k & -k is 4 (binary 100).

Each entry tree[k] stores the sum of the k & -k elements ending at position k. So tree[8] covers positions 1–8, tree[12] covers 9–12, tree[6] covers 5–6, and tree[7] covers just 7. Adding the lowest set bit jumps to the next node that contains position k, which is the update path. Subtracting it jumps to the node covering everything before the current block, which is the query path. Since each step clears or carries one bit of a number under n, both loops run at most \log_2 n times.

4. The prefix sum of positions 0 through i.
5. And a range is the difference of two prefixes — the same subtraction as Chapter 4.2's prefix array. This is also why a Fenwick tree cannot do range minimum: minima do not subtract. That single limitation is the practical dividing line between the two structures.

Which to reach for. Sums or counts, and you want it written quickly and correctly? Fenwick. Minimum, maximum, GCD, range updates, or anything where you must inspect a range rather than fold it? Segment tree. Both are O(\log n); the Fenwick's constant factor is smaller and its code is a quarter the size.

The most common real use of a Fenwick tree in interview problems is counting inversions or "how many elements to my left are smaller than me" — you sweep the array, query the prefix count, then add 1 at your own value's position. That shape solves a family of problems that otherwise need a modified merge sort.

What the interviewer will push on

"Why use a trie when a hash set has O(1) lookup?" Because the question is not lookup. A hash set cannot answer "which words start with pay" without scanning every key. Then name the second use nobody expects: longest-prefix matching, which is how IP routing tables work.

"What is a trie's memory cost?" Real answer with a number: an array-child node for a 26-letter alphabet is 26 pointers, roughly 208 bytes, to store one character. Then name a fix — a compressed trie collapsing single-child chains, which is what actual routing tables use.

"Why is a segment tree query O(\log n)? It looks like it visits many nodes." At most four nodes per level are partially overlapping; everything else terminates immediately as fully-inside or fully-outside. O(1) per level times \log n levels.

"Segment tree or Fenwick tree?" Fenwick for sums and counts, because it is a quarter of the code with a smaller constant. Segment tree when the operation is not invertible — minimum and maximum cannot be recovered by subtracting two prefixes — or when you need range updates with lazy propagation.

"Your segment tree does range sums. What must change for range minimum?" One line: the combine function, plus the identity value returned for a non-overlapping range, which becomes Infinity instead of 0. Naming the identity unprompted is the tell, because that is the line people get wrong.

One thing to volunteer: say what the operation must satisfy for the tree to be valid — it must be associative, since the tree groups the combining however its structure dictates. That is why sum, min, max and GCD work and subtraction does not.

Recall

• A trie puts one character per edge, so lookup is O(L) independent of how many words are stored, and shared prefixes are stored once. The isWord flag is what separates car the word from car the prefix of card.
• Tries win on prefix questions — autocomplete, longest-prefix matching in IP routing — and lose on memory; a compressed trie collapses single-child chains to fix that.
• Prefix sums give O(1) query and O(n) update; a segment tree balances both at O(\log n) by storing one range's answer per node.
• The query is O(\log n) because at most four nodes per level are partially overlapping — the rest stop immediately as fully inside or fully outside.
• Changing a segment tree from sum to minimum is one line — the combine function — plus the matching identity value for non-overlapping ranges. The operation must be associative.
• A Fenwick tree does prefix sums and point updates in eight lines using k & -k to isolate the lowest set bit; it cannot do minimum, because minima do not subtract.

Self-test: Why does a trie need an isWord flag at all? · What does k & -k compute, and why does that make both Fenwick loops O(\log n)? · Why is a segment tree array sized 4n? · What must be true of an operation for a segment tree to compute it, and give one operation that fails the test · When is a Fenwick tree the wrong choice?

Next: 4.14 is the largest problem set in the book — fifteen tree problems, and almost all of them are one question: is this answered on the way down, on the way up, or level by level?