hackercupai/hackercup huggingface dataset:
Having to now deal with updates on numbers up to \(10^6\), we can no longer use prefix sums as in chapter 1. Instead, let's consider a hashing approach. We'll need a hash function defined over subarrays, some \(h(A_{l..r})\) that is only sensitive to the frequency of its input values (i.e. is agnostic to the order they are in), along with a strategy to update the hashes and quickly query the hash of any subarray. Most importantly, we should be able to compare the two hashes and deduce whether their corresponding subarrays differ by exactly one number.

One strategy is to first pick your favorite hash function \(h : [1, 10^6] \to [0, P)\) on a single integer, where \(P\) is some large prime number, then define \(h(A_{l..r}) := (h(A_l) + \ldots + h(A_r)) \text{ mod } P\). It can be shown that the sum of uniformly distributed random variables mod \(P\) is itself uniformly distributed mod \(P\). Now, given two subarrays \(A_{l1..r1}\) and \(A_{l2..r2}\) with the same value frequencies except \(A_{l1..r1}\) having one extra number \(v\), we have \(h(A_{l1..r1}) - h(A_{l2..r2}) \equiv h(v) \; (\text{mod } P)\).

We can maintain a segment tree of the hashes of each \(A_i\), supporting updates and range queries for the modded sum of hashes in \(\mathcal{O}(\log N\)\) time. We can also precompute a lookup table of each \(h(A_i)\) to \(A_i\). For each query \(A_{l..r}\), again let \(m = \lfloor(l + r)/2\rfloor\). Then, we can calculate the two hash differences \(h(A_{m..r}) - h(A_{l..(m-1)})\) and \(h(A_{l..m}) - h(A_{(m+1)..r})\), checking if either one corresponds to an original value of \(A\) using the lookup table.

One concern is that if the subarrays do not differ by exactly one number, then the difference of the hashes will be garbage. It's possible for us to be unlucky and get garbage that maps back to a value in \(A\). There are ~\(10^{6}\) queries and ~\(10^{19}\) possible hash values if we hash to a \(64\)-bit range. The chances of a collision for a single hash would be \(10^{6-19} = 10^{-13}\). The chances of at least one collision across any of the \(10^6\) queries would be roughly \(1 - \left(1-10^{-13}\right)^{10^6} \approx 10^{-7}\). With a good base hash function and seed, this should already be good enough, but in theory we can be more certain by maintaining two hash functions modulo two different primes to cross-check.

[See David Harmeyer's solution video here.](https://www.youtube.com/watch?v=w65VekVkuHA)