LeetCode 3526 - Range XOR Queries with Subarray Reversals

The problem asks us to maintain a dynamic array of integers under three types of operations: point updates, range XOR queries, and in-place subarray reversals.

leetcodehardarraytreebinary-tree

LeetCode Problem 3526

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

Solution

Problem Understanding

The problem asks us to maintain a dynamic array of integers under three types of operations: point updates, range XOR queries, and in-place subarray reversals. We are required to process a sequence of queries and return the results of only the XOR range queries in the order they appear.

The input array nums represents an initial sequence. Each query either modifies a single element, computes the XOR over a contiguous range, or reverses a contiguous range of elements. The key difficulty is that reversals change the order of elements, which directly affects future range queries and updates because indices are positional, not value-based.

The constraints allow up to 100,000 elements and 100,000 queries, which makes any naive approach that performs O(n) operations per query infeasible. This immediately suggests that we need a data structure that supports efficient range operations and structural modifications.

Important edge cases include repeated reversals on overlapping ranges, updates after reversals, and queries over full array ranges. The problem guarantees valid indices and non-empty arrays, so we do not need to handle invalid access, but we must carefully maintain positional correctness under structural changes.

Approaches

A brute-force approach directly simulates each query on an array structure such as a Python list. Range XOR queries scan the subarray, reversals use slicing and reversing, and updates modify a single index. While simple, this approach becomes too slow because both range XOR and reversal are O(n) operations, leading to O(nq) worst-case complexity.

The key insight is that this is not just a static array problem, but a dynamic sequence problem where the positions of elements change. This strongly suggests using an implicit balanced binary search tree, specifically an implicit treap. In such a structure, the in-order traversal represents the array, and subtree operations correspond to range operations on indices.

We maintain subtree metadata such as size and XOR aggregate, and we use lazy propagation to support range reversal efficiently by toggling a reversal flag instead of physically reversing nodes. Range queries and updates are handled via split and merge operations, allowing all operations to run in logarithmic time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n · q) O(n) Direct simulation using slicing and scanning
Optimal (Implicit Treap) O(q log n) O(n) Supports dynamic sequence with lazy reverse and range XOR

Algorithm Walkthrough

We use an implicit treap where each node represents an element in the array, and the in-order traversal corresponds to the current array order.

  1. We build a treap from the initial array, where each node stores its value, subtree size, and subtree XOR. This structure allows us to compute XOR over any segment efficiently using stored aggregates.
  2. Each node maintains a lazy reversal flag. When a reversal is applied to a subtree, we do not physically reorder nodes. Instead, we toggle the flag and swap children when necessary during propagation. This ensures reversals remain O(1) amortized.
  3. To perform a range operation, we split the treap into three parts: left segment, middle segment, and right segment. The middle segment corresponds exactly to the queried range.
  4. For a range XOR query, after splitting, we directly read the XOR value stored at the root of the middle segment, then merge the segments back together.
  5. For a range reversal, we split similarly and toggle the reversal flag on the middle segment, then merge everything back. The structure ensures the segment is logically reversed without restructuring all nodes.
  6. For a point update, we split the treap to isolate the target index as a single node, update its value, recompute its metadata, and merge everything back.

Why it works is that the implicit treap maintains two invariants: the in-order traversal always represents the current array state, and each subtree correctly maintains aggregated XOR values under lazy propagation. This ensures that every operation manipulates structural segments without violating correctness.

Python Solution

from typing import List
import random

class Node:
    __slots__ = ("val", "prio", "left", "right", "size", "xor", "rev")

    def __init__(self, val):
        self.val = val
        self.prio = random.randint(1, 10**9)
        self.left = None
        self.right = None
        self.size = 1
        self.xor = val
        self.rev = False

def get_size(node):
    return node.size if node else 0

def get_xor(node):
    return node.xor if node else 0

def pull(node):
    if not node:
        return
    node.size = 1 + get_size(node.left) + get_size(node.right)
    node.xor = node.val ^ get_xor(node.left) ^ get_xor(node.right)

def push(node):
    if not node or not node.rev:
        return
    node.left, node.right = node.right, node.left
    if node.left:
        node.left.rev ^= True
    if node.right:
        node.right.rev ^= True
    node.rev = False

def split(node, k):
    if not node:
        return None, None
    push(node)
    if get_size(node.left) >= k:
        left, right = split(node.left, k)
        node.left = right
        pull(node)
        return left, node
    else:
        left, right = split(node.right, k - get_size(node.left) - 1)
        node.right = left
        pull(node)
        return node, right

def merge(left, right):
    if not left or not right:
        return left or right
    push(left)
    push(right)
    if left.prio > right.prio:
        left.right = merge(left.right, right)
        pull(left)
        return left
    else:
        right.left = merge(left, right.left)
        pull(right)
        return right

class Solution:
    def getResults(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        root = None

        for v in nums:
            root = merge(root, Node(v))

        res = []

        for q in queries:
            t = q[0]

            if t == 1:
                i, val = q[1], q[2]
                left, mid = split(root, i)
                mid, right = split(mid, 1)
                if mid:
                    mid.val = val
                    pull(mid)
                root = merge(merge(left, mid), right)

            elif t == 2:
                l, r = q[1], q[2]
                left, mid = split(root, l)
                mid, right = split(mid, r - l + 1)
                res.append(get_xor(mid))
                root = merge(merge(left, mid), right)

            else:
                l, r = q[1], q[2]
                left, mid = split(root, l)
                mid, right = split(mid, r - l + 1)
                if mid:
                    mid.rev ^= True
                root = merge(merge(left, mid), right)

        return res

The implementation builds an implicit treap over the array, then processes each query using split and merge operations. Range queries extract a subtree, read its stored XOR, and restore structure. Reversals toggle a lazy flag, and updates isolate a single node to modify its value safely.

Go Solution

package main

import "math/rand"

type Node struct {
	val   int
	pri   int
	left  *Node
	right *Node
	size  int
	xor   int
	rev   bool
}

func newNode(v int) *Node {
	return &Node{
		val: v,
		pri: rand.Int(),
		size: 1,
		xor: v,
	}
}

func getSize(n *Node) int {
	if n == nil {
		return 0
	}
	return n.size
}

func getXor(n *Node) int {
	if n == nil {
		return 0
	}
	return n.xor
}

func pull(n *Node) {
	if n == nil {
		return
	}
	n.size = 1 + getSize(n.left) + getSize(n.right)
	n.xor = n.val ^ getXor(n.left) ^ getXor(n.right)
}

func push(n *Node) {
	if n == nil || !n.rev {
		return
	}
	n.left, n.right = n.right, n.left
	if n.left != nil {
		n.left.rev = !n.left.rev
	}
	if n.right != nil {
		n.right.rev = !n.right.rev
	}
	n.rev = false
}

func split(n *Node, k int) (*Node, *Node) {
	if n == nil {
		return nil, nil
	}
	push(n)
	if getSize(n.left) >= k {
		l, r := split(n.left, k)
		n.left = r
		pull(n)
		return l, n
	}
	l, r := split(n.right, k-getSize(n.left)-1)
	n.right = l
	pull(n)
	return n, r
}

func merge(a, b *Node) *Node {
	if a == nil || b == nil {
		if a != nil {
			return a
		}
		return b
	}
	push(a)
	push(b)
	if a.pri > b.pri {
		a.right = merge(a.right, b)
		pull(a)
		return a
	}
	b.left = merge(a, b.left)
	pull(b)
	return b
}

func getResults(nums []int, queries [][]int) []int {
	var root *Node

	for _, v := range nums {
		root = merge(root, newNode(v))
	}

	var res []int

	for _, q := range queries {
		t := q[0]

		if t == 1 {
			i, val := q[1], q[2]
			l, mid := split(root, i)
			mid, r := split(mid, 1)
			if mid != nil {
				mid.val = val
				pull(mid)
			}
			root = merge(merge(l, mid), r)
		} else if t == 2 {
			l, r := q[1], q[2]
			a, b := split(root, l)
			b, c := split(b, r-l+1)
			if b != nil {
				res = append(res, b.xor)
			} else {
				res = append(res, 0)
			}
			root = merge(merge(a, b), c)
		} else {
			l, r := q[1], q[2]
			a, b := split(root, l)
			b, c := split(b, r-l+1)
			if b != nil {
				b.rev = !b.rev
			}
			root = merge(merge(a, b), c)
		}
	}

	return res
}

Go differs mainly in manual memory management style and lack of generics for node utilities. We also explicitly handle nil checks more frequently, and XOR initialization must be carefully preserved when nodes are merged or updated.

Worked Examples

For the first example, we start with nums = [1,2,3,4,5].

After building the treap, the in-order sequence is [1,2,3,4,5].

For query [2,1,3], we split into [1], [2,3,4], [5]. The middle subtree stores XOR of 2 ^ 3 ^ 4 = 5, so we output 5.

For [1,2,10], we isolate index 2 (0-based), split into [1,2], [3], [4,5], update node value from 3 to 10, then merge back. The array becomes [1,2,10,4,5].

For [3,0,4], we split into [], [1,2,10,4,5], [] and toggle reverse flag. The logical order becomes [5,4,10,2,1].

For [2,0,4], we query full range, so XOR is 5 ^ 4 ^ 10 ^ 2 ^ 1 = 8.

Complexity Analysis

Measure Complexity Explanation
Time O(q log n) Each split/merge operation is logarithmic in treap height
Space O(n) One node per array element plus recursion stack

The logarithmic factor comes from the balanced nature of the randomized treap. Each query performs a constant number of split and merge operations, each taking O(log n) amortized time.

Test Cases

assert Solution().getResults([1,2,3,4,5], [[2,1,3],[1,2,10],[3,0,4],[2,0,4]]) == [5,8]  # sample case
assert Solution().getResults([7,8,9], [[1,0,3],[2,0,2],[3,1,2]]) == [2]  # sample case
assert Solution().getResults([5], [[2,0,0]]) == [5]  # single element query
assert Solution().getResults([1,2,3], [[3,0,2],[2,0,2]]) == [0]  # full reverse then XOR same
assert Solution().getResults([1,1,1], [[2,0,2],[3,0,2],[2,0,2]]) == [1,1]  # reverse does not change XOR
Test Why
single element validates minimal structure handling
full reverse then query ensures reversal logic correctness
repeated identical values checks XOR stability
sample cases validates baseline correctness

Edge Cases

A key edge case is a reversal over the entire array. This stresses whether the lazy propagation correctly flips subtree structure without losing XOR metadata. If push logic is incorrect, the XOR values will become inconsistent after multiple reversals.

Another edge case is repeated updates on the same index after multiple reversals. Because indices are positional, not value-based, incorrect split logic can easily update the wrong node if the implicit ordering is not maintained precisely.

A third edge case involves alternating operations on small segments, such as reversing single-element or two-element ranges repeatedly. This tests whether the reversal flag is correctly propagated and cleared, since stale lazy flags can silently corrupt future queries.