Smallest element after xor

Question

Starting with array of N positive integers, support Q queries. Each query contains a positive integer i. To answer the query, replace each element of the array with the result of xoring it with i, then output the earliest index of the smallest element in the array. Each query changes the array.

I could only come up with O(N*Q). I try to think of range update data structure but xor can make number bigger so I don't think it's right way.

How to solve faster?

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    int Q;
    cin >> Q;
    for (int j = 0; j < Q; j++) {
        int i;
        cin >> i;
        for (int k = 0; k < N; k++) {
            A[k] = A[k] ^ i;
        }
        int mini = 0;
        for (int k = 0; k < N; k++) {
            if (A[k] < A[mini]) {
                mini = k;
            }
        }
        cout << mini << '\n';
    }
    return 0;
}

Example input

5
1 2 3 4 5
3
1
2
6

Example output

0
2
4

Example output explanation

First query is 1. After xor array with 1, it becomes 0 3 2 5 4. Smallest number: index 0

Second query is 2. After xor previous array with 2, it becomes 2 1 0 7 6. Smallest number: index 2

Second query is 6. After xor previous array with 6, it becomes 4 7 6 1 0. Smallest number: index 4

Answer 1

Represent the elements in the array as fixed-width binary numbers (ie: sequences of 0 and 1 bits), most significant bit first. Construct a binary trie from them, storing the array index in the trie at the bottom.

If the fixed width is W, any single query can be answered in O(W) time; as you descend down the trie, if there's a single branch follow it, otherwise go down the "0" branch if the xor value has a "0" bit in that position, otherwise go with the "1" branch.

The intuition here is easy; if there's even one element in the array that has the same most significant bit as the xor value, the smallest element in the array must be one of those elements. And then so on for the next significant bit. The trie makes finding these sets efficient.

To run successive queries, instead of updating the datastructure, query against the running XOR of the queries so far. So if the queries are Q1, Q2, Q3, Q4..., then instead query Q1, Q1^Q2, Q1^Q2^Q3, Q1^Q2^Q3^Q4, ... (where ^ is XOR). That means you don't have to update the trie at all.