Truy vấn XOR của mảng con trong C++

Cho mảng arr các số nguyên dương và mảng queries với queries[i] = [Li, Ri]. Với mỗi truy vấn, tính XOR của các phần tử từ Li đến Ri (tức arr[Li] XOR arr[Li+1] XOR ... XOR arr[Ri]). Trả về mảng kết quả cho các truy vấn.

Ví dụ: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]. Kết quả: [2,7,14,8]. Giải thích: biểu diễn nhị phân: 1=0001, 3=0011, 4=0100, 8=1000. XOR: [0,1]=1^3=2, [1,2]=3^4=7, [0,3]=1^3^4^8=14, [3,3]=8.

Giải thuật

1. n = kích thước arr.
2. Tạo mảng tiền tố pre kích thước n+1, với pre[i] = pre[i-1] XOR arr[i-1].
3. Tạo mảng kết quả ans.
4. Với mỗi truy vấn [l, r]:
5. Tăng l và r lên 1.
6. Thêm pre[r] XOR pre[l-1] vào ans.
7. Trả về ans.

Ví dụ C++

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

void print_vector(vector<auto> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        int n = arr.size();
        vector<int> pre(n + 1);
        for(int i = 1; i <= n; i++) pre[i] = pre[i-1] ^ arr[i-1];
        vector<int> ans;
        for(int i = 0; i < queries.size(); i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            l++; r++;
            ans.push_back(pre[r] ^ pre[l-1]);
        }
        return ans;
    }
};

int main() {
    vector<int> v = {1,3,4,8};
    vector<vector<int>> v1 = {{0,1},{1,2},{0,3},{3,3}};
    Solution ob;
    print_vector(ob.xorQueries(v, v1));
    return 0;
}

Đầu vào

[1,3,4,8] [[0,1],[1,2],[0,3],[3,3]]

Đầu ra

[2,7,14,8]