Module sparse 

SparseList<T, N> — a list view that may omit materializing parts of the tree, using cached subtree roots or zero-hashes for empty regions.

The hash tree root is byte-identical to a fully-materialised List<T, N> with the same effective contents. The algorithm walks the implicit balanced binary tree of depth ceil_log2(N) iteratively, using a fixed-size stack — never materialising the full N leaves.

Storage

Both inner maps are sorted Vecs keyed by u64. Sorted Vec gives us:

• O(log n) lookup via binary_search_by_key.
• O(n) insert/remove at the sorted position. For the cnode-slot use case (N ≤ 256, typically very sparse), the linear shift is trivial.
• O(log n) range queries via partition_point, used by compute_subtree_root to short-circuit empty subtrees.
• Iteration in sorted order, byte-equivalent to BTreeMap::iter.

Structs

SparseList

A list with a maximum length of N that exposes its tree structure for sparse fill-in: materialized indices, cached subtree roots, or implicit zero-hashes for never-written regions.