# X Fast Trie Search

# X Fast Trie Search

X fast trie search looks up an integer key from a fixed word universe by combining a binary trie with hash tables over prefixes.

A normal binary trie follows one bit at a time. An X fast trie accelerates this process by storing every prefix length in a hash table. This allows the search to find the deepest existing prefix by binary search over prefix length.

## Problem

Given an X fast trie storing integer keys with word size $w$, decide whether a target key `x` is present.

Return true if `x` exists, otherwise false.

## Structure

An X fast trie stores keys as fixed width binary strings.

For word size $w$, each key has bits:

$$
b_0 b_1 \cdots b_{w-1}
$$

The data structure maintains:

| component          | purpose                                  |
| ------------------ | ---------------------------------------- |
| binary trie        | represents prefixes of stored keys       |
| prefix hash tables | map prefixes at each depth to trie nodes |
| linked leaves      | store all keys in sorted order           |
| jump pointers      | help locate predecessor or successor     |

For exact membership, the deepest prefix of length $w$ is the full key.

## Algorithm

Check whether the full key appears in the hash table for depth $w$.

For predecessor or successor search, the structure first finds the longest existing prefix using binary search over depths. Exact membership is simpler because the full length prefix is enough.

```text id="xf0p2k"
x_fast_trie_member(T, x):
    prefix = bits(x, T.word_size)

    if prefix in T.level[T.word_size]:
        return true

    return false
```

For the more general search path:

```text id="xf1m8q"
x_fast_trie_deepest_prefix(T, x):
    lo = 0
    hi = T.word_size

    while lo < hi:
        mid = (lo + hi + 1) // 2
        p = prefix(x, mid)

        if p in T.level[mid]:
            lo = mid
        else:
            hi = mid - 1

    return lo
```

## Example

Use word size $w = 4$.

Stored keys:

| decimal | bits   |
| ------: | ------ |
|       3 | `0011` |
|       9 | `1001` |
|      12 | `1100` |

Search for `9`. Its full binary key is `1001`.

| depth | prefix |
| ----: | ------ |
|     1 | `1`    |
|     2 | `10`   |
|     3 | `100`  |
|     4 | `1001` |

Since prefix `1001` exists at depth `4`, the key is present.

## Correctness

Every stored key appears as a leaf in the binary trie. The hash table at depth $w$ contains exactly the full length prefixes of stored keys.

If the lookup finds the full bit string for `x`, then a leaf for `x` exists, so the key is present. If the full bit string is absent, no stored key has exactly the same $w$ bits, so `x` is absent.

The deepest prefix routine is correct because prefixes are monotone by depth. If a prefix of length $d$ exists for `x`, then every shorter prefix also exists. Therefore binary search over prefix length finds the maximum existing depth.

## Complexity

Let $w$ be the number of bits in the universe.

| operation                | expected time |
| ------------------------ | ------------- |
| exact membership         | $O(1)$        |
| deepest prefix search    | $O(\log w)$   |
| predecessor or successor | $O(\log w)$   |

Space usage is:

$$
O(nw)
$$

because every stored key may contribute one prefix per level.

## When to Use

X fast tries are useful for bounded integer keys when fast predecessor, successor, and membership operations are needed.

They are appropriate when:

* keys are fixed width integers
* expected hash table performance is acceptable
* memory overhead of storing many prefixes is acceptable
* ordered operations are needed faster than comparison tree bounds

For lower memory usage, a Y fast trie is often preferred.

## Implementation

```python id="xf2v7r"
class XFastTrie:
    def __init__(self, word_size):
        self.word_size = word_size
        self.level = [set() for _ in range(word_size + 1)]

    def bits(self, x, length):
        shift = self.word_size - length
        return x >> shift if length > 0 else 0

    def insert_key_prefixes(self, x):
        for depth in range(self.word_size + 1):
            self.level[depth].add(self.bits(x, depth))

    def member(self, x):
        return self.bits(x, self.word_size) in self.level[self.word_size]

    def deepest_prefix(self, x):
        lo = 0
        hi = self.word_size

        while lo < hi:
            mid = (lo + hi + 1) // 2
            p = self.bits(x, mid)

            if p in self.level[mid]:
                lo = mid
            else:
                hi = mid - 1

        return lo
```

```go id="xf3n6d"
type XFastTrie struct {
	WordSize int
	Level    []map[uint64]bool
}

func NewXFastTrie(wordSize int) *XFastTrie {
	level := make([]map[uint64]bool, wordSize+1)

	for i := range level {
		level[i] = make(map[uint64]bool)
	}

	return &XFastTrie{
		WordSize: wordSize,
		Level:    level,
	}
}

func (t *XFastTrie) Prefix(x uint64, length int) uint64 {
	if length == 0 {
		return 0
	}

	shift := t.WordSize - length
	return x >> shift
}

func (t *XFastTrie) InsertKeyPrefixes(x uint64) {
	for depth := 0; depth <= t.WordSize; depth++ {
		t.Level[depth][t.Prefix(x, depth)] = true
	}
}

func (t *XFastTrie) Member(x uint64) bool {
	p := t.Prefix(x, t.WordSize)
	return t.Level[t.WordSize][p]
}

func (t *XFastTrie) DeepestPrefix(x uint64) int {
	lo, hi := 0, t.WordSize

	for lo < hi {
		mid := lo + (hi-lo+1)/2
		p := t.Prefix(x, mid)

		if t.Level[mid][p] {
			lo = mid
		} else {
			hi = mid - 1
		}
	}

	return lo
}
```