11 — Tries and range structures

The trees in chapter 10 organize keys by comparison: smaller to the left, larger to the right. The structures in this chapter organize something else.

• Tries organize keys by their digits (characters, or bits), so that all keys sharing a prefix share a path. Prefix questions, which a hash table cannot answer and a search tree answers only indirectly, become walks down one branch.
• Range structures (segment trees, Fenwick trees, square root decomposition) organize positions in an array, precomputing answers for chosen blocks so that any range can be assembled from a few of them, and so that an update touches only a few blocks.
• Spatial trees (interval, quad and k-d trees) organize regions, so that a query about a region can skip everything that cannot intersect it.

What they share is the trade they make: a little extra memory and some structure maintained on every update, in exchange for answering a whole family of queries in logarithmic rather than linear time.

Timings in this chapter were measured with Python 3.14 on one Mac. Exact numbers will differ elsewhere; the ratios are what matter.

Tries

A trie (from retrieval; the structure is usually credited to de la Briandais in 1959 and the name to Fredkin in 1960) is a tree in which each edge is labeled with one character and each node represents the string spelled by the path from the root. A node is marked if a stored word ends there. All words with a common prefix share the path for that prefix.

words: car card care cared cart cat dog

            (root)
            /    \
           c      d
           |      |
           a      o
          / \     |
         r*  t*   g*
       / | \
     d*  e*  t*
         |
         d*            * = a word ends here

The trie above has 12 nodes for 7 words. The word car and the prefix ca both correspond to nodes, but only car is marked, which is the difference between search and startsWith.

Operations

Each node holds a dictionary from character to child, a flag for “a word ends here”, and, for prefix counting, the number of words in its subtree.

class TrieNode:
    __slots__ = ("children", "end", "prefix_count")

    def __init__(self):
        self.children = {}
        self.end = False          # a word ends here
        self.prefix_count = 0     # words that pass through or end here


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        if self.search(word):
            return
        node = self.root
        node.prefix_count += 1
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
            node.prefix_count += 1
        node.end = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.end

    def starts_with(self, prefix):
        node = self._walk(prefix)
        return node is not None and node.prefix_count > 0

    def count_prefix(self, prefix):
        node = self._walk(prefix)
        return node.prefix_count if node else 0

On the seven words above:

search('car'): True  search('ca'): False  starts_with('ca'): True
count_prefix('car'): 5

Every operation costs $O(L)$ for a key of length $L$, independent of how many keys are stored. That is the trie’s main property, and it is often stated as “faster than a hash table”. It is not, in practice: a hash table also costs $O(L)$ to hash the key, and does so in one tight loop rather than $L$ pointer dereferences. What a trie adds is the ability to answer questions about prefixes.

The child map is a design decision. A Python dictionary is flexible but large. A fixed array of 26 (or 256) pointers gives the fastest child lookup and the worst memory use, since most slots are empty below the first few levels. A sorted list of (character, child) pairs is compact but needs a search. Production tries mix these, choosing a node layout by the number of children (the adaptive radix tree used in some databases does exactly this).

The insert above checks search first so that inserting a duplicate does not inflate the prefix counts. Deletion walks down, unmarks the end node, decrements counts on the way, and removes any node whose count reaches zero.

Implement Trie (Prefix Tree), LeetCode 208, is exactly insert, search and starts_with.

Autocomplete

To list completions of a prefix, walk to the prefix’s node and enumerate its subtree. Visiting children in sorted order gives the completions in lexicographic order, and stopping after limit results avoids touching the rest of the subtree:

    def autocomplete(self, prefix, limit=10):
        """Up to `limit` words with this prefix, in lexicographic order."""
        node = self._walk(prefix)
        out = []
        if node is None:
            return out
        stack = [(node, prefix)]
        while stack and len(out) < limit:
            node, word = stack.pop()
            if node.end:
                out.append(word)
            for ch in sorted(node.children, reverse=True):   # smallest popped first
                stack.append((node.children[ch], word + ch))
        return out

autocomplete('car', 3): ['car', 'card', 'care']

Real autocomplete ranks by popularity rather than alphabetically. The usual design stores, at each node, the top $k$ completions for that prefix, precomputed. Queries become $O(L)$ with no subtree walk, at the cost of $k$ entries per node and more work on updates. Search Suggestions System (LeetCode 1268) is the alphabetical version.

When a sorted array is enough

A sorted list answers prefix questions too: every word with prefix $p$ lies in one contiguous run, found with two binary searches. On the macOS word list (234,456 distinct lowercase words, 2,248,668 characters), counting words with a given prefix:

The trie is 2.5 to 2.8 times faster here, because it stores the counts. But the sorted list is one pointer per word, 1.8 MiB, where the trie took 152.8 MiB (table below), and building it is one call to sorted. For a static word set, a sorted array plus binary search is often the better engineering choice. A trie earns its memory when the set changes, when the per-node data is richer (counts, top-k lists, values), or when the query walks character by character, as in the next three problems.

Longest prefix match and IP routing

An IP router holds a table of network prefixes, each with a next hop, and must send each packet to the next hop of the longest prefix that contains the destination address. A /24 route is more specific than the /16 that contains it, which is more specific than the /0 default route.

A binary trie over address bits does this directly. Each route is inserted as a path of prefix_len bits and marked with its next hop. A lookup follows the address bit by bit and remembers the last next hop it passed, which is the longest match.

class RoutingTable:
    """Binary trie over IPv4 address bits; each node may hold a next hop."""

    def __init__(self):
        self.root = [None, None, None]        # [child0, child1, next_hop]

    def add(self, network, prefix_len, next_hop):
        node = self.root
        for i in range(prefix_len):
            bit = (network >> (31 - i)) & 1
            if node[bit] is None:
                node[bit] = [None, None, None]
            node = node[bit]
        node[2] = next_hop

    def lookup(self, addr):
        node, best = self.root, self.root[2]
        for i in range(32):
            node = node[(addr >> (31 - i)) & 1]
            if node is None:
                break
            if node[2] is not None:
                best = node[2]                # longer match found
        return best

With routes 0.0.0.0/0 → default, 10.0.0.0/8 → A, 10.1.0.0/16 → B and 10.1.2.0/24 → C:

10.1.2.3 -> C
10.1.9.9 -> B
10.200.0.1 -> A
8.8.8.8 -> default

The implementation was checked against a brute-force search over all matching prefixes (using Python’s ipaddress module) for random routing tables with prefix lengths from 0 to 32.

A lookup is at most 32 steps for IPv4 and 128 for IPv6. Real routers cannot afford one memory access per bit, so they compress the trie: a path-compressed trie skips runs of single-child nodes (next section), and a level-compressed trie replaces dense subtrees with arrays indexed by several bits at once. The Linux kernel’s IPv4 routing table is an LC-trie of this kind. Hardware routers often use TCAM, a memory that compares an address against every prefix in parallel.

Wildcard search

Design Add and Search Words Data Structure (LeetCode 211) stores words and answers patterns in which . matches any one letter. A literal character follows one edge; a . tries every child. Depth-first search with backtracking:

class WordDictionary:
    """addWord / search where '.' matches any single letter."""

    def __init__(self):
        self.root = {}

    def add_word(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True

    def search(self, pattern):
        def dfs(node, i):
            if i == len(pattern):
                return "$" in node
            ch = pattern[i]
            if ch == ".":
                return any(dfs(child, i + 1)
                           for key, child in node.items() if key != "$")
            child = node.get(ch)
            return child is not None and dfs(child, i + 1)
        return dfs(self.root, 0)

With bad, dad, mad stored, the patterns pad, bad, .ad, b.. give [False, True, True, True]. Without wildcards a search is $O(L)$. With $w$ wildcards it can branch into up to $\sigma^w$ paths for an alphabet of size $\sigma$, bounded by the size of the trie; in practice the trie prunes most branches immediately. The "$" key marks the end of a word, so it must be skipped when expanding a wildcard. Word Search II (LeetCode 212) uses the same idea in reverse: put the dictionary in a trie and walk the grid and the trie together, abandoning a grid path as soon as it leaves the trie.

Counting distinct substrings

Every substring of $s$ is a prefix of some suffix of $s$. Insert all $n$ suffixes into a trie, and every node except the root then corresponds to exactly one distinct non-empty substring: two equal substrings follow the same path to the same node.

def count_distinct_substrings(s):
    """Insert every suffix; each trie node other than the root is one distinct
    non-empty substring. O(n^2) time and nodes."""
    root, nodes = {}, 0
    for i in range(len(s)):
        node = root
        for ch in s[i:]:
            if ch not in node:
                node[ch] = {}
                nodes += 1
            node = node[ch]
    return nodes

For ababa it returns 9: a, b, ab, ba, aba, bab, abab, baba, ababa. The suffix trie has up to $n(n+1)/2$ nodes, so this is $O(n^2)$ time and space, which limits it to a few thousand characters. It is still better than putting all substrings in a set, which costs $O(n^3)$ because each substring is copied and hashed. Linear-time answers use a suffix automaton or a suffix array with its LCP array ($\frac{n(n+1)}{2} - \sum \text{LCP}$), covered with the string algorithms in chapter 5.

Maximum XOR with a binary trie

Maximum XOR of Two Numbers in an Array (LeetCode 421). Brute force tries all pairs, $O(n^2)$. The trie solution uses the fact that XOR is maximized greedily from the top bit down: a 1 in bit 30 is worth more than all lower bits combined. Store every number in a binary trie, most significant bit first. For each number $x$, walk the trie choosing at each level the bit opposite to $x$‘s bit when that branch exists, since that sets the corresponding bit of the XOR.

def max_xor_pair(nums):
    """Maximum Xor of Two Numbers in an Array, via a binary trie. O(n * B)."""
    bits = max(nums).bit_length()
    root = [None, None]
    for x in nums:
        node = root
        for b in range(bits - 1, -1, -1):
            bit = (x >> b) & 1
            if node[bit] is None:
                node[bit] = [None, None]
            node = node[bit]
    best = 0
    for x in nums:
        node, cur = root, 0
        for b in range(bits - 1, -1, -1):
            bit = (x >> b) & 1
            if node[bit ^ 1] is not None:     # the opposite bit sets this bit of the XOR
                cur |= 1 << b
                node = node[bit ^ 1]
            else:
                node = node[bit]
        best = max(best, cur)
    return best

For [3, 10, 5, 25, 2, 8] it returns 28 (5 XOR 25). Time is $O(nB)$ for $B$-bit numbers. The greedy choice is safe because whichever branch is taken at a level, the trie guarantees some stored number continues it. Variants include maximum XOR with a bound on the partner (Maximum XOR With an Element From Array, LeetCode 1707, solved offline by sorting queries and inserting numbers as they become eligible) and maximum XOR of a subarray (insert prefix XORs).

Ternary search trees

A ternary search tree (Bentley and Sedgewick, 1997) replaces each trie node’s child map with a small binary search tree. Each node holds one character and three pointers: lo for keys whose current character is smaller, hi for larger, and eq to advance to the next character.

class TSTNode:
    __slots__ = ("ch", "lo", "eq", "hi", "end")

    def __init__(self, ch):
        self.ch = ch
        self.lo = self.eq = self.hi = None
        self.end = False


class TST:
    def __init__(self):
        self.root = None

    def insert(self, word):
        if not word:
            return
        if self.root is None:
            self.root = TSTNode(word[0])
        node, i = self.root, 0
        while True:
            ch = word[i]
            if ch < node.ch:
                if node.lo is None:
                    node.lo = TSTNode(ch)
                node = node.lo
            elif ch > node.ch:
                if node.hi is None:
                    node.hi = TSTNode(ch)
                node = node.hi
            elif i + 1 < len(word):
                i += 1
                if node.eq is None:
                    node.eq = TSTNode(word[i])
                node = node.eq
            else:
                node.end = True
                return

    def _find(self, s):
        node, i = self.root, 0
        while node:
            ch = s[i]
            if ch < node.ch:
                node = node.lo
            elif ch > node.ch:
                node = node.hi
            elif i + 1 < len(s):
                i += 1
                node = node.eq
            else:
                return node
        return None

    def search(self, word):
        node = self._find(word) if word else None
        return node is not None and node.end

A TST has one node per trie edge, so the node counts are almost identical (below), but each node is three pointers instead of a map, which is much smaller. A search follows at most $L$ eq links plus the lo/hi steps at each level, about $\log_2 \sigma$ per character when those small trees are balanced. They degrade if the words are inserted in sorted order, since the lo/hi trees are ordinary unbalanced BSTs. Inserting in random order, or inserting the median first recursively, avoids that. TSTs support the same prefix and wildcard queries as tries, and partial-match queries are where they were originally pitched.

Radix trees and Patricia tries

Most trie nodes have exactly one child: below the first few characters, words rarely share long prefixes. A radix tree (compressed trie) merges each chain of single-child nodes into one edge labeled with a string. A node then exists only where a word ends or where paths branch, so the number of nodes is at most about twice the number of words, independent of their length.

trie                         radix tree
  c                            "ca"
  |                           /    \
  a                        "r"*    "t"*
 / \                      / | \
r*  t*                 "d"* "e"* "t"*
                            |
                           "d"*

Insertion has one new case: when a word diverges partway along an edge, the edge is split at the divergence point and a new internal node is created there.

    def insert(self, word):
        node = self.root
        while True:
            if not word:
                node.end = True
                return
            edge = node.edges.get(word[0])
            if edge is None:
                leaf = RadixNode()
                leaf.end = True
                node.edges[word[0]] = (word, leaf)
                return
            label, child = edge
            k = 0                                  # length of common prefix
            while k < len(label) and k < len(word) and label[k] == word[k]:
                k += 1
            if k == len(label):                    # whole edge matches: descend
                node, word = child, word[k:]
                continue
            mid = RadixNode()                      # split the edge at k
            mid.edges[label[k]] = (label[k:], child)
            node.edges[word[0]] = (label[:k], mid)
            node, word = mid, word[k:]

Each node keys its edges by first character, since no two edges from one node can start with the same character.

Patricia (Morrison, 1968) is the binary version: a compressed binary trie in which each internal node stores the index of the bit to test next, skipping the bits that all keys below share. It is used for routing tables and in-memory indexes over fixed-length keys.

Built from the same 234,456 words:

The TST’s count is exactly one less than the trie’s, because the trie’s root has no character. The radix tree removes 59% of the nodes but stores substrings on its edges, so its memory saving is smaller than its node saving. The plain trie’s cost is almost entirely the per-node dictionary. Linux kernel radix trees, the Redis rax structure used for streams, and the Ethereum state trie are all compressed tries of one form or another.

Segment trees

The problem

Given an array, answer many queries of the form “sum (or minimum, or maximum) of a[l:r]” while elements are also being changed. A prefix-sum array answers sums in $O(1)$ but needs $O(n)$ to repair after one change. Rescanning answers in $O(n)$ and updates in $O(1)$. A segment tree does both in $O(\log n)$, and works for any associative operation.

The idea

Build a binary tree over the array in which each node stores the answer for one contiguous segment: the root covers the whole array, its children cover the two halves, and so on down to single elements. Any range $[l, r)$ can be written as a union of at most about $2 \log_2 n$ of these canonical segments, at most two per level. A point update changes one leaf and the $\log_2 n$ segments that contain it.

For [5, 3, 7, 9, 6, 4, 1, 2] with sums:

                         [0,8) 37
                /                        \
         [0,4) 24                        [4,8) 13
        /          \                   /          \
   [0,2) 8      [2,4) 16          [4,6) 10      [6,8) 3
    /   \        /    \            /    \        /    \
   5     3      7      9          6      4      1      2

query sum of [1,6) = 3 + 16 + 10 = 29

The query uses the leaf 3, the node for [2,4) and the node for [4,6), three nodes instead of five elements. With a million elements a range sum touches at most about 40 nodes.

Iterative bottom-up implementation

For an array of $n$ elements, a compact layout puts the leaves at indices $n \ldots 2n-1$ of one list and each internal node $i$ at $i$, with children $2i$ and $2i+1$. This works for any $n$, not just powers of two, and uses exactly $2n$ slots. The query walks two pointers up from the ends of the range, taking a node whenever the pointer is on the “outside” edge of its parent.

class SegTree:
    """Bottom-up segment tree for any associative op with an identity.
    Leaves live at tree[n:2n]; node i has children 2i and 2i+1."""

    def __init__(self, data, op, identity):
        self.n = n = len(data)
        self.op, self.e = op, identity
        self.t = [identity] * n + list(data)
        for i in range(n - 1, 0, -1):
            self.t[i] = op(self.t[2 * i], self.t[2 * i + 1])

    def update(self, i, value):
        i += self.n
        self.t[i] = value
        i //= 2
        while i:
            self.t[i] = self.op(self.t[2 * i], self.t[2 * i + 1])
            i //= 2

    def query(self, lo, hi):
        """op over data[lo:hi] (half-open)."""
        left = right = self.e
        lo += self.n
        hi += self.n
        while lo < hi:
            if lo & 1:                    # lo is a right child: take it, move past
                left = self.op(left, self.t[lo])
                lo += 1
            if hi & 1:                    # hi-1 is a left child: take it
                hi -= 1
                right = self.op(self.t[hi], right)
            lo //= 2
            hi //= 2
        return self.op(left, right)

For the example the internal array is:

tree array: [0, 37, 24, 13, 8, 16, 10, 3, 5, 3, 7, 9, 6, 4, 1, 2]
sum of [1:6) = 29

Keeping separate left and right accumulators preserves the order of the operands, so the tree also works for non-commutative operations such as string concatenation or matrix products. It was tested with sum, minimum, and concatenation against direct computation on random arrays with random updates. For a minimum tree, the identity is $+\infty$; for maximum, $-\infty$; for GCD, 0.

Build is $O(n)$, update and query $O(\log n)$, memory $2n$. The recursive formulation (a function on node, node range, query range) is longer but more flexible, and is the natural home for lazy propagation. It needs up to $4n$ slots for arbitrary $n$.

Classic uses

• Range Sum Query - Mutable (LeetCode 307): the class above with +.
• Range minimum with updates: the class with min. Without updates, a sparse table answers RMQ in $O(1)$ after $O(n \log n)$ preprocessing.
• Count of Smaller Numbers After Self (LeetCode 315): scan from the right; a segment tree (or Fenwick tree) over value ranks counts how many smaller values have been seen.
• Storing richer nodes: the maximum subarray sum in a range is answerable if each node stores (total, best prefix, best suffix, best), combined in $O(1)$. Any “monoid” of this kind fits.

Lazy propagation

Point updates touch one leaf. A range update, such as “add 5 to every element of a[l..r]”, touches up to $n$ leaves if done naively. Lazy propagation applies the update to the $O(\log n)$ canonical nodes that exactly cover the range and stops there, leaving a tag on each that says “every element below me has had 5 added, but my children have not been told yet”. When a later operation needs to go below a tagged node, it first pushes the tag down to the two children.

The invariant: every node’s stored aggregate is correct for its segment, taking into account all tags at it and above it; tags at a node describe updates its children have not yet received. Applying a tag to a node must update its aggregate without looking at its children, which is why the update and the aggregate have to fit together: adding $d$ to every element of a segment of length $k$ increases the sum by $dk$ and the minimum by $d$.

class LazySegTree:
    """Range add, range sum and range min, recursive with lazy tags."""

    def __init__(self, data):
        self.n = len(data)
        size = 4 * max(1, self.n)
        self.sum = [0] * size
        self.min = [0] * size
        self.lazy = [0] * size
        if self.n:
            self._build(1, 0, self.n - 1, data)

    def _build(self, node, l, r, data):
        if l == r:
            self.sum[node] = self.min[node] = data[l]
            return
        m = (l + r) // 2
        self._build(2 * node, l, m, data)
        self._build(2 * node + 1, m + 1, r, data)
        self._pull(node)

    def _pull(self, node):
        self.sum[node] = self.sum[2 * node] + self.sum[2 * node + 1]
        self.min[node] = min(self.min[2 * node], self.min[2 * node + 1])

    def _apply(self, node, l, r, delta):
        self.sum[node] += delta * (r - l + 1)
        self.min[node] += delta
        self.lazy[node] += delta          # owed to the children, not yet pushed

    def _push(self, node, l, r):
        if self.lazy[node]:
            m = (l + r) // 2
            self._apply(2 * node, l, m, self.lazy[node])
            self._apply(2 * node + 1, m + 1, r, self.lazy[node])
            self.lazy[node] = 0

    def add(self, ql, qr, delta, node=1, l=0, r=None):
        """Add delta to data[ql..qr] (inclusive)."""
        if r is None:
            r = self.n - 1
        if qr < l or r < ql:
            return
        if ql <= l and r <= qr:           # fully covered: tag and stop
            self._apply(node, l, r, delta)
            return
        self._push(node, l, r)
        m = (l + r) // 2
        self.add(ql, qr, delta, 2 * node, l, m)
        self.add(ql, qr, delta, 2 * node + 1, m + 1, r)
        self._pull(node)

    def query(self, ql, qr, node=1, l=0, r=None):
        """(sum, min) of data[ql..qr] (inclusive)."""
        if r is None:
            r = self.n - 1
        if qr < l or r < ql:
            return 0, float("inf")
        if ql <= l and r <= qr:
            return self.sum[node], self.min[node]
        self._push(node, l, r)
        m = (l + r) // 2
        s1, m1 = self.query(ql, qr, 2 * node, l, m)
        s2, m2 = self.query(ql, qr, 2 * node + 1, m + 1, r)
        return s1 + s2, min(m1, m2)

Both range update and range query are $O(\log n)$. The implementation was verified against a plain list on random arrays with interleaved range adds, point assignments and range queries.

The usual bugs are forgetting to _push before recursing (children then miss earlier updates), forgetting to _pull after recursing (the parent’s aggregate goes stale), and composing tags wrongly when there is more than one kind. With both “assign” and “add” updates, for example, an assignment must clear any pending add, and an add arriving on top of a pending assignment must modify the assignment’s value. In general the tags must form a set of functions closed under composition, with a rule for applying a tag to an aggregate.

Lazy propagation solves problems like “Falling Squares” (LeetCode 699, range assign-max over coordinates) and range-assignment painting problems, usually after coordinate compression.

Persistent segment trees

A persistent structure keeps every past version available after updates. A segment tree is a natural fit, because a point update changes only the $\log_2 n + 1$ nodes on one root-to-leaf path. Path copying creates new copies of exactly those nodes, each pointing to the old, unchanged sibling subtrees. The new root is the new version; the old root still describes the old version, untouched. Each update costs $O(\log n)$ time and $O(\log n)$ new memory.

version 0 root          version 1 root (after updating leaf 5)
     A                      A'
   /   \                  /    \
  B     C       --->     B      C'        B is shared, not copied
 / \   / \                     /  \
...   D   E                   D    E'

The classic application is kth smallest in a subarray. Compress values to ranks $0 \ldots m-1$. Version $i$ is a segment tree over ranks that counts how many of a[0:i] have each rank. The counts of a[l..r] are then version $r+1$ minus version $l$, node by node, and the $k$th smallest is found by walking both versions down together: if the left half contains at least $k$ of the subarray’s values, go left; otherwise subtract that count and go right.

class PersistentKth:
    """kth smallest in a[l..r] with a persistent segment tree over value ranks.
    Version i counts the values of a[0:i]; each version shares all but
    O(log n) nodes with the previous one (path copying)."""

    def __init__(self, a):
        self.vals = sorted(set(a))
        m = len(self.vals)
        self.m = m
        self.left, self.right, self.cnt = [0], [0], [0]   # node 0 = empty tree
        self.roots = [0]
        for x in a:
            r = bisect_left(self.vals, x)
            self.roots.append(self._insert(self.roots[-1], 0, m - 1, r))

    def _new(self, l, r, c):
        self.left.append(l)
        self.right.append(r)
        self.cnt.append(c)
        return len(self.cnt) - 1

    def _insert(self, prev, lo, hi, pos):
        if lo == hi:
            return self._new(0, 0, self.cnt[prev] + 1)
        mid = (lo + hi) // 2
        if pos <= mid:                     # copy this node, rebuild only one side
            child = self._insert(self.left[prev], lo, mid, pos)
            return self._new(child, self.right[prev], self.cnt[prev] + 1)
        child = self._insert(self.right[prev], mid + 1, hi, pos)
        return self._new(self.left[prev], child, self.cnt[prev] + 1)

    def kth(self, l, r, k):
        """k-th smallest (1-based) of a[l..r] inclusive."""
        u, v = self.roots[r + 1], self.roots[l]
        lo, hi = 0, self.m - 1
        while lo < hi:
            mid = (lo + hi) // 2
            in_left = self.cnt[self.left[u]] - self.cnt[self.left[v]]
            if k <= in_left:
                u, v, hi = self.left[u], self.left[v], mid
            else:
                k -= in_left
                u, v, lo = self.right[u], self.right[v], mid + 1
        return self.vals[lo]

Node 0 is a shared empty tree whose children are itself, so versions never need to be built in full: the first version is just node 0. Nodes are stored in three parallel lists rather than as objects, which keeps the memory overhead low.

On [5, 1, 4, 2, 3, 1, 5, 2] the whole structure used 28 nodes, and the 3rd smallest of positions 1 to 5 ([1, 4, 2, 3, 1]) is 2. On 100,000 random values (95,122 distinct), 100,001 versions took 1,762,181 nodes, 17.6 per version, matching the $\lceil \log_2 95122 \rceil + 1 = 18$ nodes on one path. Each query is $O(\log m)$. The implementation was checked against sorting the subarray for random arrays and queries.

2D segment trees

For an $n \times m$ grid with point updates and rectangle queries, a segment tree over rows can store, at each node, a segment tree over columns for the rows that node covers. A rectangle query decomposes the row range into $O(\log n)$ outer nodes and queries each inner tree in $O(\log m)$, for $O(\log n \log m)$ in total. An update changes one leaf in each of the $O(\log n)$ inner trees on the outer path, also $O(\log n \log m)$. Memory is $O(nm)$ with the compact layout (four times as many slots as the grid). Inner trees can be built lazily, allocating only the nodes that are touched, when the grid is huge and sparse. For sums only, the 2D Fenwick tree below is far simpler and uses a quarter of the memory; range-minimum over a static grid is better served by a 2D sparse table.

Fenwick trees

A Fenwick tree, or binary indexed tree (Fenwick, 1994), supports point updates and prefix sums in $O(\log n)$ with one array of $n + 1$ numbers and loops of three lines each. It does less than a segment tree: it needs an operation with an inverse (sum works, so does XOR; min and max do not, except in restricted cases) because a range is computed as the difference of two prefixes.

The lowbit trick

Index the array from 1. Let $\text{lowbit}(i)$ be the value of the lowest set bit of $i$; in two’s complement, i & -i computes it. Fenwick slot $i$ stores the sum of the $\text{lowbit}(i)$ elements ending at position $i$, that is, of the range $(i - \text{lowbit}(i),\; i]$.

 i  binary   i&-i  covers
 1  00001     1   (0, 1]
 2  00010     2   (0, 2]
 3  00011     1   (2, 3]
 4  00100     4   (0, 4]
 5  00101     1   (4, 5]
 6  00110     2   (4, 6]
 7  00111     1   (6, 7]
 8  01000     8   (0, 8]
 9  01001     1   (8, 9]
10  01010     2   (8, 10]
11  01011     1   (10, 11]
12  01100     4   (8, 12]
13  01101     1   (12, 13]
14  01110     2   (12, 14]
15  01111     1   (14, 15]
16  10000    16   (0, 16]

Prefix query. The sum of positions $1 \ldots i$ is slot $i$, which covers $(i - \text{lowbit}(i), i]$, plus the prefix sum up to $i - \text{lowbit}(i)$. Subtracting the lowest set bit is the same as clearing it, so the loop visits one slot per set bit of $i$: at most $\log_2 n$ slots. For $i = 13 = 1101_2$ the loop visits 13 ($1101$), 12 ($1100$) and 8 ($1000$), whose ranges $(12, 13]$, $(8, 12]$ and $(0, 8]$ tile $(0, 13]$ exactly.

Point update. Changing position $i$ must update every slot whose range contains $i$. Those are $i$, then $i + \text{lowbit}(i)$, and so on: adding the lowest set bit carries into the next higher bit, which moves to the next larger range that contains the current one. For $i = 5$: slots 5, 6, 8, 16.

class Fenwick:
    """Point update, prefix sum. Public indices are 0-based."""

    def __init__(self, n_or_data):
        if isinstance(n_or_data, int):
            self.n = n_or_data
            self.t = [0] * (self.n + 1)
        else:                              # O(n) build
            self.n = len(n_or_data)
            self.t = [0] + list(n_or_data)
            for i in range(1, self.n + 1):
                j = i + (i & -i)
                if j <= self.n:
                    self.t[j] += self.t[i]

    def add(self, i, delta):
        i += 1
        while i <= self.n:
            self.t[i] += delta
            i += i & -i                    # next node whose range covers i

    def prefix(self, i):
        """Sum of data[0:i]."""
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i                    # drop the lowest set bit
        return s

    def range_sum(self, lo, hi):
        """Sum of data[lo:hi]."""
        return self.prefix(hi) - self.prefix(lo)

The $O(n)$ build pushes each slot’s total into its parent slot once, instead of doing $n$ separate $O(\log n)$ updates. The test suite checks that both builds produce identical arrays.

A Fenwick tree with non-negative values can also find the smallest index whose prefix sum reaches a target, in $O(\log n)$, by descending powers of two (the lower_bound method in the tested code). That turns it into an order-statistic structure: with counts per value, it finds the $k$th smallest element in a dynamic multiset.

Range update, point query

Store the difference array $d$ in the Fenwick tree, where $d[i] = a[i] - a[i-1]$. Adding $\delta$ to $a[l:h]$ changes only $d[l]$ (by $+\delta$) and $d[h]$ (by $-\delta$), and $a[i]$ is the prefix sum of $d$ up to $i$. Both operations are $O(\log n)$.

class RangeAddPointQuery:
    """Fenwick over the difference array."""

    def __init__(self, n):
        self.f = Fenwick(n + 1)

    def range_add(self, lo, hi, delta):    # data[lo:hi] += delta
        self.f.add(lo, delta)
        self.f.add(hi, -delta)

    def point(self, i):
        return self.f.prefix(i + 1)

Range update, range query

The prefix sum of $a$ is a sum of prefix sums of $d$:

$\sum_{j<i} a[j] = \sum_{j<i} \sum_{k \le j} d[k] = \sum_{k<i} d[k]\,(i - k) = i \sum_{k<i} d[k] - \sum_{k<i} k\, d[k]$

So keeping two Fenwick trees, one over $d[k]$ and one over $k\,d[k]$, gives prefix sums of $a$ in $O(\log n)$, and a range add updates two entries in each.

class RangeAddRangeSum:
    """Two Fenwick trees: prefix(i) = sum(B1, i) * i - sum(B2, i)."""

    def __init__(self, n):
        self.b1 = Fenwick(n + 1)
        self.b2 = Fenwick(n + 1)

    def range_add(self, lo, hi, delta):    # data[lo:hi] += delta
        self.b1.add(lo, delta)
        self.b1.add(hi, -delta)
        self.b2.add(lo, delta * lo)
        self.b2.add(hi, -delta * hi)

    def prefix(self, i):                   # sum of data[0:i]
        return self.b1.prefix(i) * i - self.b2.prefix(i)

    def range_sum(self, lo, hi):
        return self.prefix(hi) - self.prefix(lo)

This does the job of a lazy segment tree for “range add, range sum” in a fraction of the code. All three Fenwick variants were checked against a plain list.

2D Fenwick trees

The same idea nests: slot $(i, j)$ covers the rectangle $(i - \text{lowbit}(i), i] \times (j - \text{lowbit}(j), j]$, and both loops run independently. Updates and prefix queries are $O(\log n \log m)$, and any rectangle sum follows from four prefix rectangles by inclusion-exclusion.

    def add(self, x, y, delta):
        i = x + 1
        while i <= self.r:
            j = y + 1
            row = self.t[i]
            while j <= self.c:
                row[j] += delta
                j += j & -j
            i += i & -i

    def prefix(self, x, y):
        """Sum of the rectangle [0:x) x [0:y)."""
        s, i = 0, x
        while i > 0:
            j, row = y, self.t[i]
            while j > 0:
                s += row[j]
                j -= j & -j
            i -= i & -i
        return s

    def rect(self, x1, y1, x2, y2):
        """Sum of [x1:x2) x [y1:y2), by inclusion-exclusion."""
        return (self.prefix(x2, y2) - self.prefix(x1, y2)
                - self.prefix(x2, y1) + self.prefix(x1, y1))

Range Sum Query 2D - Mutable (LeetCode 308) is this structure.

Choosing a range structure, measured

On an array of 100,000 values, 20,000 operations, each either a point assignment or a range-sum query over a random range, with the share of updates varied (best of three runs):

The prefix-sum array here is given its best chance: an update only marks it stale, and the next query rebuilds it with itertools.accumulate, which runs in C. It is unbeatable with no updates and loses badly as soon as updates and queries interleave, because each rebuild is $O(n)$. The Fenwick tree is about twice as fast as the segment tree, with half the memory and a tenth of the code. The segment tree costs more but handles any associative operation and, with lazy tags, range updates of many kinds. Square root decomposition, $O(\sqrt n)$ per query, is the slowest of the three dynamic structures here, mostly because its queries loop over up to $2\sqrt n$ individual elements in Python; it gets faster as the share of queries falls, since its updates are $O(1)$.

Square root decomposition

Split the array into blocks of about $\sqrt n$ elements and keep one precomputed summary per block. A range query covers some whole blocks, answered from their summaries, plus at most two partial blocks at the ends, scanned element by element. There are at most $\sqrt n$ whole blocks and $2\sqrt n$ loose elements, so a query is $O(\sqrt n)$. A point update fixes one element and one block summary in $O(1)$.

class SqrtSum:
    def __init__(self, data):
        self.a = list(data)
        self.b = max(1, isqrt(len(self.a)))
        self.blocks = [sum(self.a[i:i + self.b]) for i in range(0, len(self.a), self.b)]

    def update(self, i, value):
        self.blocks[i // self.b] += value - self.a[i]
        self.a[i] = value

    def query(self, lo, hi):
        """Sum of a[lo:hi]."""
        s, b = 0, self.b
        while lo < hi and lo % b:          # ragged left edge
            s += self.a[lo]
            lo += 1
        while lo + b <= hi:                # whole blocks
            s += self.blocks[lo // b]
            lo += b
        while lo < hi:                     # ragged right edge
            s += self.a[lo]
            lo += 1
        return s

The choice of $\sqrt n$ balances the two costs: blocks of size $b$ give $n/b$ whole blocks and up to $2b$ loose elements, and $n/b + 2b$ is minimized near $b = \sqrt{n/2}$. When updates and queries have different costs, the best block size shifts accordingly.

The technique is slower than a segment tree for sums but much more flexible. Block summaries can be anything that is cheap to rebuild for one block: a sorted copy of the block (for “count elements less than $x$ in a range” with updates, $O(\sqrt n \log n)$ per query), a frequency table, or a lazy “add to the whole block” tag combined with a sorted copy. When it is not obvious how to merge two partial answers, which is what a segment tree requires, sqrt decomposition often still works. The same idea applied to a sequence of operations instead of an array, rebuilding a structure every $\sqrt q$ operations, is called sqrt decomposition on queries.

Mo’s algorithm

Some range queries have no good way to merge answers from two halves. “How many distinct values are in a[l..r]?” is one: the distinct counts of two halves do not determine the count of their union. But the answer is cheap to maintain for a sliding window: keep a count of each value in the window; adding an element increments its count (and the distinct total if the count became 1), removing decrements.

Mo’s algorithm answers $q$ such queries offline (all known in advance) by moving one window through all of them in a clever order, so the total movement is small. Divide positions into blocks of size $B$, and sort queries by the block of their left end, then by their right end. Within one block, the right pointer moves only forward, at most $n$ steps per block; the left pointer moves at most $B$ steps per query.

$\text{total moves} \approx \frac{n}{B} \cdot n + q \cdot B$

which is minimized at $B = n / \sqrt q$, giving $O(n \sqrt q)$ moves, or $O((n + q)\sqrt n)$ when $q \approx n$. A common refinement reverses the sort on the right end in alternate blocks, so the right pointer sweeps back down instead of jumping from $n$ to the start; it roughly halves the movement in practice.

def mo_distinct(a, queries):
    """Number of distinct values in a[l..r] (inclusive) for each query."""
    n = len(a)
    block = max(1, int(n / max(1, len(queries)) ** 0.5)) if queries else 1
    order = sorted(range(len(queries)),
                   key=lambda q: (queries[q][0] // block,
                                  queries[q][1] if (queries[q][0] // block) % 2 == 0
                                  else -queries[q][1]))
    freq = [0] * (max(a) + 1 if a else 1)
    distinct = 0
    cur_l, cur_r = 0, -1                   # current window a[cur_l..cur_r], empty
    ans = [0] * len(queries)
    for qi in order:
        l, r = queries[qi]
        while cur_r < r:
            cur_r += 1
            freq[a[cur_r]] += 1
            if freq[a[cur_r]] == 1:
                distinct += 1
        while cur_l > l:
            cur_l -= 1
            freq[a[cur_l]] += 1
            if freq[a[cur_l]] == 1:
                distinct += 1
        while cur_r > r:
            freq[a[cur_r]] -= 1
            if freq[a[cur_r]] == 0:
                distinct -= 1
            cur_r -= 1
        while cur_l < l:
            freq[a[cur_l]] -= 1
            if freq[a[cur_l]] == 0:
                distinct -= 1
            cur_l += 1
        ans[qi] = distinct
    return ans

The order of the four loops matters: the window is expanded before it is shrunk, so it never becomes “negative” (left past right), which would make the counts inconsistent. Values must be small non-negative integers to index freq; compress them first otherwise.

Measured on random arrays with values below $n/10$ and random ranges:

The fair comparison is with the last column, which does the same per-element work as Mo but restarts for each query: Mo is 26 times faster at 20,000. Even against the C-speed set of a slice, Mo is 15 times faster at 20,000 and 41 times at 100,000, because the naive total work grows as $nq$ and Mo’s as $n\sqrt q$. For 20,000 queries the window pointers moved 2,365,725 steps in total, against 100,376,266 elements summed over all the query ranges.

Limitations: queries must be known in advance, the add and remove operations must both be cheap, and updates to the array are not supported in the basic version (a variant with a third “time” dimension handles them, at $O(n^{5/3})$). When the answer can be merged, a segment tree is better, and distinct counting in particular also has an $O((n + q) \log n)$ offline solution with a Fenwick tree, by sorting queries by right end and keeping only the last occurrence of each value marked.

Interval trees

An interval tree stores intervals and finds those that overlap a query interval. Two closed intervals $[a, b]$ and $[c, d]$ overlap exactly when $a \le d$ and $c \le b$. Scheduling systems (which meetings conflict with this slot?), genome browsers (which genes overlap this region?), and memory managers (which mappings intersect this address range?) all ask this question. The Linux kernel has a generic interval tree built on its red-black trees, and PostgreSQL indexes range types with GiST, covered in PostgreSQL indexes.

Augmenting a BST

The version from Cormen and colleagues is a balanced BST keyed by the interval’s low endpoint, where each node also stores max_hi: the largest high endpoint anywhere in its subtree. That one extra field is enough to prune the search.

• Any overlap. At a node that does not overlap the query, go left if the left subtree’s max_hi is at least the query’s low end, otherwise go right. If the left subtree has a high endpoint that reaches the query, either something there overlaps, or nothing to the right can either (their low endpoints are even larger). One path, $O(\log n)$.
• All overlaps. Skip any subtree whose max_hi is below the query’s low end; skip a node’s right subtree when the node’s own low end is already past the query’s high end. Cost $O(k \log n)$ for $k$ results, or $O(k + \log n)$ with more careful structures.

max_hi must be recomputed on every structural change: insertion, deletion, and every rotation. Since each change only affects the nodes on one path (and the nodes involved in a rotation), maintenance is $O(\log n)$.

The implementation below balances with a treap, a BST in which each node also has a random priority kept in heap order. Insertion and deletion use split and merge, which are short, and the expected height is $O(\log n)$. The _pull function restores max_hi after any change below a node.

def _pull(n):
    m = n.hi
    if n.left and n.left.max_hi > m:
        m = n.left.max_hi
    if n.right and n.right.max_hi > m:
        m = n.right.max_hi
    n.max_hi = m


class IntervalTree:
    """Closed intervals [lo, hi], keyed by (lo, hi); a treap keeps it balanced
    in expectation. Duplicate intervals are allowed."""

    def __init__(self):
        self.root = None

    def insert(self, lo, hi):
        left, right = _split(self.root, (lo, hi))
        self.root = _merge(_merge(left, INode(lo, hi)), right)

    def delete(self, lo, hi):
        """Remove one copy of [lo, hi] if present."""
        left, rest = _split(self.root, (lo, hi))
        mid, right = _split(rest, (lo, hi), inclusive=True)   # mid: all copies of it
        if mid is not None:
            mid = _merge(mid.left, mid.right)       # drop mid's root
        self.root = _merge(_merge(left, mid), right)

    def any_overlap(self, qlo, qhi):
        """Some interval overlapping [qlo, qhi], or None. O(log n) expected."""
        n = self.root
        while n:
            if n.lo <= qhi and qlo <= n.hi:
                return (n.lo, n.hi)
            if n.left and n.left.max_hi >= qlo:
                n = n.left             # if anything overlaps, something on the left does
            else:
                n = n.right
        return None

    def all_overlaps(self, qlo, qhi):
        """Every interval overlapping [qlo, qhi]. O(k log n) expected."""
        out, stack = [], [self.root]
        while stack:
            n = stack.pop()
            if n is None or n.max_hi < qlo:          # nothing here reaches qlo
                continue
            stack.append(n.left)
            if n.lo <= qhi:                           # else n and its right side start too late
                if qlo <= n.hi:
                    out.append((n.lo, n.hi))
                stack.append(n.right)
        return out

_split(node, key) divides a treap into keys below key and the rest, and _merge(a, b) joins two treaps whose keys are in order; both recurse down one path and call _pull on the way back. The full code was checked against a list of live intervals through random sequences of insertions, deletions (including of absent intervals) and queries.

Other designs exist: the centered interval tree (Edelsbrunner) stores intervals at the node whose center point they contain, giving $O(\log n + k)$ queries for a static set; a segment tree over coordinates handles stabbing queries (“which intervals contain point $x$?”). For a one-off batch rather than a dynamic set, sorting by start and sweeping is simpler: that is how Merge Intervals and Meeting Rooms II are solved, and the greedy interval scheduling problem (choose the most non-overlapping intervals: sort by end, take each that starts after the last one taken) needs no tree at all; see chapter 16.

Quad trees

A quadtree (Finkel and Bentley, 1974) recursively divides a square region into four equal quadrants. There are several kinds, distinguished by what they store and when they split.

Point quadtrees for spatial indexing

A point-region quadtree holds points. Each leaf holds up to a small number of points; when a leaf overflows, it splits into four children and redistributes its points. Dense areas get deep, fine subdivisions; empty areas stay as single large leaves. A rectangle query visits only the quadrants that intersect the rectangle.

class QuadTree:
    """Point-region quadtree over a square [x0, x0+size) x [y0, y0+size).
    A leaf holds up to `capacity` points, then splits into four quadrants."""
    __slots__ = ("x0", "y0", "size", "capacity", "points", "kids")

    def __init__(self, x0, y0, size, capacity=8):
        self.x0, self.y0, self.size, self.capacity = x0, y0, size, capacity
        self.points = []
        self.kids = None

    def insert(self, p):
        node = self
        while node.kids is not None:
            node = node._child_for(p)
        node.points.append(p)
        if len(node.points) > node.capacity and node.size > 1e-9:
            node._split()

    def _child_for(self, p):
        half = self.size / 2
        i = (p[0] >= self.x0 + half) + 2 * (p[1] >= self.y0 + half)
        return self.kids[i]

    def _split(self):
        half = self.size / 2
        self.kids = [QuadTree(self.x0 + dx * half, self.y0 + dy * half, half, self.capacity)
                     for dy in (0, 1) for dx in (0, 1)]
        pts, self.points = self.points, []
        for p in pts:
            self.insert(p)                 # may split a child again if all land together

    def query(self, xlo, ylo, xhi, yhi, out):
        """Append every point with xlo <= x <= xhi and ylo <= y <= yhi."""
        stack = [self]
        while stack:
            n = stack.pop()
            if (n.x0 > xhi or n.x0 + n.size < xlo or
                    n.y0 > yhi or n.y0 + n.size < ylo):
                continue                   # square misses the query box
            if n.kids is None:
                out.extend(p for p in n.points
                           if xlo <= p[0] <= xhi and ylo <= p[1] <= yhi)
            else:
                stack.extend(n.kids)
        return out

The depth is not bounded by $\log n$: two points very close together force as many splits as it takes to separate them, and more than capacity identical points can never be separated. The size > 1e-9 guard stops that case; real implementations cap the depth and let the deepest leaves overflow.

Collision detection

Games and physics engines need every pair of objects that are close enough to collide. Checking all pairs is $O(n^2)$. With a quadtree, each object queries only the small box around itself (broad phase), and the exact test runs on the few candidates found (narrow phase). Finding all pairs of points within distance 1 among random points in a 1,000 × 1,000 square:

Five times the points made the all-pairs check 25 times slower and the quadtree about 6 times slower. For moving objects the tree must be rebuilt or updated every frame; with objects of similar size, a uniform grid (spatial hashing) is often simpler and faster, while a quadtree adapts better to uneven density.

Image compression with region quadtrees

A region quadtree represents an image: if a square block is all one color it becomes a leaf; otherwise it splits into four. Large uniform areas collapse into single leaves, and detail is only kept where the image has it.

def build_region(img, x, y, size):
    """img is a square 0/1 grid with side a power of two.
    Returns 0 or 1 for a uniform block, or a list of four sub-blocks (NW, NE, SW, SE)."""
    if size == 1:
        return img[y][x]
    h = size // 2
    kids = [build_region(img, x, y, h), build_region(img, x + h, y, h),
            build_region(img, x, y + h, h), build_region(img, x + h, y + h, h)]
    if all(k == 0 for k in kids):
        return 0
    if all(k == 1 for k in kids):
        return 1                           # merge four equal leaves into one
    return kids

For a black disk on white, the number of leaves grows with the length of the boundary, not with the area:

Each reconstruction was compared pixel by pixel with the original. Random noise has no uniform regions, so the tree is nearly as large as the image (and, counting internal nodes, larger). Construct Quad Tree (LeetCode 427) is this function. A lossy variant merges a block when its pixels are all within a tolerance of their mean.

Quadtrees can also answer nearest-neighbor queries (search the query’s quadrant first, then neighbors whose squares are closer than the best so far), but the k-d tree below does the same job in any dimension. The 3D version, dividing cubes into eight, is the octree, used in graphics and for 3D collision.

k-d trees

A k-d tree (Bentley, 1975) is a binary search tree over points in $k$ dimensions. Each level splits on one coordinate, cycling through the axes: the root splits by $x$, its children by $y$, and so on. Splitting at the median of the current axis gives a balanced tree.

def kd_build(points, depth=0):
    if not points:
        return None
    k = len(points[0])
    axis = depth % k
    points = sorted(points, key=lambda p: p[axis])
    mid = len(points) // 2
    return KDNode(points[mid], axis,
                  kd_build(points[:mid], depth + 1),
                  kd_build(points[mid + 1:], depth + 1))

Sorting at every level makes this $O(n \log^2 n)$; using linear-time median selection, or presorting once per axis, gives $O(n \log n)$. The tree has $\lceil \log_2(n+1) \rceil$ levels.

Range search (all points in an axis-aligned box) descends into a child only if the box reaches that side of the splitting plane. For a balanced 2D tree it visits $O(\sqrt n + k)$ nodes for $k$ results, and $O(n^{1 - 1/d} + k)$ in $d$ dimensions.

Nearest neighbor descends toward the query first (the side of each split it lies on), records the best distance found, then on the way back checks the other side of each split only if the splitting plane is closer than the current best, since otherwise nothing on that side can be closer.

def kd_nearest(root, q):
    """Nearest point to q by Euclidean distance. Returns (dist2, point, visited)."""
    best = [float("inf"), None]
    visited = 0

    def go(n):
        nonlocal visited
        if n is None:
            return
        visited += 1
        p = n.point
        d2 = sum((a - b) ** 2 for a, b in zip(p, q))
        if d2 < best[0]:
            best[0], best[1] = d2, p
        diff = q[n.axis] - p[n.axis]
        near, far = (n.left, n.right) if diff < 0 else (n.right, n.left)
        go(near)                            # the side q is on, first
        if diff * diff < best[0]:           # the ball crosses the splitting plane
            go(far)

    go(root)
    return best[0], best[1], visited

Comparing squared distances avoids square roots. Measured with 1,000 nearest-neighbor queries on uniform random 2D points:

Every k-d tree answer was compared with brute force (at 100,000 points, for the first 50 queries). Query time barely grows with $n$: a hundred times more points added about eight nodes per query.

The curse of dimensionality

The pruning test, “is the splitting plane closer than the best distance?”, stops working as dimensions grow. In high dimensions, distances between random points concentrate around the same value, so the nearest neighbor is not much nearer than a typical point, and the ball around the query crosses almost every splitting plane. With 20,000 uniform random points:

By 16 dimensions the tree is a slower brute-force search. The usual rule of thumb is that k-d trees pay off only when $n \gg 2^d$. For high-dimensional data such as text or image embeddings with hundreds of dimensions, exact nearest-neighbor search is effectively linear, and systems use approximate methods instead: graph-based indexes such as HNSW, inverted-file clustering, and product quantization. Ball trees and cover trees help in moderate dimensions and for non-Euclidean metrics. K Closest Points to Origin (LeetCode 973) is usually better solved with a heap or quickselect, since there is only one query.

Heavy-light decomposition

Segment trees answer queries on contiguous ranges of an array. Heavy-light decomposition (HLD) extends that to queries on paths in a tree: “sum (or max) of the values on the path from $u$ to $v$”, with values changing between queries. The heavy/light classification of edges comes from Sleator and Tarjan’s 1983 work on dynamic trees.

The idea

Root the tree. For each node, the child with the largest subtree is its heavy child, and the edge to it is heavy; edges to the other children are light. Following heavy edges partitions the tree into vertex-disjoint heavy chains.

The key property: moving down a light edge from $v$ to child $c$ means $c$‘s subtree has at most half the nodes of $v$‘s (otherwise $c$ would be the heavy child). So any root-to-node path crosses at most $\log_2 n$ light edges, and therefore passes through at most $\log_2 n + 1$ chains.

Now number the nodes with a DFS that always visits the heavy child first. Every heavy chain then occupies a contiguous range of positions. Put the node values into a segment tree in that order. A path from $u$ to $v$ splits into $O(\log n)$ pieces, each a contiguous piece of one chain, and each piece is one segment tree query of $O(\log n)$. Path queries cost $O(\log^2 n)$ and point updates $O(\log n)$.

            0
          //  \
         1     2          heavy edges drawn double
       //  \    \\
      3     4    5        chains: [0 1 3 6]  [4]  [2 5]
     //
     6                    positions: 0 1 3 6 -> 0..3,  4 -> 4,  2 5 -> 5..6

Here 0’s heavy child is 1 (subtree size 4 against 2), so 0–1 is heavy and 0–2 is light; each chain occupies consecutive positions.

Path queries

To query the path between $a$ and $b$: while they are on different chains, take whichever has the deeper chain head, query its chain from the head down to it, and jump to the head’s parent. Once both are on the same chain, query the stretch between them. The last node reached is also their lowest common ancestor.

    def path(self, a, b):
        """(sum, max) of node values on the path a..b."""
        s, m = 0, float("-inf")
        head, pos, depth, parent = self.head, self.pos, self.depth, self.parent
        while head[a] != head[b]:
            if depth[head[a]] < depth[head[b]]:
                a, b = b, a
            cs, cm = self._seg(pos[head[a]], pos[a])   # a's chain, up to its head
            s += cs
            m = max(m, cm)
            a = parent[head[a]]                        # jump over a light edge
        if depth[a] > depth[b]:
            a, b = b, a
        cs, cm = self._seg(pos[a], pos[b])             # same chain now
        return s + cs, max(m, cm)

The constructor (an iterative DFS for parents and depths, a reverse pass for subtree sizes and heavy children, and a second pass that lays out each chain contiguously) and the segment tree helper _seg are in the tested code; the full class is about 100 lines. It was checked on 200 random trees of up to 150 nodes, with random roots and labels, against walking the path explicitly, for both path sums and path maximums, with point updates interleaved, and its lca method against the parent-walking LCA.

Measured behavior

On two trees of 100,000 nodes, 2,000 random path-sum queries:

Both light-edge counts sit well under $\log_2 n = 16.6$. On the shallow random tree, walking the path directly is faster than HLD, because a path of about 20 nodes is cheaper to walk than several segment tree queries. HLD’s guarantee matters for deep trees, where the walk is 216 times slower here: its cost depends on the number of chains, not the length of the path.

Variants: values on edges rather than nodes are handled by storing each edge’s value at its lower endpoint and excluding the LCA in the final same-chain query. Subtree queries come free, since a subtree is also a contiguous range in this DFS order: $[\text{pos}(v), \text{pos}(v) + \text{size}(v))$. Range updates on paths use a lazy segment tree. For trees whose shape changes (edges added and removed), link-cut trees provide amortized $O(\log n)$ path operations; when only queries are needed and there are no updates, binary lifting with an aggregate per jump (chapter 10) is simpler.

Persistent data structures

A data structure is persistent if updates create new versions while leaving old versions intact and queryable. Partially persistent structures allow queries on any version but updates only to the newest; fully persistent ones allow updates to any version, producing a version tree; confluent ones can merge versions. Persistence is the norm in functional languages (an immutable list or map is persistent by construction), and it underlies undo histories, snapshot isolation, and version control. Driscoll, Sarnak, Sleator and Tarjan’s 1989 paper “Making Data Structures Persistent” laid out the general techniques.

Path copying

When a node changes, copy it, and copy every node on the path from the root to it, since each of them must point to a new child. Everything off the path is shared. In any tree with $O(\log n)$ height, an update costs $O(\log n)$ time and space, as measured above for the segment tree (17.6 new nodes per version). Persistent balanced BSTs work the same way, with rotations also copying the few nodes they touch. Immutable maps in Clojure and Scala, and the hash array mapped tries behind them, use path copying. The method requires that nodes have no parent pointers, since a parent pointer would force the whole tree to be copied.

Fat nodes

Instead of copying, let each node keep a list of (version, field, value) modifications. Reading a field at version $v$ finds the latest modification at or before $v$, a binary search. Space is $O(1)$ per change, but each access pays an $O(\log m)$ lookup for $m$ modifications. The node-copying method of the same paper combines the two: each node has room for a constant number of modifications, and when it fills up, it is copied, with the copy propagated to its parents. For structures whose nodes have bounded in-degree, this achieves $O(1)$ amortized extra space and time per update for partial persistence.

Typical uses of persistent segment trees beyond kth smallest: counting values in a range within a value interval, answering queries “as of time $t$” after a sequence of updates, and offline 2D counting problems, where one dimension becomes the version number.

Summary