XOR pair frequency queries?

Revision en1, by bihariforces, 2023-08-17 09:47:52

We are given an array of length $$$N$$$ and $$$Q$$$ queries (offline) where each query is a value $$$K$$$, for each query we need to count number of pairs in array with XOR $$$K$$$.

If $$$N$$$ and $$$Q$$$ can both be upto $$$10^5$$$, is it possible to answer these queries better than traversing entire array for each query?

An analogous version to count pairs with given sum uses FFT to precompute frequency every possible sum, which seems very difficult to do for XOR operation.

We can assume values in array are upto $$$10^5$$$ too, but if a solution exists which works for larger numbers too, that's preferable.

Tags query, xor, fft, counting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English bihariforces 2023-08-17 09:47:52 619 Initial revision (published)