Fractional Cascading, in depth: searching k sorted lists in O(log n + k), the one-step proof, a tested implementation and layered range trees

The problem and the naive bounds

Call the lists catalogs L0, L1, ..., L(k-1). For a query x we want, in each catalog, the index of the first element that is at least x (the successor, or bisect_left in Python terms). Two naive approaches bracket the problem:

• Search each list. O(n) space, O(k log n) per query. Simple, and for small k often fine.
• Merge everything. Build one sorted array of all n values and store, for every position, the answer index in all k catalogs. One binary search then answers everything in O(log n + k), but the table needs O(nk) space, which is hopeless when k is large.

Fractional cascading gets the query time of the second approach with the space of the first. The insight is that you do not need to merge everything into level 0. You only need enough of level i+1 inside level i that, once you know where x falls in level i, you know almost exactly where it falls in level i+1.

Augmented catalogs and bridges

Build augmented catalogs M from the bottom up. The last one is just the last catalog: M(k-1) = L(k-1). For each earlier level, M(i) is L(i) merged with every second element of M(i+1). The promoted elements are samples of the level below; they let a position in M(i) act as a bridge into M(i+1). Note that we sample from M(i+1), not from L(i+1): elements cascade upward through several levels, halving each time, which is where the name comes from.

Each entry of M(i) stores two integers. own: the index in L(i) of the first element of L(i) that is at least this entry's value, which is the answer for level i. down: the index in M(i+1) of the first element at least this entry's value, which is the bridge. Add a sentinel entry at the end of every M(i) for queries larger than everything.

Space is linear. |M(i)| = |L(i)| + floor(|M(i+1)| / 2), and unrolling the recurrence gives |M(i)| at most |L(i)| + |L(i+1)|/2 + |L(i+2)|/4 + ..., so the total over all levels is at most 2n plus the k sentinels.

Why one step back is enough

The query does one binary search in M0 to find j, the first position whose value is at least x. It reads own[0][j] for level 0. Then, at each level, it jumps to down[i][j] in M(i+1) and checks whether the element just before it is also at least x; if so, it steps back once. Why is one step always enough?

Let y = M(i)[j], the smallest element of M(i) that is at least x, and let t be the true successor position of x in M(i+1). The bridge d = down[i][j] is the successor position of y in M(i+1). Since x is at most y, t is at most d. Every element of M(i+1) at positions t to d-1 is at least x and strictly less than y. If any of them had been promoted, it would also sit in M(i), be at least x and smaller than y, contradicting the choice of y. So positions t to d-1 contain no promoted element. Promoted elements are every second position, so a run of consecutive unpromoted positions has length at most one. Hence d - t is 0 or 1. The same argument covers the sentinel case where x exceeds all of M(i).

That proof is the whole technique. If you promote every third element instead, the gap can be two and you step back up to twice; promoting a fraction 1/b gives space about n * b/(b-1) and up to b-1 back-steps per level. Every second element is the usual choice.

Implementation

The implementation below favours clarity: it builds own and down with bisect_left, which costs O(n log n). A production build replaces each bisect with a linear merge pass and gets O(n) construction. It was checked against independent binary searches on thousands of random inputs, including duplicates and empty lists.

from bisect import bisect_left

class FractionalCascade:
    def __init__(self, lists):
        self.L = [list(l) for l in lists]          # each must be sorted
        k = len(self.L)
        self.M = [None] * k
        self.own = [None] * k                      # own[i][j]: answer index in L[i]
        self.down = [None] * k                     # down[i][j]: bridge index into M[i+1]
        self.M[k - 1] = self.L[k - 1][:]
        self.own[k - 1] = list(range(len(self.L[k - 1]) + 1))
        for i in range(k - 2, -1, -1):
            nxt = self.M[i + 1]
            m = sorted(self.L[i] + nxt[1::2])      # promote every second element of M[i+1]
            self.M[i] = m
            probe = m + [float("inf")]             # sentinel for x above everything
            self.own[i] = [bisect_left(self.L[i], v) for v in probe]
            self.down[i] = [bisect_left(nxt, v) for v in probe]

    def search(self, x):
        j = bisect_left(self.M[0], x)              # the only O(log n) step
        out = []
        for i in range(len(self.L)):
            out.append(self.own[i][j])
            if i + 1 == len(self.L):
                break
            j = self.down[i][j]
            if j > 0 and self.M[i + 1][j - 1] >= x:   # at most one step back
                j -= 1
        return out                                  # out[i] == bisect_left(L[i], x)

Duplicates are handled because both own and down use successor (first element at least v) semantics consistently, and the back-step test uses greater-or-equal. Mixing bisect_left in one place with bisect_right in another is the most common way to break this code.

Worked example

Take four catalogs: L0 = [3, 11, 19, 31, 40], L1 = [7, 15, 22, 29], L2 = [2, 14, 25, 33, 38], L3 = [9, 18, 27]. Building bottom-up: M3 = [9, 18, 27]. M2 promotes 18 from M3, giving [2, 14, 18, 25, 33, 38]. M1 promotes 14, 25 and 38 from M2, giving [7, 14, 15, 22, 25, 29, 38]. M0 promotes 14, 22 and 29 from M1, giving [3, 11, 14, 19, 22, 29, 31, 40]. Note 14 has cascaded up from L2 through two levels.

Query x = 24. Binary search in M0 finds j = 5 (value 29). own gives index 3 in L0, which is 31, correct. The bridge from 29 points to position 5 in M1 (value 29); the element before it, 25, is also at least 24, so step back to j = 4. own gives index 3 in L1, which is 29, correct. The bridge from 25 points to position 3 in M2 (value 25); the element before is 18, below 24, so stay. own gives index 2 in L2, which is 25. The bridge from 25 points to position 2 in M3 (value 27); 18 before it is too small, so the answer is index 2, value 27. Four answers from one binary search and three constant-time hops: [3, 3, 2, 2].

Where it is used

The technique pays off wherever a search walks a path of nodes that each hold a sorted list of the same keys:

• Layered range trees. A 2D range tree stores, at each node of a tree on x, the points of its subtree sorted by y. A rectangle query visits O(log n) nodes and binary-searches y at each, for O(log^2 n + m) time with m reported points. Cascading the y-lists from each node to its children (Willard and Lueker's layered range tree) drops it to O(log n + m) with the same O(n log n) space.
• Merge sort trees. Counting values below v in an index range touches O(log n) nodes, each holding a sorted list; with bridges between parent and child lists one search at the root answers all of them. Merge sort tree shows this inside a full structure.
• Planar point location. Searching a hierarchy of separating chains naively costs O(log^2 n); with fractional cascading (Edelsbrunner, Guibas and Stolfi) it becomes O(log n).
• Segment trees over intervals. Stabbing and intersection queries that look up the same coordinate in node lists along a root-to-leaf path; see segment trees for geometry and segment tree basics.

In tree structures the cascade runs from each node into both children, which is the general form: Chazelle and Guibas define it on any catalog graph of bounded degree, where a search along a path of length p costs O(log n + p) after the first search, with each node sampling from all its neighbours. Mehlhorn and Naher later gave a dynamic version supporting inserts and deletes, with a log log n factor per level; most practical code stays static and rebuilds.

Engineering in practice

Asymptotics and wall-clock time disagree more here than in many algorithms. With k = 4 lists of a million integers, four branchless binary searches cost around 80 comparisons and a handful of cache misses each; fractional cascading replaces three of them with one hop and one comparison, but each hop is a dependent random access into another array, also likely a cache miss. The benefit grows with k and with the cost of comparisons (strings, composite keys), and it is decisive inside structures like range trees where k is itself log n and the alternative multiplies logs. For tiny k, or when the lists fit in L1 cache, plain searches usually win.

Layout matters. Store value, own and down in parallel arrays or packed structs so a hop touches one cache line; use 32-bit indices; build in one pass with merges. If you query many keys in sorted order, a simpler alternative may beat both: walk all k lists with advancing pointers, which is O(n + q k) with perfectly sequential access.

Common bugs

Test the structure exactly as its proof suggests: random lists with heavy duplicates, empty lists, queries below the minimum and above the maximum, compared against independent bisect_left calls. A few thousand random cases find every bug in the table above.

What to do next

1. Check that your workload really searches one key in many sorted lists; count k and n.
2. Benchmark plain branchless binary searches first; adopt cascading only if k or comparison cost is large.
3. Implement the static version above and test it against bisect on random data with duplicates.
4. Replace the bisect-based build with linear merges and parallel arrays for production.
5. If you have a range tree or merge sort tree, add parent-to-child bridges and measure the query time drop.
6. Read Chazelle and Guibas's paper for the graph version before generalising beyond paths and trees.
7. Continue with persistent segment trees for another way to answer range order statistics.