How to get the minimum XOR of a given value and the value from a query of range for a given array

Given an array A of n integers and given queries in the form of range [l , r] and a value x, find the minimum of A[i] XOR x where l <= i <= r and x will be different for different queries.

I tried solving this problem using segment trees but I am not sure what type of information I should store in them as x will be different for different queries.

0 < number of queries <= 1e4

0 < n <= 1e4 

I was able to solve this using segment tree and tries as suggested by @David Eisenstat

Below is an implementation in c++. I constructed a trie for each segment in the segment tree. And finding the minimum xor is just traversing and matching the corresponding trie using each bit of the query value (here)

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < b; i++)
using namespace std;

const int bits = 7;

struct trie {
    trie *children[2];
    bool end;
};

trie *getNode(void)
{
    trie *node        = new trie();
    node->end         = false;
    node->children[0] = NULL;
    node->children[1] = NULL;
    return node;
}

trie *merge(trie *l, trie *r)
{
    trie *node = getNode();
    // Binary 0:
    if (l->children[0] && r->children[0])
        node->children[0] = merge(l->children[0], r->children[0]);

    else if (!r->children[0])
        node->children[0] = l->children[0];

    else if (!l->children[0])
        node->children[0] = r->children[0];

    // Binary 1:
    if (l->children[1] && r->children[1])
        node->children[1] = merge(l->children[1], r->children[1]);

    else if (!r->children[1])
        node->children[1] = l->children[1];

    else if (!l->children[1])
        node->children[1] = r->children[1];

    return node;
}

void insert(trie *root, int num)
{
    int mask = 1 << bits;
    int bin;
    rep(i, 0, bits + 1)
    {
        bin = ((num & mask) >> (bits - i));
        if (!root->children[bin]) root->children[bin] = getNode();
        root = root->children[bin];
        mask = mask >> 1;
    }

    root->end = true;
}

struct _segTree {
    int n, height, size;
    vector<trie *> tree;

    _segTree(int _n)
    {
        n      = _n;
        height = (int)ceil(log2(n));
        size   = (int)(2 * pow(2, height) - 1);
        tree.resize(size);
    }

    trie *construct(vector<int> A, int start, int end, int idx)
    {
        if (start == end) {
            tree[idx] = getNode();
            insert(tree[idx], A[start]);
            return tree[idx];
        }

        int mid   = start + (end - start) / 2;
        tree[idx] = merge(construct(A, start, mid, 2 * idx + 1),
                          construct(A, mid + 1, end, 2 * idx + 2));
        return tree[idx];
    }

    int findMin(int num, trie *root)
    {
        int mask = 1 << bits;
        int bin;

        int rnum = 0;
        int res  = 0;

        rep(i, 0, bits + 1)
        {
            bin = ((num & mask) >> (bits - i));

            if (!root->children[bin]) {
                bin = 1 - bin;
                if (!root->children[bin]) return res ^ num;
            }

            rnum |= (bin << (bits - i));
            root = root->children[bin];
            if (root->end) res = rnum;
            mask = mask >> 1;
        }
        return res ^ num;
    }

    int Query(int X, int start, int end, int qstart, int qend, int idx)
    {
        if (qstart <= start && qend >= end) return findMin(X, tree[idx]);

        if (qstart > end || qend < start) return INT_MAX;

        int mid = start + (end - start) / 2;
        return min(Query(X, start, mid, qstart, qend, 2 * idx + 1),
                   Query(X, mid + 1, end, qstart, qend, 2 * idx + 2));
    }
};

int main()
{
    int n, q;
    vector<int> A;
    vector<int> L;
    vector<int> R;
    vector<int> X;

    cin >> n;
    A.resize(n, 0);

    rep(i, 0, n) cin >> A[i];

    cin >> q;
    L.resize(q);
    R.resize(q);
    X.resize(q);
    rep(i, 0, q) cin >> L[i] >> R[i] >> X[i];

    //---------------------code--------------------//

    _segTree segTree(n);
    segTree.construct(A, 0, n - 1, 0);

    rep(i, 0, q)
    {
        cout << segTree.Query(X[i], 0, n - 1, L[i], R[i], 0) << " ";
    }

    return 0;
}

Time complexity : O((2n - 1)*k + qklogn)

Space complexity : O((2n - 1)*2k)

k -> number of bits