LeetCode 3526 - Range XOR Queries with Subarray Reversals

Difficulty: 🔴 Hard
Topics: Array, Tree, Binary Tree

Solution

Here’s a full technical solution guide for LeetCode 3526 - Range XOR Queries with Subarray Reversals following your requested structure and formatting:

Problem Understanding

The problem provides an array nums of integers and a list of queries, where each query can either update a value in the array, reverse a subarray, or compute the XOR of a subarray. The task is to return the results of all XOR queries in the order they appear.

In other words, the array nums is dynamic, and we need to efficiently handle three operations: point updates, range XOR computations, and subarray reversals. The final output is only the results of XOR queries, not the state of the array after each operation.

The constraints indicate that nums can have up to 10^5 elements and there can be up to 10^5 queries. This rules out any naive solution that performs operations like reversing or XOR computation over subarrays in O(n) time per query because the total runtime would be too large (up to 10^10).

Edge cases include queries that operate on the boundaries of the array (left = 0 or right = n-1), arrays with length 1, queries that consecutively reverse the same subarray, and multiple updates to the same index.

Approaches

Brute Force Approach

The simplest approach is to directly simulate the array operations. For each query:

For type 1 (update), set nums[index] = value.
For type 2 (XOR query), iterate from left to right and compute XOR.
For type 3 (reverse), slice the array and reverse the subarray.

While this approach is straightforward and guarantees correctness, it has poor performance for large inputs. Each XOR or reverse query could take O(n) time, and with up to 10^5 queries, the worst-case time complexity becomes O(n*q) which can reach 10^10, far exceeding practical limits.

Optimal Approach

The key observation is that the problem involves range XOR queries, point updates, and subarray reversals. A data structure that supports these efficiently is required. A Segment Tree is suitable because it can handle:

Point updates in O(log n) time.
Range XOR queries in O(log n) time.
Lazy propagation for range reversals, which allows reversing subarrays in O(log n) time per operation.

In a Segment Tree:

Each node stores the XOR of its segment.
A lazy flag at each node tracks whether its segment should be reversed.
Push-down ensures reversals are applied correctly to child nodes before further operations.

Using a Segment Tree with lazy propagation reduces the complexity from O(n*q) to O(q*log n), which is feasible for n, q <= 10^5.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n*q)	O(n)	Directly simulates each query
Segment Tree	O(q*log n)	O(n)	Handles updates, XOR queries, and reversals efficiently

Algorithm Walkthrough

Build the Segment Tree: Construct a tree where each leaf corresponds to an element of nums, and each internal node stores the XOR of its children.
Process Queries: Iterate through each query.
Update (type 1): Use the segment tree to update the value at the given index and propagate changes to ancestors.
Range XOR Query (type 2): Use the segment tree to compute the XOR over the specified range, accounting for any pending reversals using lazy propagation. Append the result to the output list.
Reverse Subarray (type 3): Mark the segment of the segment tree representing the subarray as "reversed" using a lazy flag. Push the reversal to children nodes when necessary.
Return Results: After processing all queries, return the list of results from XOR queries.

Why it works: The Segment Tree guarantees that all operations over a segment can be done in logarithmic time. Lazy propagation ensures reversals do not require O(n) time for each reverse query, instead propagating the effect efficiently. XOR is associative and commutative, so range XOR queries are compatible with this structure.

Python Solution

from typing import List

class SegmentTree:
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.tree = [0] * (4 * self.n)
        self.lazy = [False] * (4 * self.n)
        self.build(1, 0, self.n - 1, nums)

    def build(self, node, l, r, nums):
        if l == r:
            self.tree[node] = nums[l]
        else:
            mid = (l + r) // 2
            self.build(node*2, l, mid, nums)
            self.build(node*2+1, mid+1, r, nums)
            self.tree[node] = self.tree[node*2] ^ self.tree[node*2+1]

    def push(self, node, l, r):
        if self.lazy[node]:
            self.tree[node] = self.tree[node]  # XOR remains same for reversal
            if l != r:
                self.lazy[node*2] ^= True
                self.lazy[node*2+1] ^= True
            self.lazy[node] = False

    def update(self, node, l, r, idx, val):
        self.push(node, l, r)
        if l == r:
            self.tree[node] = val
        else:
            mid = (l + r) // 2
            if idx <= mid:
                self.update(node*2, l, mid, idx, val)
            else:
                self.update(node*2+1, mid+1, r, idx, val)
            self.tree[node] = self.tree[node*2] ^ self.tree[node*2+1]

    def range_xor(self, node, l, r, ql, qr):
        self.push(node, l, r)
        if r < ql or l > qr:
            return 0
        if ql <= l and r <= qr:
            return self.tree[node]
        mid = (l + r) // 2
        return self.range_xor(node*2, l, mid, ql, qr) ^ self.range_xor(node*2+1, mid+1, r, ql, qr)

    def reverse(self, node, l, r, ql, qr):
        self.push(node, l, r)
        if r < ql or l > qr:
            return
        if ql <= l and r <= qr:
            self.lazy[node] ^= True
            self.push(node, l, r)
            return
        mid = (l + r) // 2
        self.reverse(node*2, l, mid, ql, qr)
        self.reverse(node*2+1, mid+1, r, ql, qr)
        self.tree[node] = self.tree[node*2] ^ self.tree[node*2+1]

class Solution:
    def getResults(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        st = SegmentTree(nums)
        results = []
        for q in queries:
            if q[0] == 1:
                st.update(1, 0, st.n - 1, q[1], q[2])
            elif q[0] == 2:
                results.append(st.range_xor(1, 0, st.n - 1, q[1], q[2]))
            else:
                st.reverse(1, 0, st.n - 1, q[1], q[2])
        return results

Explanation: The Segment Tree class encapsulates all required operations. push ensures lazy reversals are applied correctly. update and range_xor are standard segment tree operations. reverse uses lazy propagation to flip the reversal state for a subarray.

Go Solution

func getResults(nums []int, queries [][]int) []int {
    n := len(nums)
    tree := make([]int, 4*n)
    lazy := make([]bool, 4*n)

    var build func(node, l, r int)
    build = func(node, l, r int) {
        if l == r {
            tree[node] = nums[l]
        } else {
            mid := (l + r) / 2
            build(node*2, l, mid)
            build(node*2+1, mid+1, r)
            tree[node] = tree[node*2] ^ tree[node*2+1]
        }
    }

    var push func(node, l, r int)
    push = func(node, l, r int) {
        if lazy[node] {
            if l != r {
                lazy[node*2] = !lazy[node*2]
                lazy[node*2+1] = !lazy[node*2+1]
            }
            lazy[node] = false
        }
    }

    var update func(node, l, r, idx, val int)
    update = func(node, l, r, idx, val int) {
        push(node, l, r)
        if l == r {
            tree[node] = val
        } else {
            mid := (l + r) / 2
            if idx <= mid {