Hiểu bài toán

Bài toán yêu cầu xử lý một mảng gồm N số nguyên và Q truy vấn. Có hai loại truy vấn:

1. Cập nhật: Thay đổi giá trị phần tử tại chỉ số i bằng cách XOR với một giá trị x (A[i] = A[i] XOR x).
2. Truy vấn: Tính giá trị XOR của các phần tử từ chỉ số l đến r (A[l] XOR A[l+1] XOR ... XOR A[r]). Với N, Q lên tới 10^5, chúng ta cần một cấu trúc dữ liệu hiệu quả để xử lý cả hai thao tác trong thời gian logarit.

Các cách tiếp cận

Cách Brute Force (Mãng thường)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int i, x;
            cin >> i >> x;
            a[i-1] ^= x; // Cập nhật trực tiếp
        } else {
            int l, r;
            cin >> l >> r;
            int ans = 0;
            for (int k = l-1; k < r; k++) ans ^= a[k]; // Tính toán lại từ đầu
            cout << ans << "\n";
        }
    }
    return 0;
}

• Time Complexity: O(Q * N)
• Space Complexity: O(N)

Sử dụng mảng thường để lưu dữ liệu. Với mỗi truy vấn loại 2, ta duyệt qua mảng từ l đến r để tính XOR. Với N, Q lên tới 10^5, độ phức tạp O(Q*N) sẽ dẫn đến Time Limit Exceeded (TLE). Tuy nhiên, đây là cách tiếp cận cơ bản nhất để hiểu vấn đề.

Cách Fenwick Tree (Binary Indexed Tree)

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

const int MAX = 1e5 + 5;
int n, q;
int a[MAX], bit[MAX];

void update(int idx, int val) {
    for (; idx <= n; idx += idx & -idx)
        bit[idx] ^= val;
}

int query(int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & -idx)
        res ^= bit[idx];
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        update(i, a[i]);
    }
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int i, x;
            cin >> i >> x;
            update(i, a[i] ^ x); // Logic cập nhật BIT
            a[i] ^= x;
        } else {
            int l, r;
            cin >> l >> r;
            cout << (query(r) ^ query(l-1)) << "\n";
        }
    }
    return 0;
}

• Time Complexity: O(Q log N)
• Space Complexity: O(N)

Cấu trúc Fenwick Tree (BIT) rất linh hoạt và có thể hỗ trợ các phép toán cộng, nhân và XOR. BIT lưu trữ kết quả XOR của các dãy con có độ dài là số mũ của 2 (từ chỉ số đó trở về trước).

• Cập nhật: Khi thay đổi A[i], ta phải cập nhật tất cả các node trong BIT chứa A[i]. Do XOR là phép toán có tính giao hoán và có phủ (a XOR a = 0), ta có thể thực hiện cập nhật bằng cách XOR giá trị mới với giá trị cũ, hoặc nếu chỉ biết giá trị thay đổi delta, ta XOR delta vào các node.
• Truy vấn: Tính XOR prefix từ 1 đến r và từ 1 đến l-1, kết quả là XOR của chúng. Phương pháp này nhanh hơn Brute Force rất nhiều và giải quyết được bài toán trong giới hạn thời gian.

Cách Segment Tree

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

const int MAX = 1e5 + 5;
int n, q;
int a[MAX];
int seg[4 * MAX];

void build(int node, int l, int r) {
    if (l == r) {
        seg[node] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    seg[node] = seg[2 * node] ^ seg[2 * node + 1];
}

void update(int node, int l, int r, int idx, int val) {
    if (l == r) {
        seg[node] ^= val;
        return;
    }
    int mid = (l + r) / 2;
    if (idx <= mid) update(2 * node, l, mid, idx, val);
    else update(2 * node + 1, mid + 1, r, idx, val);
    seg[node] = seg[2 * node] ^ seg[2 * node + 1];
}

int query(int node, int l, int r, int i, int j) {
    if (j < l || i > r) return 0;
    if (i <= l && r <= j) return seg[node];
    int mid = (l + r) / 2;
    return query(2 * node, l, mid, i, j) ^ query(2 * node + 1, mid + 1, r, i, j);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int i, x;
            cin >> i >> x;
            update(1, 1, n, i, x);
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << "\n";
        }
    }
    return 0;
}

• Time Complexity: O(Q log N)
• Space Complexity: O(N)

Segment Tree là một cấu trúc cây phân đoạn chuẩn để xử lý các truy vấn khoảng. Cây được xây dựng với mỗi node lưu giá trị XOR của đoạn con tương ứng.

• Cập nhật: Ta đi xuống lá tương ứng với chỉ số i, thay đổi giá trị (hoặc XOR thêm x), và cập nhật lại các node cha trên đường đi lên.
• Truy vấn: Ta duyệt cây để tìm các đoạn con nằm hoàn toàn trong khoảng [l, r] và XOR chúng lại với nhau. Đây là phương pháp chuẩn và trực quan nhất cho các bài toán xử lý truy vấn khoảng.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Phép toán XOR có tính giao hoán (a ^ b = b ^ a) và kết hợp (a ^ b ^ c = (a ^ b) ^ c). Quan trọng nhất là a ^ a = 0 và 0 ^ a = a.
• Vì a ^ a = 0, giá trị XOR của một đoạn [l, r] có thể tính nhanh bằng cách lấy XOR của hai mảng prefix: Prefix[r] ^ Prefix[l-1]. Tuy nhiên, với bài toán có cập nhật, cấu trúc cây phân đoạn (Segment Tree) hoặc cây BIT là bắt buộc.

Lỗi thường gặp

• Lỗi chỉ số (Off-by-one error): Trong các cấu trúc cây như BIT hoặc Segment Tree, thường quy ước chỉ số bắt đầu từ 1 để thuận tiện cho phép tính bit phụ (LSB). Cần chú ý khi nhập xuất dữ liệu từ mảng.
• Giá trị ban đầu và giá trị cập nhật: Với Segment Tree, cập nhật giá trị mới (set) khác với cập nhật XOR thêm (add). Cập nhật XOR thêm chỉ cần thực hiện ở lá và đi lên, không cần biết giá trị cũ.
• Kiểu dữ liệu và giới hạn: Giá trị XOR nằm trong phạm vi của số nguyên (int), nhưng với các bài toán lớn hơn, cần chú ý kiểu dữ liệu long long.