# Maximum XOR Score Subarray Queries
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-xor-score-subarray-queries)
Canonical: https://scaleengineer.com/dsa/problems/maximum-xor-score-subarray-queries
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## Problem
You are given an array `nums` of `n` integers, and a 2D integer array `queries` of size `q`, where `queries[i] = [li, ri]`.

For each query, you must find the **maximum XOR score** of any subarray of `nums[li..ri]`.

The **XOR score** of an array `a` is found by repeatedly applying the following operations on `a` so that only one element remains, that is the **score**:

* Simultaneously replace `a[i]` with `a[i] XOR a[i + 1]` for all indices `i` except the last one.
* Remove the last element of `a`.

Return an array `answer` of size `q` where `answer[i]` is the answer to query `i`.

**Example 1:**

**Input:** nums = \[2,8,4,32,16,1\], queries = \[\[0,2\],\[1,4\],\[0,5\]\]

**Output:** \[12,60,60\]

**Explanation:**

In the first query, `nums[0..2]` has 6 subarrays `[2]`, `[8]`, `[4]`, `[2, 8]`, `[8, 4]`, and `[2, 8, 4]` each with a respective XOR score of 2, 8, 4, 10, 12, and 6\. The answer for the query is 12, the largest of all XOR scores.

In the second query, the subarray of `nums[1..4]` with the largest XOR score is `nums[1..4]` with a score of 60.

In the third query, the subarray of `nums[0..5]` with the largest XOR score is `nums[1..4]` with a score of 60.

**Example 2:**

**Input:** nums = \[0,7,3,2,8,5,1\], queries = \[\[0,3\],\[1,5\],\[2,4\],\[2,6\],\[5,6\]\]

**Output:** \[7,14,11,14,5\]

**Explanation:**

| Index | nums\[li..ri\]    | Maximum XOR Score Subarray | Maximum Subarray XOR Score |
| ----- | ----------------- | -------------------------- | -------------------------- |
| 0     | \[0, 7, 3, 2\]    | \[7\]                      | 7                          |
| 1     | \[7, 3, 2, 8, 5\] | \[7, 3, 2, 8\]             | 14                         |
| 2     | \[3, 2, 8\]       | \[3, 2, 8\]                | 11                         |
| 3     | \[3, 2, 8, 5, 1\] | \[2, 8, 5, 1\]             | 14                         |
| 4     | \[5, 1\]          | \[5\]                      | 5                          |

**Constraints:**

* `1 <= n == nums.length <= 2000`
* `0 <= nums[i] <= 231 - 1`
* `1 <= q == queries.length <= 105`
* `queries[i].length == 2 `
* `queries[i] = [li, ri]`
* `0 <= li <= ri <= n - 1`

# Approaches
## Brute Force
This is the most straightforward and naive approach. For each query, we generate every possible subarray within the given range `[l, r]`. For each of these subarrays, we compute its XOR score and keep track of the maximum score encountered. The XOR score calculation is done based on its definition involving bitwise operations related to binomial coefficients modulo 2.
**Time:** O(q * n^3). For each of the `q` queries, we iterate through `O(n^2)` subarrays. Calculating the score for each subarray of length `k` takes `O(k)` time. In the worst case, `k` can be up to `n`, leading to the cubic complexity per query. · **Space:** O(1), as it only uses a few variables to store intermediate results, not counting the space for the output array.
**Pros:** Simple to understand and implement.; Requires minimal extra space.
**Cons:** Extremely inefficient due to its high time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The brute-force method directly translates the problem statement into code. It involves three nested loops for each query. The outer two loops iterate through all possible start (`i`) and end (`j`) points of subarrays within the query's range `[l, r]`. The innermost loop (or a helper function) calculates the XOR score for the subarray `nums[i..j]`. 

The score of a subarray `a` of length `len` is the XOR sum of its elements `a[k]` where the binary representation of `k` is a 'submask' of the binary representation of `len - 1`. This can be computed by iterating from `k = 0` to `len - 1` and checking the condition `((len - 1) & k) == k`.

```java
class Solution {
    private int calculateScore(int[] nums, int start, int end) {
        int len = end - start + 1;
        if (len == 0) return 0;
        int m = len - 1;
        int score = 0;
        for (int k = 0; k <= m; k++) {
            if ((m & k) == k) {
                score ^= nums[start + k];
            }
        }
        return score;
    }

    public int[] maxSubarrayXORScore(int[] nums, int[][] queries) {
        int q = queries.length;
        int[] ans = new int[q];
        for (int k = 0; k < q; k++) {
            int l = queries[k][0];
            int r = queries[k][1];
            int maxScore = 0;
            for (int i = l; i <= r; i++) {
                for (int j = i; j <= r; j++) {
                    maxScore = Math.max(maxScore, calculateScore(nums, i, j));
                }
            }
            ans[k] = maxScore;
        }
        return ans;
    }
}
```
### Algorithm
- For each query `[l, r]` in the `queries` array:
  - Initialize a variable `max_score` to 0.
  - Iterate through all possible start indices `i` from `l` to `r`.
    - Iterate through all possible end indices `j` from `i` to `r`.
      - This defines a subarray `nums[i..j]`.
      - Calculate the XOR score of this subarray.
        - To calculate the score of a subarray of length `len`, let `m = len - 1`.
        - The score is the XOR sum of `nums[i+k]` for all `k` from `0` to `m` such that `(m & k) == k`.
      - Update `max_score = max(max_score, current_subarray_score)`.
  - After all subarrays are checked, the `max_score` is the answer for the query `[l, r]`.

## DP Pre-computation of All Subarray Scores
We can optimize the score calculation by observing a dynamic programming structure. The score of an array `[a_0, ..., a_k]` is the same as the score of the transformed array `[a_0^a_1, ..., a_{k-1}^a_k]`. This allows us to pre-compute the scores of all `O(n^2)` subarrays in `O(n^2)` time. After pre-computation, we answer each query by iterating through the relevant pre-computed scores in the DP table.
**Time:** O(n^2 + q * n^2). The pre-computation takes `O(n^2)`. Each of the `q` queries then takes `O(n^2)` to check all relevant entries in the pre-computed table. · **Space:** O(n^2) to store the DP table `T`.
**Pros:** Efficiently pre-computes all subarray scores.; Much faster than the pure brute-force approach.
**Cons:** The query processing part is still very slow, making the overall approach inefficient for a large number of queries.; Requires significant `O(n^2)` space for the DP table.
### Explanation
This approach is based on a key recurrence relation for the XOR score. Let `T[d][i]` be the score of the subarray starting at `i` with length `d+1` (i.e., `nums[i..i+d]`).

- The base cases are subarrays of length 1: `T[0][i] = nums[i]`.
- For a subarray of length `d+1`, `nums[i..i+d]`, its score is equivalent to the score of the array `[nums[i]^nums[i+1], nums[i+1]^nums[i+2], ..., nums[i+d-1]^nums[i+d]]`. This transformed array starts at index `i` (in a conceptual transformed array) and has length `d`. Its score is thus `T[d-1][i]` based on the previous level of computation. This gives the recurrence `T[d][i] = T[d-1][i] ^ T[d-1][i+1]`.

We can build this `n x n` table `T` in `O(n^2)` time. Once `T` is populated, for each query `[l, r]`, we simply iterate through all subarrays `nums[i..j]` within this range and look up their scores `T[j-i][i]` to find the maximum.

```java
class Solution {
    public int[] maxSubarrayXORScore(int[] nums, int[][] queries) {
        int n = nums.length;
        int[][] T = new int[n][n];

        for (int i = 0; i < n; i++) {
            T[0][i] = nums[i];
        }

        for (int d = 1; d < n; d++) {
            for (int i = 0; i <= n - 1 - d; i++) {
                T[d][i] = T[d - 1][i] ^ T[d - 1][i + 1];
            }
        }

        int q = queries.length;
        int[] ans = new int[q];
        for (int k = 0; k < q; k++) {
            int l = queries[k][0];
            int r = queries[k][1];
            int maxScore = 0;
            for (int i = l; i <= r; i++) {
                for (int j = i; j <= r; j++) {
                    maxScore = Math.max(maxScore, T[j - i][i]);
                }
            }
            ans[k] = maxScore;
        }
        return ans;
    }
}
```
### Algorithm
- **Pre-computation:**
  - Create a 2D DP table `T` of size `n x n`, where `T[d][i]` will store the XOR score of the subarray `nums[i..i+d]`.
  - Initialize the base cases: `T[0][i] = nums[i]` for all `i` (scores of subarrays of length 1).
  - Fill the rest of the table using the recurrence: `T[d][i] = T[d-1][i] ^ T[d-1][i+1]`. This takes `O(n^2)` time.
- **Query Processing:**
  - For each query `[l, r]`:
    - Initialize `max_score = 0`.
    - Iterate `i` from `l` to `r` and `j` from `i` to `r`.
    - Look up the pre-computed score `T[j-i][i]`.
    - Update `max_score = max(max_score, T[j-i][i])`.
  - Store `max_score` as the answer.

## DP with Column-wise RMQ Optimization
This approach improves upon the previous one by optimizing the query phase. After pre-computing all subarray scores in the `T` table, we recognize that for a given query `[l, r]`, we are essentially performing a 2D range query on `T`. We can break this down. For each starting position `i` in the query range, we need the maximum score of subarrays starting at `i` and ending within the range. This is a Range Maximum Query (RMQ) on a column of our `T` table. By pre-building a Sparse Table for each column, we can answer these column-wise queries efficiently.
**Time:** O(n^2 log n + q * n). `O(n^2 log n)` for pre-computation (DP table + sparse tables) and `O(n)` for each of the `q` queries. · **Space:** O(n^2 log n). The `T` table takes `O(n^2)` space, but the sparse tables for all columns dominate, requiring `O(n^2 log n)` space.
**Pros:** Much faster query time compared to the simple DP approach.; Makes the problem tractable for the given constraints, though it might be on the edge of the time limit.
**Cons:** The `O(q*n)` query part can still be a bottleneck if both `q` and `n` are large.; High space complexity due to storing `n` sparse tables.
### Explanation
The query for `[l, r]` asks for `max_{l <= i <= j <= r} T[j-i][i]`. This can be rewritten as `max_{i=l..r} (max_{j=i..r} T[j-i][i])`. By substituting `d = j-i`, the inner maximum becomes `max_{d=0..r-i} T[d][i]`, which is a prefix maximum query on column `i` of the `T` table.

To accelerate this, we pre-process each column of `T` to handle RMQ. A Sparse Table is an ideal data structure for this, offering `O(k log k)` build time for a column of size `k` and `O(1)` query time.

1.  **DP Table `T`**: Compute in `O(n^2)`. `T[d][i]` is the score of `nums[i..i+d]`.
2.  **Sparse Tables**: For each column `i` from `0` to `n-1`, create a sparse table on the array `[T[0][i], T[1][i], ..., T[n-1-i][i]]`. Total build time is `O(n^2 log n)`.
3.  **Queries**: For a query `[l, r]`, we iterate `i` from `l` to `r`. In each iteration, we query the sparse table for column `i` to find `max_{d=0..r-i} T[d][i]` in `O(1)`. The total time for a query becomes `O(r-l+1)`, which is `O(n)` in the worst case.

This reduces the overall complexity, making it feasible for larger inputs than the previous approach.
### Algorithm
- **Pre-computation Step 1 (DP Table):**
  - Compute the `T[d][i]` table storing all subarray scores in `O(n^2)` time, as in the previous approach.
- **Pre-computation Step 2 (Sparse Tables):**
  - For each column `i` of the `T` table, build a Sparse Table data structure. This allows for `O(1)` Range Maximum Queries (RMQ) on that column.
  - Building sparse tables for all `n` columns takes a total of `O(n^2 log n)` time.
- **Query Processing:**
  - For each query `[l, r]`:
    - The problem is to find `max_{i=l..r} (max_{d=0..r-i} T[d][i])`.
    - Iterate `i` from `l` to `r`.
    - For each `i`, use the pre-built sparse table for column `i` to find the maximum value in the range of `d` from `0` to `r-i`. This query takes `O(1)`.
    - Keep track of the overall maximum.

## DP with Diagonal RMQ Optimization
This is the most efficient approach, optimizing the query time to a constant `O(1)`. It builds upon the DP foundation by performing further pre-computation. After calculating all scores, we compute column-wise prefix maximums. The crucial insight is that a query `[l, r]` corresponds to finding the maximum over a set of values that all lie on a single anti-diagonal of this new prefix-max table. By pre-building sparse tables for each anti-diagonal, we can answer any query in constant time.
**Time:** O(n^2 log n + q). `O(n^2)` for the `T` and `CMax` tables, `O(n^2 log n)` for building all sparse tables, and `O(1)` for each of the `q` queries. · **Space:** O(n^2 log n). The dominant factor is the space required to store the sparse tables for all `n` relevant anti-diagonals.
**Pros:** Extremely fast `O(1)` query time, making it ideal for a large number of queries.; The overall solution is very efficient and comfortably passes the time limits.
**Cons:** The implementation is complex, requiring multiple layers of data structures (DP table, prefix-max table, and sparse tables).; Requires a large amount of memory, `O(n^2 log n)`.
### Explanation
This approach refines the query process to achieve `O(1)` time per query.

1.  First, compute the `T[d][i]` table of all subarray scores in `O(n^2)`.
2.  Next, we transform the query problem. A query `[l, r]` seeks `max_{i=l..r} (max_{d=0..r-i} T[d][i])`. We can pre-calculate the inner maximum. Let `CMax[d][i] = max_{k=0..d} T[k][i]`. This table can be computed in `O(n^2)` time. The query then becomes finding `max_{i=l..r} CMax[r-i][i]`.
3.  The key observation is that for a fixed query `[l, r]`, all the accessed entries `CMax[r-i][i]` have indices `(d, i)` where `d+i = (r-i)+i = r`. This means they all lie on the anti-diagonal `k=r` of the `CMax` table.
4.  Therefore, we can pre-process the anti-diagonals. For each anti-diagonal `k` (from `0` to `n-1`, since `r` is at most `n-1`), we construct a sparse table. The `i`-th element on diagonal `k` is `CMax[k-i][i]`. Building these sparse tables takes `O(n^2 log n)` time.
5.  With this structure, a query `[l, r]` is answered by a single `O(1)` lookup in the sparse table for anti-diagonal `r`, querying the range of indices `[l, r]`.

```java
// Conceptual structure; requires a SparseTable helper class.
class Solution {
    public int[] maxSubarrayXORScore(int[] nums, int[][] queries) {
        int n = nums.length;
        // 1. Compute T[d][i]
        int[][] T = new int[n][n];
        for (int i = 0; i < n; i++) T[0][i] = nums[i];
        for (int d = 1; d < n; d++) {
            for (int i = 0; i <= n - 1 - d; i++) {
                T[d][i] = T[d - 1][i] ^ T[d - 1][i + 1];
            }
        }

        // 2. Compute CMax[d][i]
        int[][] CMax = new int[n][n];
        for (int i = 0; i < n; i++) {
            CMax[0][i] = T[0][i];
            for (int d = 1; d < n - i; d++) {
                CMax[d][i] = Math.max(CMax[d - 1][i], T[d][i]);
            }
        }

        // 3. Build Sparse Tables for diagonals of CMax
        SparseTable[] diagonalST = new SparseTable[n];
        for (int k = 0; k < n; k++) { // k = r, the diagonal index
            int[] diagonal = new int[k + 1];
            for (int i = 0; i <= k; i++) { // i is the index on the diagonal
                diagonal[i] = CMax[k - i][i];
            }
            diagonalST[k] = new SparseTable(diagonal);
        }

        // 4. Process queries in O(1) each
        int q = queries.length;
        int[] ans = new int[q];
        for (int i = 0; i < q; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            ans[i] = diagonalST[r].query(l, r);
        }
        return ans;
    }
}
// Assume SparseTable class is implemented for RMQ in O(1)
```
### Algorithm
- **Step 1: DP Table `T`**
  - Compute `T[d][i]` (score of `nums[i..i+d]`) in `O(n^2)` time.
- **Step 2: Column-Prefix-Max Table `CMax`**
  - Create a new table `CMax[d][i] = max_{k=0..d} T[k][i]`.
  - This can be computed in `O(n^2)` using the recurrence `CMax[d][i] = max(CMax[d-1][i], T[d][i])`.
- **Step 3: Sparse Tables on Diagonals**
  - The query for `[l, r]` simplifies to `max_{i=l..r} CMax[r-i][i]`.
  - All points `(d, i) = (r-i, i)` lie on the anti-diagonal where `d+i = r`.
  - For each anti-diagonal `k` (from `0` to `n-1`), create an array of its elements from `CMax` and build a Sparse Table on it.
  - This pre-computation takes `O(n^2 log n)` time and space.
- **Step 4: Query Processing**
  - A query `[l, r]` now translates to an RMQ on the `r`-th anti-diagonal's sparse table over the index range `[l, r]`.
  - This takes `O(1)` time.

# Solutions
### Java

```java
class Solution {
public
  int[] maximumSubarrayXor(int[] nums, int[][] queries) {
    int n = nums.length;
    int[][] f = new int[n][n];
    int[][] g = new int[n][n];
    for (int i = n - 1; i >= 0; --i) {
      f[i][i] = nums[i];
      g[i][i] = nums[i];
      for (int j = i + 1; j < n; ++j) {
        f[i][j] = f[i][j - 1] ^ f[i + 1][j];
        g[i][j] = Math.max(f[i][j], Math.max(g[i][j - 1], g[i + 1][j]));
      }
    }
    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] = g[l][r];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> maximumSubarrayXor(vector<int> &nums,
                                 vector<vector<int>> &queries) {
    int n = nums.size();
    vector<vector<int>> f(n, vector<int>(n));
    vector<vector<int>> g(n, vector<int>(n));
    for (int i = n - 1; i >= 0; --i) {
      f[i][i] = nums[i];
      g[i][i] = nums[i];
      for (int j = i + 1; j < n; ++j) {
        f[i][j] = f[i][j - 1] ^ f[i + 1][j];
        g[i][j] = max({f[i][j], g[i][j - 1], g[i + 1][j]});
      }
    }
    vector<int> ans;
    for (const auto &q : queries) {
      int l = q[0], r = q[1];
      ans.push_back(g[l][r]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumSubarrayXor(self, nums: List[int], queries: List[List[int]]) -> List[int]: n = len(nums) f = [[0] * n for _ in range(n)] g = [[0] * n for _ in range(n)] for i in range(n - 1, - 1, - 1): f[i][i] = g[i][i] = nums[i] for j in range(i + 1, n): f[i][j] = f[i][j - 1] ^ f[i + 1][j] g[i][j] = max(f[i][j], g[i][j - 1], g[i + 1][j]) return [g[l][r] for l, r in queries]

```