You are given an integer array nums of length n and a 2D integer array queries of length q, where each query is one of the following three types:
Update: queries[i] = [1, index, value]
Set nums[index] = value.
Range XOR Query: queries[i] = [2, left, right]
Compute the bitwise XOR of all elements in the subarray nums[left...right], and record this result.
Reverse Subarray: queries[i] = [3, left, right]
Reverse the subarray nums[left...right] in place.
Return an array of the results of all range XOR queries in the order they were encountered.
Example 1:
Input: nums = [1,2,3,4,5], queries = [[2,1,3],[1,2,10],[3,0,4],[2,0,4]]
Output: [5,8]
Explanation:
Query 1: [2, 1, 3] – Compute XOR of subarray [2, 3, 4] resulting in 5.
Query 2: [1, 2, 10] – Update nums[2] to 10, updating the array to [1, 2, 10, 4, 5].
Query 3: [3, 0, 4] – Reverse the entire array to get [5, 4, 10, 2, 1].
Query 4: [2, 0, 4] – Compute XOR of subarray [5, 4, 10, 2, 1] resulting in 8.
Example 2:
Input: nums = [7,8,9], queries = [[1,0,3],[2,0,2],[3,1,2]]
Output: [2]
Explanation:
Query 1: [1, 0, 3] – Update nums[0] to 3, updating the array to [3, 8, 9].
Query 2: [2, 0, 2] – Compute XOR of subarray [3, 8, 9] resulting in 2.
Query 3: [3, 1, 2] – Reverse the subarray [8, 9] to get [9, 8].
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1091 <= queries.length <= 105queries[i].length == 3queries[i][0] ∈ {1, 2, 3}queries[i][0] == 1:
0 <= index < nums.length0 <= value <= 109queries[i][0] == 2 or queries[i][0] == 3:
0 <= left <= right < nums.lengthProblem Overview: You maintain an array while processing two operations: reverse a subarray and compute the XOR of values inside a range. The difficulty comes from handling many reversals without rebuilding the array each time.
Approach 1: Direct Simulation (Brute Force) (Time: O(n) per operation, Space: O(1))
The simplest approach stores the array and performs each operation directly. For a reversal, iterate from both ends of the range and swap elements until the segment is reversed. For a query, iterate from l to r and compute the XOR cumulatively. This approach is straightforward but slow when the number of operations is large because each reversal or query may scan up to the entire array. It works only when n and the number of queries are small.
Approach 2: Prefix XOR with Rebuild After Reversal (Time: O(n) update, O(1) query, Space: O(n))
You can maintain a prefixXor array so that range XOR queries run in constant time using prefix[r] ^ prefix[l-1]. However, reversing a subarray breaks the prefix structure. After every reversal, the prefix array must be recomputed for the affected portion or for the entire array. This reduces query time but still keeps updates expensive. It improves performance when queries are far more frequent than reversals.
Approach 3: Implicit Balanced Binary Tree with Lazy Reversal (Time: O(log n) per operation, Space: O(n))
The optimal approach stores the sequence inside a balanced structure such as an implicit treap or rope-like tree. Each node represents one value and stores metadata including subtree size and the XOR of the entire subtree. Splitting the tree by index isolates any range in O(log n). To reverse a subarray, toggle a lazy reverse flag on the subtree instead of physically rearranging nodes. When needed, the flag swaps children and propagates downward.
For XOR queries, isolate the range using two splits and read the stored subtree XOR value. After the query, merge the segments back together. Because XOR is associative, each node simply maintains node.xor = left.xor ^ value ^ right.xor. Both reversal and XOR operations remain logarithmic regardless of array size. This technique is a common pattern when problems combine sequence modification with range queries.
Problems involving dynamic sequences often combine ideas from array manipulation with tree-based structures. The implicit treap behaves like a dynamic array while maintaining aggregated values similar to a segment tree built on a tree or binary tree.
Recommended for interviews: The implicit tree with lazy reversal is the expected solution. Brute force demonstrates baseline understanding, but the logarithmic tree approach shows you can design data structures that support both structural changes and fast range aggregation.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(n) per operation | O(1) | Small arrays or very few operations |
| Prefix XOR with Rebuild | Query O(1), Update O(n) | O(n) | Query-heavy workloads with rare reversals |
| Implicit Balanced Binary Tree (Lazy Reverse) | O(log n) per operation | O(n) | General case with frequent reversals and range XOR queries |
Practice Range XOR Queries with Subarray Reversals with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor