Finger Tree, in depth: 2-3 finger trees, monoid measures, split and concatenation, a tested Python implementation and measured costs

The problem it solves

The finger tree is the only row that is cheap at both ends, cheap to join and cheap to cut, and it is cheapest near the ends. You pay with larger constants and more memory per element than an array. Compare a rope, which is tuned for text, and a size-annotated treap, which reaches every position in O(log n).

The shape: digits, nodes and a spine

FingerTree a = Empty | Single a
             | Deep (Digit a) (FingerTree (Node a)) (Digit a)
Digit a = one to four values;  Node a = Node2 a a | Node3 a a a

A Deep tree holds one to four elements in a prefix digit and one to four in a suffix digit. Everything in between lives in a middle tree whose elements are 2-3 nodes of values, whose own middle holds nodes of nodes, and so on. At depth d an element is a 2-3 tree of height d holding between 2^d and 3^d values, so the spine has O(log n) levels. The ends always sit in the shallowest digits. Those digits are the fingers, and they never move.

Why the ends are cheap, and when they are not

To push onto the front: if the prefix has fewer than four elements, prepend and stop. If it holds four (a, b, c, d) and you push e, keep (e, a) and push the 3-node (b, c, d) onto the middle tree. That push can overflow the next level in the same way, but after an overflow the prefix holds two elements, so the next pushes stop at the top. A credit argument that treats digits of size 2 or 3 as safe and 1 or 4 as dangerous gives amortised O(1). Popping is symmetric: an emptied digit borrows a node from the middle tree and unpacks it. Measured: building 100,000 elements with push_back allocated exactly 2.000 tree objects per push, and draining with view_left allocated 1.5 per pop.

The persistence trap. Amortisation assumes each version is consumed once. In a sequential build of 200,000 elements the costliest single push allocated 20 objects. Pushing 10,000 times onto that saved version cost 20.0 objects every time, ten times the amortised rate. Haskell avoids this because the middle tree is lazy: the cascade is a suspended computation that runs once and is shared by every version, and Hinze and Paterson's amortised bounds rely on it. In a strict language, accept O(log n) worst case per operation, make the middle field a memoised thunk, or use a worst-case design such as Kaplan and Tarjan's catenable deques, which are considerably more complex.

Measures: one skeleton, many structures

A measure is a monoid: a function from an element to a value, an associative combine, and its identity. Each node caches the combined measure of its contents in left-to-right order. Associativity lets concatenation regroup nodes without changing any cached answer. Split takes a monotone predicate, false on short prefixes and then true, and cuts where it first turns true.

Pairs of monoids are monoids, so one tree can serve several queries.

A tested implementation

Strict Python following the paper's structure. M is the measure, digits are tuples, and None is the empty tree. The tests ran exactly this code plus an allocation counter.

from functools import reduce

class Monoid:
    def __init__(self, zero, plus, leaf):
        self.zero, self.plus, self.leaf = zero, plus, leaf

class Node:
    __slots__ = ("v", "kids")
    def __init__(self, v, kids): self.v, self.kids = v, kids

class Single:
    __slots__ = ("x",)
    def __init__(self, x): self.x = x

class Deep:
    __slots__ = ("v", "pr", "mid", "sf")
    def __init__(self, v, pr, mid, sf): self.v, self.pr, self.mid, self.sf = v, pr, mid, sf

def ms(M, x):                                  # measure of anything
    if x is None: return M.zero
    if type(x) is Node or type(x) is Deep: return x.v
    if type(x) is Single: return ms(M, x.x)
    return M.leaf(x)

def msd(M, xs): return reduce(M.plus, (ms(M, x) for x in xs), M.zero)
def node(M, *kids): return Node(msd(M, kids), kids)
def deep(M, pr, mid, sf):
    return Deep(M.plus(msd(M, pr), M.plus(ms(M, mid), msd(M, sf))), pr, mid, sf)

def push_front(M, a, t):
    if t is None: return Single(a)
    if type(t) is Single: return deep(M, (a,), None, (t.x,))
    if len(t.pr) == 4:
        b, c, d, e = t.pr
        return deep(M, (a, b), push_front(M, node(M, c, d, e), t.mid), t.sf)
    return deep(M, (a,) + t.pr, t.mid, t.sf)

def push_back(M, t, a):
    if t is None: return Single(a)
    if type(t) is Single: return deep(M, (t.x,), None, (a,))
    if len(t.sf) == 4:
        e, d, c, b = t.sf
        return deep(M, t.pr, push_back(M, t.mid, node(M, e, d, c)), (b, a))
    return deep(M, t.pr, t.mid, t.sf + (a,))

def to_tree(M, xs):
    t = None
    for x in xs: t = push_back(M, t, x)
    return t

def view_left(M, t):                           # (head, rest) or None
    if t is None: return None
    if type(t) is Single: return t.x, None
    return t.pr[0], deep_l(M, t.pr[1:], t.mid, t.sf)

def view_right(M, t):                          # (rest, last) or None
    if t is None: return None
    if type(t) is Single: return None, t.x
    return deep_r(M, t.pr, t.mid, t.sf[:-1]), t.sf[-1]

def deep_l(M, pr, mid, sf):                    # pr may be empty: borrow a node
    if pr: return deep(M, pr, mid, sf)
    if mid is None: return to_tree(M, sf)
    n, mid2 = view_left(M, mid)
    return deep(M, n.kids, mid2, sf)

def deep_r(M, pr, mid, sf):
    if sf: return deep(M, pr, mid, sf)
    if mid is None: return to_tree(M, pr)
    mid2, n = view_right(M, mid)
    return deep(M, pr, mid2, n.kids)

def nodes(M, xs):                              # regroup 2..12 items into 2-3 nodes
    out = []
    while len(xs) > 4:
        out.append(node(M, *xs[:3])); xs = xs[3:]
    if len(xs) == 4: out += [node(M, *xs[:2]), node(M, *xs[2:])]
    else: out.append(node(M, *xs))
    return out

def app3(M, t1, ts, t2):
    if t1 is None:
        for x in reversed(ts): t2 = push_front(M, x, t2)
        return t2
    if t2 is None:
        for x in ts: t1 = push_back(M, t1, x)
        return t1
    if type(t1) is Single: return push_front(M, t1.x, app3(M, None, ts, t2))
    if type(t2) is Single: return push_back(M, app3(M, t1, ts, None), t2.x)
    mid = app3(M, t1.mid, nodes(M, list(t1.sf) + ts + list(t2.pr)), t2.mid)
    return deep(M, t1.pr, mid, t2.sf)

def concat(M, t1, t2): return app3(M, t1, [], t2)

def split_digit(M, p, i, xs):
    for j, x in enumerate(xs):
        i2 = M.plus(i, ms(M, x))
        if p(i2) or j == len(xs) - 1:
            return xs[:j], x, xs[j + 1:]
        i = i2

def split_tree(M, p, i, t):                    # t non-empty, p(i + ms(t)) true
    if type(t) is Single: return None, t.x, None
    vpr = M.plus(i, msd(M, t.pr))
    if p(vpr):
        l, x, r = split_digit(M, p, i, t.pr)
        return to_tree(M, l), x, deep_l(M, r, t.mid, t.sf)
    vm = M.plus(vpr, ms(M, t.mid))
    if p(vm):
        ml, xs, mr = split_tree(M, p, vpr, t.mid)
        l, x, r = split_digit(M, p, M.plus(vpr, ms(M, ml)), xs.kids)
        return deep_r(M, t.pr, ml, l), x, deep_l(M, r, mr, t.sf)
    l, x, r = split_digit(M, p, vm, t.sf)
    return deep_r(M, t.pr, t.mid, l), x, to_tree(M, r)

def split(M, p, t):
    if t is None: return None, None
    if not p(ms(M, t)): return t, None
    l, x, r = split_tree(M, p, M.zero, t)
    return l, push_front(M, x, r)

def find(M, p, i, t):                          # lookup without building trees
    if type(t) is Single: return i, t.x
    vpr = M.plus(i, msd(M, t.pr))
    if p(vpr): return in_digit(M, p, i, t.pr)
    vm = M.plus(vpr, ms(M, t.mid))
    if p(vm):
        j, n = find(M, p, vpr, t.mid)
        return in_digit(M, p, j, n.kids)
    return in_digit(M, p, vm, t.sf)

def in_digit(M, p, i, xs):
    for x in xs[:-1]:
        i2 = M.plus(i, ms(M, x))
        if p(i2): return i, x
        i = i2
    return i, xs[-1]

SIZE = Monoid(0, lambda a, b: a + b, lambda x: 1)
MAX = Monoid(float("-inf"), max, lambda x: x)

Indexing is find(SIZE, lambda v: v > k, 0, t)[1]. For a priority queue, split_tree(MAX, lambda v: v >= ms(MAX, t), float('-inf'), t) on [5, 1, 9, 3, 9, 2] returns [5, 1], 9, [3, 9, 2]: the leftmost maximum. Tested against Python lists: 300 random concatenate, split and index trials of up to 400 elements, 5,000 mixed end operations, and a check after each trial that the input versions were unchanged.

Worked example: splitting at index 4

Split Figure 1 with p = v > 4, so the left part should hold four elements.

1. Top level, i = 0. The prefix [0] brings the measure to 1, and p(1) is false. The middle tree brings it to 7, which is true, so the cut is inside the middle tree.
2. In the middle tree, from i = 1: node (1, 2, 3) reaches 4, which is false. Node (4, 5, 6) reaches 7, so that node holds the cut.
3. Split its children from i = 4. Element 4 reaches 5, which is true: l = (), x = 4, r = (5, 6).
4. The left side is deep_r([0], ...). Its suffix is empty, so it borrows the (1, 2, 3) node and gives [0] | [1, 2, 3]. The right side is deep_l((5, 6), empty, (7, 8, 9)) with 4 pushed back on: [4, 5, 6] | [7, 8, 9].

The work tracked the depth reached, not n, and positions near an end are reached in fewer levels.

Measured costs

CPython 3.13, a 100,000-element tree built with push_back, averaged over 2,000 to 20,000 random positions:

Write a non-allocating find for lookups, because split-based lookup was ten times slower. In Python the tree is about 40 times slower than a list for random reads and about 7 times faster for cut and join. Use it for persistence, splicing or both ends, not as a faster array.

Operational guidance

Prefer a library. Data.Sequence is the count-measured version, and Paterson's fingertree package on Hackage takes a custom measure. If you port it, decide up front whether old versions are reused. Keep measures small and immutable (integers or tuples of integers), since every node stores one. Track objects allocated per operation as well as time. More general patterns are in persistent data structures.

Failure modes

• Non-associative measure. Averages make cached values depend on tree shape, so splits go wrong after concatenation. Store sums and counts, and divide outside the tree.
• Non-monotone predicate. Split skips whole subtrees and misses the answer.
• Floating-point sums. Rounding breaks associativity. Use integers.
• Strict persistence. 20 objects per push instead of 2, as measured above.
• Values that are Node instances. ms tells nodes from elements by type, so wrap such values.
• Memory. Several objects per element, so measure resident memory before storing millions of small items.

Trade-offs

Choose a finger tree for both ends plus persistence plus splicing: an undo-friendly buffer, a versioned log split by time, or a functional deque. Choose a treap or skip list when middle updates dominate and old versions do not matter. Choose a rope for large text, and an array when random reads dominate.

What to do next

1. List your operations and their frequencies, and confirm that ends or split and concatenate actually matter.
2. Pick the measure, test associativity on random triples, and confirm the predicate is monotone.
3. Use Data.Sequence or fingertree if you can. If you port, start from the code above and keep a list-oracle test.
4. Set a persistence policy: a lazy middle tree, or O(log n) per operation with that worst case tested.
5. Benchmark a non-allocating lookup against split-based lookup and against an array at your real sizes.
6. Track objects per operation and resident memory in CI.