974. Counting Values With a Given Run of Top Bits

You are given n values, written as 30 bit strings from bit 29 down to bit 0, then q queries. Each query is a string of 0 and 1 characters. Print how many of the stored values START with that exact run of bits.

``` values 1, 2, 3, 1073741823 0 -> 3 1, 2 and 3 all have a 0 at bit 29 1 -> 1 only 1073741823 has a 1 there 00 -> 3

values 536870912, 536870913 1 -> 2 11 -> 0 both have a 0 at bit 28 ```

## This is problem 936 in binary

936 counts the words under a prefix by keeping, at every node, how many words passed through it. Nothing about that argument mentions letters, so it works unchanged here: keep a counter at each node of the binary trie, increment it on every insertion that passes through, and the answer to a query is the counter at the node the query leads to.

``` insert v: node = root for b from 29 down to 0: step into child (v >> b) & 1, creating it if needed, then cnt[node] += 1

query p: node = root for each character c of p: if child[node][c] is absent: print 0 and stop node = child[node][c] print cnt[node] ```

## Why the counter is the answer

A stored value passes through the node at depth d that spells its top d bits, and through no other node at that depth. So the counter at a node is exactly the number of stored values whose top d bits are that node's string, which is the question.

Counting by hand instead, by comparing each query against each value, is q * n * 30 bit tests, which at the limits is 3 * 10^11.

## The bits are in a different order from the digits

The query reads left to right and the bits run from position 29 downwards, so the first character of the query is bit 29 and not bit 0. Reading the value with (v >> b) & 1 for b counting DOWN is what keeps the two in step. Building the value's bit string with b counting up, which is the natural loop to write, reverses it and produces answers that are wrong in a way that looks random.

## The two boundaries

A query no stored value matches must print 0, which happens when the walk falls off the trie. Printing the counter of the node the walk stopped at instead gives a non-zero count for a pattern nothing has.

A query of the full 30 characters asks for values EQUAL to that bit string, which is the exact-membership question, and the counter at the last node is how many copies are stored.

## Cost

Building is O(30 n). Each query costs its own length, at most 30 steps. Space is at most 1 + 30 n = 3000001 nodes. Nothing here overflows: the largest count is n, which is 100000.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ q ≤ 100000` - `0 ≤ each value ≤ 1073741823`, which is `2^30 - 1` - Every pattern is 1 to 30 characters, each `0` or `1`. - Values may repeat.