Leetcode 1310

题目要求

给定一个正数组arr，给定一个数组queries，其每个元素的结构为[left, right]，分别对于每一次查询，求从arr[left]一直异或到arr[right]的结果，结果保存在数组中

说明：如果left=right则直接返回arr[left]

核心算法和原理

• 神奇位运算之 x ^ y ^ x = y

• 根据这个原理，注意到对于一次查询的结果：

• 直接转变为前缀和问题，后略

代码

class Solution {
public:
    Solution() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        // res[i, j] = res[0, i - 1] ^ res[0, j]
        vector<int> res;
        vector<int> pre(arr.size());
        pre[0] = arr[0];
        for (int i = 1; i < arr.size(); i++) {
            pre[i] = pre[i - 1] ^ arr[i];
        }
        for (auto query : queries) {
            if (query[0] == query[1]) {
                res.push_back(arr[query[0]]);
            } else if (query[0] != 0){
                res.push_back(pre[query[0] - 1] ^ pre[query[1]]);
            } else {
                res.push_back(pre[query[1]]);
            }
        }
        return res;
    }
};