Tổng XOR của tất cả các mảng con trong C++

Trong bài toán này, chúng ta được cho một mảng arr[] gồm n số. Nhiệm vụ là viết chương trình tìm tổng XOR của tất cả các mảng con (subarray) của mảng đó.

Ví dụ minh họa

Input: arr[] = {5, 1, 4}
Output: 19
Giải thích:
XOR {5} = 5
XOR {1} = 1
XOR {4} = 4
XOR {5, 1} = 5^1 = 4
XOR {1, 4} = 1^4 = 5
XOR {5, 1, 4} = 5^1^4 = 0
Tổng = 5 + 1 + 4 + 4 + 5 + 0 = 19

Cách đơn giản là dùng vòng lặp lồng nhau để duyệt tất cả các mảng con, tính XOR từng mảng con và cộng dồn. Tuy nhiên, cách này có độ phức tạp thời gian O(n³) (hoặc O(n²) nếu tính XOR tích lũy), không hiệu quả với mảng lớn.

Phương pháp tối ưu: Mảng tiền tố XOR (Prefix XOR)

Xây dựng mảng prefixXOR sao cho:

prefixXOR[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]

Khi đó, XOR của mảng con từ chỉ số i đến j (với i ≤ j) được tính như sau:

• Nếu i == 0: XOR(i, j) = prefixXOR[j]
• Nếu i > 0: XOR(i, j) = prefixXOR[j] ^ prefixXOR[i-1]

Độ phức tạp giảm xuống O(n²) do vẫn cần duyệt tất cả cặp (i, j).

Phương pháp tối ưu hơn: Xử lý từng bit (Bit Manipulation)

Cách tiếp cận hiệu quả nhất là tính đóng góp của từng bit độc lập. Với mỗi vị trí bit i (0 ≤ i < 30 cho int 32-bit), ta đếm số mảng con mà XOR tại bit đó bằng 1. Tổng kết quả là tổng của (số_mảng_con_bit_1 * 2^i) cho mọi bit.

Thuật toán chi tiết trong code dưới đây chạy trong O(30 * n) ≈ O(n).

Chương trình C++ minh họa

#include <iostream>
using namespace std;

long long calcSubArrayXORSum(int arr[], int n) {
    long long sum = 0;
    long long multiplier = 1; // 2^i
    
    for (int i = 0; i < 30; i++) { // Duyệt qua 30 bit (int 32-bit)
        int oddCount = 0;
        bool isOdd = false;
        
        // Đếm số tiền tố có bit i = 1
        for (int j = 0; j < n; j++) {
            if ((arr[j] & (1 << i)) != 0)
                isOdd = !isOdd;
            if (isOdd)
                oddCount++;
        }
        
        // Tính đóng góp của bit i vào tổng
        for (int j = 0; j < n; j++) {
            sum += multiplier * oddCount;
            if ((arr[j] & (1 << i)) != 0)
                oddCount = (n - j - oddCount);
        }
        multiplier <<= 1; // Nhân 2
    }
    return sum;
}

int main() {
    int arr[] = {3, 8, 13};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Tong XOR cua tat ca mang con la " << calcSubArrayXORSum(arr, n);
    return 0;
}

Kết quả

Tong XOR cua tat ca mang con la 46