Range bitwise properties (Bit Manipulation Sub-pattern)

// XOR of a[l..r] in O(1) after O(N) setup: the shared prefix cancels.
struct PrefixXor {
    vector<int> p;                            // p[i] = a[0] ^ ... ^ a[i-1], p[0] = 0
    PrefixXor(const vector<int>& a) : p(a.size() + 1, 0) {
        for (size_t i = 0; i < a.size(); i++) p[i + 1] = p[i] ^ a[i];
    }
    int query(int l, int r) const { return p[r + 1] ^ p[l]; }
};

// AND of every number in [left, right] = their common binary prefix.
// Each lower bit is 0 somewhere in the range, so it becomes 0.
int rangeAnd(int left, int right) {
    int shift = 0;
    while (left != right) { left >>= 1; right >>= 1; shift++; }
    return left << shift;
}

// Largest group with AND > 0: the group must share one bit, so count per bit.
int largestSharingABit(const vector<int>& a) {
    int best = 0;
    for (int b = 0; b < 31; b++) {
        int cnt = 0;
        for (int v : a) cnt += (v >> b) & 1;
        best = max(best, cnt);
    }
    return best;
}