C++ Tìm số tối ưu hóa tổng XOR với mảng con trong khoảng

Cho mảng và các truy vấn [L,R]. Tìm số x sao cho tổng XOR của x với các phần tử trong khoảng là lớn nhất. Ví dụ:

Input: A={20,11,18,2,13}, queries: (1,3), (3,5), (2,4)
Output: 2147483629, 2147483645, 2147483645

Phương pháp giải

Tiền tính prefix_count[i][b] = số bit 1 tại vị trí b trong prefix[1..i]. Với truy vấn [L,R], số bit 1 tại vị trí b = prefix[R][b] - prefix[L-1][b]. Để tối đa tổng XOR: nếu bit 1 chiếm đa số → đặt bit x = 0, ngược lại đặt bit x = 1. Khởi tạo x = 2³¹-1 (tất cả bit 1), tắt bit nơi 1 chiếm đa số.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

#define MAX 2147483647
int prefix[100001][32];

void prefix_bit(int A[], int n) {
    for (int j=0; j<32; j++) prefix[0][j] = 0;
    for (int i=1; i<=n; i++) {
        int a = A[i-1];
        for (int j=0; j<32; j++) {
            int x = 1 << j;
            if (a & x) prefix[i][j] = 1 + prefix[i-1][j];
            else prefix[i][j] = prefix[i-1][j];
        }
    }
}

int maximum_num(int l, int r) {
    int bits = r - l + 1;
    int X = MAX;
    for (int i=0; i<31; i++) {
        int ones = prefix[r][i] - prefix[l-1][i];
        if (ones >= bits - ones) {
            X ^= (1 << i);
        }
    }
    return X;
}

int main() {
    int n=5, q=3;
    int A[] = {210,11,48,22,133};
    int L[] = {1,4,2}, R[] = {3,14,4};
    prefix_bit(A, n);
    for (int i=0; i

Kết quả
2147483629 2147483647 2147483629

Giải thích
Prefix bit count cho phép trả lời truy vấn O(32). X tối đa khi bit x ngược với bit đa số trong khoảng.

Kết luận
Đã giải bài toán tối đa tổng XOR trong khoảng bằng prefix bit count. Code C++ áp dụng cho C, Java, Python. Hy vọng hữu ích.