子数组异或查询 图解题解

这道题到底在问什么

输入

arr=[1,3,4,8], queries=[[0,1],[1,2],[0,3],[3,3]]

输出

[2,7,14,8]

输入

arr=[4,8,2,10], queries=[[2,3],[1,3],[0,0],[0,3]]

输出

[8,0,4,4]

最优解：一步一步想明白

1. 3记牢一句话:先把前缀异或数组 pre 建出来,之后每个区间查询都等于 pre[R+1] 异或 pre[L]。下面每一帧都在套这个公式。
2. 4上面这排是 arr = [1, 3, 4, 8]。右边面板是要建的前缀异或数组 pre,它比 arr 多一格,一共 5 格,现在全是问号。第一格 pre[0] 我们约定它等于 0,这是一段空异或的自然起点,异或上 0 什么都不变。
3. 5异或是按二进制位算的,所以先把 arr 每个数写成二进制看清楚:1 是 0001,3 是 0011,4 是 0100,8 是 1000。两个数异或时,逐位比较,这一位相同就得 0、不同就得 1,各位互不影响。心里有了这张二进制表,后面建前缀异或、算查询都顺。
4. 6先把 pre[0] 写成 0。它代表前 0 个数的异或,也就是什么都不异或,结果就是 0。0 是异或的零元,谁异或 0 都等于它自己,这个性质待会儿处理从下标 0 开始的查询时会非常顺手。
5. 7把 arr[0] = 1 接进来。新的前缀值 pre[1] 等于上一格 pre[0] = 0 再异或这个 1,二进制是 0000 异或 0001 等于 0001,也就是 1。把它记到 pre[1] 这一格。
6. 8把 arr[1] = 3 接进来。新的前缀值 pre[2] 等于上一格 pre[1] = 1 再异或这个 3,二进制是 0001 异或 0011 等于 0010,也就是 2。把它记到 pre[2] 这一格。
7. 9把 arr[2] = 4 接进来。新的前缀值 pre[3] 等于上一格 pre[2] = 2 再异或这个 4,二进制是 0010 异或 0100 等于 0110,也就是 6。把它记到 pre[3] 这一格。
8. 10把 arr[3] = 8 接进来。新的前缀值 pre[4] 等于上一格 pre[3] = 6 再异或这个 8,二进制是 0110 异或 1000 等于 1110,也就是 14。把它记到 pre[4] 这一格。
9. 11前缀异或数组建好了,从左到右是 0、1、2、6、14。从这一帧起,舞台上摆的就是这排 pre,不再是原来的 arr。记住每一格的含义:pre[i] 是 arr 前 i 个数的异或值,比如 pre[3] = 6 就是 arr[0] 异或 arr[1] 异或 arr[2]。
10. 12现在用 pre 来回答查询。任意区间 [L, R] 的异或值,等于 pre[R+1] 异或 pre[L]。为什么是 R+1 而不是 R?因为 pre[R+1] 才包含到 arr[R] 这一项,pre[R] 只到 arr[R-1]。下面对 3 个查询逐个套这个公式。
11. 13先用查询 [3,3] 体会抵消。pre[4] 是 arr[0] 异或 arr[1] 异或 arr[2] 异或 arr[3],pre[3] 是 arr[0] 异或 arr[1] 异或 arr[2]。两者异或时,共有的 arr[0]、arr[1]、arr[2] 各出现两次,而一个数异或它自己等于 0,于是成对抵消,只剩下 arr[3] = 8。这就是公式成立的根。
12. 14第 0 个查询是 [0, 1]。套公式,R 是 1,那 R+1 就是 2,所以要取 pre[2] 这一格;L 是 0,取 pre[0] 这一格。下一步把这两格异或起来。
13. 15把绿色这两格异或:pre[2] = 2,pre[0] = 0。二进制是 0010 异或 0000,逐位算下来等于 0010,也就是 2。这就是区间 [0, 1] 的异或值。
14. 16查询 [0, 1] 的答案是 2。验一下:arr 这一段是 1、3,直接全异或起来也是 2,对得上。把它接到答案数组,目前是 [2]。
15. 17第 1 个查询是 [0, 3]。套公式,R 是 3,那 R+1 就是 4,所以要取 pre[4] 这一格;L 是 0,取 pre[0] 这一格。下一步把这两格异或起来。
16. 18把绿色这两格异或:pre[4] = 14,pre[0] = 0。二进制是 1110 异或 0000,逐位算下来等于 1110,也就是 14。这就是区间 [0, 3] 的异或值。
17. 19查询 [0, 3] 的答案是 14。验一下:arr 这一段是 1、3、4、8,直接全异或起来也是 14,对得上。把它接到答案数组,目前是 [2、14]。
18. 20第 2 个查询是 [3, 3]。套公式,R 是 3,那 R+1 就是 4,所以要取 pre[4] 这一格;L 是 3,取 pre[3] 这一格。下一步把这两格异或起来。
19. 21把绿色这两格异或:pre[4] = 14,pre[3] = 6。二进制是 1110 异或 0110,逐位算下来等于 1000,也就是 8。这就是区间 [3, 3] 的异或值。
20. 22查询 [3, 3] 的答案是 8。验一下:arr 这一段是 8,直接全异或起来也是 8,对得上。把它接到答案数组,目前是 [2、14、8]。
21. 23三个查询都答完了,回放一遍:[0,1] 是 pre[2] 异或 pre[0] 等于 2;[0,3] 是 pre[4] 异或 pre[0] 等于 14;[3,3] 是 pre[4] 异或 pre[3] 等于 8。最终答案数组就是 [2、14、8]。全程 pre 只建一次,每个查询都是一步异或。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
from string import *
from operator import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        s = list(accumulate(arr, xor, initial=0))
        return [s[r + 1] ^ s[l] for l, r in queries]

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        int n = arr.size();
        int s[n + 1];
        memset(s, 0, sizeof(s));
        for (int i = 1; i <= n; ++i) {
            s[i] = s[i - 1] ^ arr[i - 1];
        }
        vector<int> ans;
        for (auto& q : queries) {
            int l = q[0], r = q[1];
            ans.push_back(s[r + 1] ^ s[l]);
        }
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            s[i] = s[i - 1] ^ arr[i - 1];
        }
        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; ++i) {
            int l = queries[i][0], r = queries[i][1];
            ans[i] = s[r + 1] ^ s[l];
        }
        return ans;
    }
}

复杂度

面试官可能追问