LeetCode 1310. 子数组异或查询

约 4 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 阿里
标签
数组 位运算 前缀和

题目描述

✅ 1310. 子数组异或查询

image-20260929080504677

image-20260929080504784

题意分析

给定不变的数组和多次查询，每个查询 [left, right] 要求计算这两个下标之间所有元素的按位异或，左右端点都包含。按查询原顺序返回结果数组。

查询之间可能有大量重叠区间，但不会修改数组。单次查询也可能只含一个元素，因此需要统一处理区间起点为零、终点为末尾及单元素等边界。

解法：前缀异或

核心思路

[!blue]

逐条扫描查询区间会重复异或相同前缀。先定义 prefix[i] 为前 i 个元素，即 arr[0..i-1] 的异或，prefix[0] = 0 表示空前缀。每次把新元素接到前缀后，有 prefix[i + 1] = prefix[i] ^ arr[i]。

异或满足结合律、交换律，以及 x ^ x = 0、x ^ 0 = x。prefix[right + 1] 同时包含目标区间和它左侧的公共前缀，再异或 prefix[left]，公共部分每项出现两次全部抵消，只剩 arr[left..right]。

因此每个答案都用 prefix[right + 1] ^ prefix[left] 两次读表得到。这里前缀下标表示元素个数，所以包含右端元素时需要加一，排除左端之前的部分时直接使用 left。

多保存一个空前缀，使 left = 0 时也无需特判；当左右端相同，两个前缀只相差那个元素，结果自然就是它本身。预处理可在全部静态查询间复用。

解题步骤

  1. 创建长度为 n + 1 的前缀数组，保留零号位置为零。
  2. 按原数组顺序计算 prefix[i + 1] = prefix[i] ^ arr[i]。
  3. 为每个查询读取 left、right，将 prefix[right + 1] ^ prefix[left] 写到对应答案位置。
  4. 返回长度为查询数量的结果数组。

代码实现

class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        // prefix[i] 表示前 i 个元素的异或，零位置代表空前缀。
        int[] prefix = new int[arr.length + 1];

        for (int i = 0; i < arr.length; i++) {
            prefix[i + 1] = prefix[i] ^ arr[i];
        }

        int[] answer = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];

            // 异或抵消区间左侧，闭区间右端需要转换为 right+1。
            answer[i] = prefix[right + 1] ^ prefix[left];
        }

        return answer;
    }
}

func xorQueries(arr []int, queries [][]int) []int {
    // prefix[i] 表示前 i 个元素的异或，零位置代表空前缀。
    prefix := make([]int, len(arr)+1)
    for i, value := range arr {
        prefix[i+1] = prefix[i] ^ value
    }

    answer := make([]int, len(queries))
    for i, query := range queries {
        left, right := query[0], query[1]
        // 异或抵消区间左侧，闭区间右端需要转换为 right+1。
        answer[i] = prefix[right+1] ^ prefix[left]
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(n+q)$，预处理一次，每个查询为常数时间。
  • 空间复杂度：前缀表占 $O(n)$，返回结果另占 $O(q)$。

关键点总结

[!green]

  • 下标表示元素个数，不是截至该下标。
  • 异或的逆操作仍是异或。
  • 答案数组长度由查询数决定。

易错点总结

[!yellow]

  • 右端没有加 1：会漏掉 arr[r]。
  • 左端减 1：与当前前缀定义不符，l=0 还会越界。
  • 使用普通减法抵消：异或前缀需要使用 XOR。

相似题目

题目 难度 关联与区别
303. 区域和检索 - 数组不可变 简单 前缀求和通过减法消去公共部分，本题前缀异或通过再次异或消去公共部分。
1177. 构建回文串检测 中等 字符频次奇偶可编码成位掩码，再用同样的前缀异或获取子串状态。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/81852427
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！