การคิวรี XOR ของซับอาร์เรย์ใน C++

สมมติว่าเรามีอาร์เรย์ arr ของจำนวนเต็มบวก และอาร์เรย์ queries โดยที่ queries[i] = [Li, Ri] สำหรับแต่ละคิวรี เราต้องคำนวณ XOR ขององค์ประกอบตั้งแต่ Li ถึง Ri (คือ arr[Li] XOR arr[Li+1] XOR ... XOR arr[Ri]) เราต้องหาอาร์เรย์ที่มีผลลัพธ์สำหรับคิวรีที่กำหนด

ตัวอย่าง อินพุต: [1,3,4,8], คิวรี: [[0,1],[1,2],[0,3],[3,3]] ผลลัพธ์: [2,7,14,8]

เพราะการแทนค่าบاينารี: 1 = 0001, 3 = 0011, 4 = 0100, 8 = 1000
XOR สำหรับคิวรี: [0,1] = 1 XOR 3 = 2, [1,2] = 3 XOR 4 = 7, [0,3] = 1 XOR 3 XOR 4 XOR 8 = 14, [3,3] = 8

ขั้นตอนการแก้ปัญหา

• n := ขนาดของ arr
• กำหนดอาร์เรย์ pre ขนาด n + 1 แล้วเติมค่า โดยที่ pre[i] := pre[i-1] XOR arr[i-1]
• กำหนดอีกอาร์เรย์หนึ่งชื่อ ans
• วนลูป i จาก 0 ถึง จำนวนคิวรี - 1
  • l := queries[i][0], r := queries[i][1]
  • เพิ่ม l และ r ขึ้น 1
  • นำ pre[r] XOR pre[l-1] ใส่เข้า ans
• คืนค่า ans

ตัวอย่างโค้ด (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));
}

อินพุต

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

เอาต์พุต

[2,7,14,8]