Skip to main content
Talentd

Range XOR Queries with Subarray Reversals - Solution & Explanation

HardPremiumFree on FleetCodeArrayTreeBinary Tree4 min read
Practice this problem

Problem Statement

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:

  1. Update: queries[i] = [1, index, value]
    Set nums[index] = value.

  2. 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.

  3. 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 <= 105
  • 0 <= nums[i] <= 109
  • 1 <= queries.length <= 105
  • queries[i].length == 3​
  • queries[i][0] ∈ {1, 2, 3}​
  • If queries[i][0] == 1:​
    • 0 <= index < nums.length​
    • 0 <= value <= 109
  • If queries[i][0] == 2 or queries[i][0] == 3:​
    • 0 <= left <= right < nums.length​

Approach Overview

Problem 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

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct SimulationO(n) per operationO(1)Small arrays or very few operations
Prefix XOR with RebuildQuery O(1), Update O(n)O(n)Query-heavy workloads with rare reversals
Implicit Balanced Binary Tree (Lazy Reverse)O(log n) per operationO(n)General case with frequent reversals and range XOR queries

Frequently Asked Questions

Is Range XOR Queries with Subarray Reversals easy or hard?
This problem is considered Hard because it combines sequence manipulation with efficient range queries. A correct solution requires understanding lazy propagation and balanced tree structures rather than simple array iteration.
Range XOR Queries with Subarray Reversals Python/Java solution
Most implementations build an implicit treap where nodes track value, subtree size, and subtree XOR. Split and merge operations isolate ranges, while a lazy reverse flag flips children when propagated. The same logic works in Python, Java, C++, and Go with O(log n) per operation.
How to solve Range XOR Queries with Subarray Reversals in O(n)?
Linear-time preprocessing alone is not sufficient when reversals occur frequently because the order of elements changes dynamically. Efficient solutions rely on structures like implicit treaps or segment-tree-like representations to support O(log n) updates and queries instead of recomputing the array each time.
What is the best approach for Range XOR Queries with Subarray Reversals?
The most efficient approach uses an implicit balanced binary tree such as a treap or rope with lazy propagation. Each node stores subtree size and XOR value. Reversal operations toggle a lazy flag while range queries read the stored XOR after splitting the tree. This keeps every operation at O(log n) time.
Is Range XOR Queries with Subarray Reversals asked at Google/Amazon/Meta?
Problems combining sequence updates and range queries appear frequently in interviews at companies like Google, Amazon, and Meta. Variants using segment trees, implicit treaps, or lazy propagation are common when testing advanced data structure design.
What data structure is used in Range XOR Queries with Subarray Reversals?
Typical implementations use an implicit treap, splay tree, or rope-style balanced binary tree. Each node stores subtree XOR and a lazy reversal flag so segments can be reversed without physically rearranging every element.
What is the time complexity of Range XOR Queries with Subarray Reversals?
The optimal solution processes both reversals and XOR queries in O(log n) time using a tree structure with lazy propagation. Space complexity is O(n) for storing nodes and subtree metadata. Brute force approaches may take O(n) per operation.

Ready to solve this problem?

Practice Range XOR Queries with Subarray Reversals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays