1310 子数组异或查询

问题描述：

​ 有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor … xor arr[Ri]）作为本次查询的结果。并返回一个包含给定查询 queries 所有结果的数组。

示例1：

输入：arr = [1,3,4,8], queries = [[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

示例2：

输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
输出：[8,0,4,4]

思路：

​ 这个问题乍一看不难，毕竟常理来说遍历一趟就什么都解决了，但这里如果遍历的话，我们需要重复计算的内容太多了，所以这里需要对之前计算的东西做一个保存，才能在时间上保证可以通过。

​ 第一个思路是新建一个二维数组，保存从 i 到 j 的异或值，后面输出的时候直接使用即可，但是这里存在一个问题，就是我们需要new的这个数组实在是太大了，并且里面有将近一半的空间是没有用的，因为我们只需要 j 大于等于 i 的那一部分值，反映到矩阵中就是一个矩阵的上半部分。所以对空间产生了极大地浪费。

​ 初级实现的时候，时间没有爆炸，空间爆炸了。

Java代码：

/** 
* @Description: 力扣1310题题解
* @return: 返回结果
* @Author: Mr.Gao
* @Date: 2021/5/12 
*/
public int[] xorQueries(int[] arr, int[][] queries) {
    int n = arr.length;
    int[][] temp = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if(i==j){
                temp[i][j] = arr[i];
            }else{
                temp[i][j] = temp[i][j-1]^arr[j];
            }
        }
    }
    int m = queries.length;
    int[] re = new int[m];
    for (int i = 0; i < m; i++) {
        re[i] = temp[queries[i][0]][queries[i][1]];
    }
    return re;
}

​ 空间爆炸之后，我们就思考初始化的数组让其变得简单点，我们其实没有必要将所有匹配的异或值全部计算出来，只需要计算两个边界的值即可。也就是我们计算0号位置到其余各号位置的异或值，和其余各号位置到n-1号位置的异或值，然后在根据异或计算的特性，我们就可以根据这两个值来计算出所有左右边界的异或值。

​ 根据之前异或计算的结论，a异或b = c，那么abc三者的任意两个的异或都等于第三个变量的值。根据这个结论。

• 我们可以先将数组中所有元素一起异或的值保存下来
• 接着再异或从0到左边界的值，再异或从右边界到n-1号的值，我们就得出了从左边界+1到右边界-1的异或值
• 再异或一下左边界和右边界就可以得到从左边界到右边界的异或值。

这样节约了空间和时间。

Java代码：

/** 
* @Description: 力扣1310题题解2
* @return: 返回结果
* @Author: Mr.Gao
* @Date: 2021/5/12 
*/

public int[] xorQueries2(int[] arr, int[][] queries) {
    int n = arr.length;
    //temp【0】保存从0到j的所有异或值，temp【1】保存从j到n-1的所有异或值。
    int[][] temp = new int[2][n];
    //x保存arr中所有元素的异或值
    int x = arr[0];

    temp[0][0] = arr[0];
    for(int i=1;i<n;i++){
        temp[0][i] = temp[0][i-1]^arr[i];
        x^=arr[i];
    }

    temp[1][n-1] = arr[n-1];
    for(int i = n-2;i>=0;i--){
        temp[1][i] = temp[1][i+1]^arr[i];
    }

    int m = queries.length;
    int[] re = new int[m];
    for (int i = 0; i < m; i++) {
        re[i] = x^temp[0][queries[i][0]]^temp[1][queries[i][1]]^arr[queries[i][0]]^arr[queries[i][1]];
    }
    return re;
}

• 码字不易，还望素质三连！