Tries & Range Query Trees
Two specialized trees built for one job each: matching strings by prefix, and answering "what's the sum of this range?" fast
Introduction
Lesson 7 introduced trees as a general-purpose hierarchy. The structures in this lesson go the opposite direction: they're trees shaped around exactly one problem. A trie organizes strings character by character so that shared prefixes are never stored twice. A segment tree and a Fenwick tree both answer range questions, "what's the sum from index 3 to index 9?", in O(log n), instead of the O(n) a plain array scan needs every time.
Tries: Storing Strings by Shared Prefix
A trie (from retrieval) is a tree where each edge represents one character, and each root-to-node path spells out the prefix of some word. Words that share a prefix share the same path, only the branch point where they diverge, and whatever comes after, actually costs extra storage.
A Trie Holding "cat", "car", and "dog"
Figure 1: "cat" and "car" share the "ca" path and only diverge at the last letter
class TrieNode:
def __init__(self) -> None:
self.children: dict[str, "TrieNode"] = {}
self.is_end_of_word: bool = False
class Trie:
def __init__(self) -> None:
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word: str) -> bool:
node = self._walk(word)
return node is not None and node.is_end_of_word
def starts_with(self, prefix: str) -> bool:
return self._walk(prefix) is not None
def _walk(self, prefix: str) -> "TrieNode | None":
# Shared by search() and starts_with(): follow one character per level
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return nodetrie = Trie()
for word in ["cat", "car", "card", "care", "dog"]:
trie.insert(word)
print(trie.search("car"))
print(trie.search("ca")) # "ca" was never inserted as a complete word
print(trie.starts_with("ca")) # but it is a valid prefix
print(trie.search("bird"))Expected Output:
True False True False
search() vs starts_with()
Both walk the exact same path, the only difference is what they check once they arrive. starts_with just needs the path to exist. search additionally needs is_end_of_word to be True, since "ca" being a valid path doesn't mean "ca" was ever inserted as a complete word.
Practical Pattern: Autocomplete
Walk to the end of the prefix once, then depth-first search everything below that point, collecting every complete word found along the way. This is exactly how a search bar suggests completions as you type.
def autocomplete(trie: Trie, prefix: str) -> list[str]:
node = trie._walk(prefix)
if node is None:
return []
results: list[str] = []
def dfs(node: "TrieNode", path: str) -> None:
if node.is_end_of_word:
results.append(prefix + path)
for char, child in node.children.items():
dfs(child, path + char)
dfs(node, "")
return sorted(results)print(autocomplete(trie, "car")) print(autocomplete(trie, "do")) print(autocomplete(trie, "xyz"))
Expected Output:
['car', 'card', 'care'] ['dog'] []
Lookup by index and prefix search cost O(m), where m is the length of the word or prefix, completely independent of how many other words are stored. A hash table (Lesson 6) can match a word in O(m) too, but it has no notion of "prefix" at all, finding every word starting with "ca" would mean scanning every key.
Segment Trees: Answering Range Queries Fast
Given an array, a segment tree precomputes the sum (or min, max, anything associative) of every range that a divide-and-conquer split would ever touch. Each node covers a contiguous range and stores the combined result for it; leaves cover a single element.
Segment Tree Over [1, 3, 5, 7]
Figure 2: Every node's sum is precomputed from its two halves
class SegmentTree:
def __init__(self, values: list[int]) -> None:
self.n = len(values)
self.tree: list[int] = [0] * (4 * self.n) # generous upper bound on node count
self._build(values, 0, 0, self.n - 1)
def _build(self, values: list[int], node: int, start: int, end: int) -> None:
if start == end:
self.tree[node] = values[start]
return
mid = (start + end) // 2
left, right = 2 * node + 1, 2 * node + 2
self._build(values, left, start, mid)
self._build(values, right, mid + 1, end)
self.tree[node] = self.tree[left] + self.tree[right]
def query(self, left: int, right: int) -> int:
return self._query(0, 0, self.n - 1, left, right)
def _query(self, node: int, start: int, end: int, left: int, right: int) -> int:
if right < start or end < left:
return 0 # no overlap
if left <= start and end <= right:
return self.tree[node] # fully covered
mid = (start + end) // 2 # partial overlap: split
return (self._query(2 * node + 1, start, mid, left, right)
+ self._query(2 * node + 2, mid + 1, end, left, right))
def update(self, index: int, value: int) -> None:
self._update(0, 0, self.n - 1, index, value)
def _update(self, node: int, start: int, end: int, index: int, value: int) -> None:
if start == end:
self.tree[node] = value
return
mid = (start + end) // 2
if index <= mid:
self._update(2 * node + 1, start, mid, index, value)
else:
self._update(2 * node + 2, mid + 1, end, index, value)
self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]values = [1, 3, 5, 7, 9, 11] seg = SegmentTree(values) print(seg.query(1, 3)) # 3 + 5 + 7 seg.update(1, 10) # index 1 changes from 3 to 10 print(seg.query(1, 3)) # 10 + 5 + 7
Expected Output:
15 22
A query only recurses into a node when the requested range partially overlaps it, fully covered nodes return their precomputed sum immediately, fully uncovered nodes return 0 without recursing further. That pruning is what keeps both query and update at O(log n).
Fenwick Trees: A Leaner Alternative
A Fenwick tree (also called a Binary Indexed Tree) answers the same prefix-sum questions as a segment tree, but with a single flat array and no explicit node objects at all. The trick is a bit of integer arithmetic: isolating the lowest set bit of an index tells you exactly which range that array slot is responsible for.
for i in [4, 6, 12, 13]:
print(i, bin(i), "-> lowest set bit:", i & (-i))Expected Output:
4 0b100 -> lowest set bit: 4 6 0b110 -> lowest set bit: 2 12 0b1100 -> lowest set bit: 4 13 0b1101 -> lowest set bit: 1
class FenwickTree:
def __init__(self, size: int) -> None:
self.size = size
self.tree: list[int] = [0] * (size + 1) # 1-indexed internally
def update(self, index: int, delta: int) -> None:
index += 1 # convert caller's 0-indexed position
while index <= self.size:
self.tree[index] += delta
index += index & (-index) # jump to the next node this index feeds into
def prefix_sum(self, index: int) -> int:
index += 1
total = 0
while index > 0:
total += self.tree[index]
index -= index & (-index) # strip the lowest set bit, climb toward the root
return total
def range_sum(self, left: int, right: int) -> int:
if left == 0:
return self.prefix_sum(right)
return self.prefix_sum(right) - self.prefix_sum(left - 1)values = [1, 3, 5, 7, 9, 11]
fenwick = FenwickTree(len(values))
for index, value in enumerate(values):
fenwick.update(index, value)
print(fenwick.range_sum(1, 3)) # 3 + 5 + 7
fenwick.update(1, 10 - 3) # a *delta*, not a replacement: old value was 3, new is 10
print(fenwick.range_sum(1, 3)) # 10 + 5 + 7Expected Output:
15 22
The bit trick has a clean geometric meaning. Each slot tree[i] is responsible for a block of the array whose length is its lowest set bit (i & -i), ending at position i. Those blocks tile the array at different scales:
update() Takes a Delta, Not a New Value
Unlike the segment tree's update(index, value), the Fenwick tree's update(index, delta) adds to what's already there. To overwrite a value, you compute new_value - old_value and pass that as the delta, exactly what the usage example above does to change index 1 from 3 to 10.
Segment Tree vs Fenwick Tree
| Segment Tree | Fenwick Tree | |
|---|---|---|
| Build / query / update | O(n) / O(log n) / O(log n) | O(n log n) / O(log n) / O(log n) |
| Memory | ~4n array slots | n + 1 array slots |
| Supported operations | Any associative operation: sum, min, max, gcd | Best suited to invertible operations like sum, where subtraction can undo an update |
| Code complexity | More code, more flexible | About 20 lines, but narrower in what it supports |
Key Takeaways
- Tries share storage for common prefixes, and cost O(m) per operation, where m is word length, not the number of words stored
- Autocomplete is just a walk to a prefix followed by a DFS collecting every complete word underneath it
- Segment trees precompute range results with a divide-and-conquer tree, turning O(n) range scans into O(log n) queries
- Fenwick trees answer the same prefix-sum questions with a flat array and bit arithmetic instead of explicit tree nodes
- Neither range structure beats the other universally - segment trees handle more operation types, Fenwick trees are leaner when sum (or another invertible operation) is all you need