Problem

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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6

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​

Solution

Method 1 – Segment Tree with Lazy Propagation

Intuition

The problem requires efficiently handling range XOR queries and subarray reversals. A segment tree with lazy propagation can efficiently support both range XOR and range reverse operations by maintaining additional information for each segment.

Approach

  1. Build a segment tree where each node stores the XOR of its segment and a flag for pending reversals.
  2. For a range reversal, propagate the reversal flag down the tree and swap children as needed.
  3. For a range XOR query, use the segment tree to get the XOR in O(log n) time, considering any pending reversals.
  4. Use lazy propagation to ensure all operations are efficient.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// This is a template for the solution. Actual implementation may vary based on the problem's API.
class Solution {
public:
    // Assume arr is the array, queries is a list of queries
    // Each query: [type, l, r] where type=1 for reverse, type=2 for xor query
    // Returns vector<int> for xor queries
    struct Node {
        int l, r, x;
        bool rev;
        Node *left, *right;
        Node(int l, int r): l(l), r(r), x(0), rev(false), left(nullptr), right(nullptr) {}
    };
    Node* build(vector<int>& arr, int l, int r) {
        Node* node = new Node(l, r);
        if (l == r) { node->x = arr[l]; return node; }
        int m = (l + r) / 2;
        node->left = build(arr, l, m);
        node->right = build(arr, m+1, r);
        node->x = node->left->x ^ node->right->x;
        return node;
    }
    void push(Node* node) {
        if (node->rev) {
            swap(node->left, node->right);
            if (node->left) node->left->rev ^= 1;
            if (node->right) node->right->rev ^= 1;
            node->rev = false;
        }
    }
    void reverse(Node* node, int l, int r) {
        if (node->r < l || node->l > r) return;
        if (l <= node->l && node->r <= r) { node->rev ^= 1; return; }
        push(node);
        reverse(node->left, l, r);
        reverse(node->right, l, r);
        node->x = node->left->x ^ node->right->x;
    }
    int query(Node* node, int l, int r) {
        if (node->r < l || node->l > r) return 0;
        if (l <= node->l && node->r <= r) return node->x;
        push(node);
        return query(node->left, l, r) ^ query(node->right, l, r);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

// This is a template for the solution. Actual implementation may vary based on the problem's API.
type Node struct {
    l, r int
    x int
    rev bool
    left, right *Node
}
func build(arr []int, l, r int) *Node {
    node := &Node{l: l, r: r}
    if l == r {
        node.x = arr[l]
        return node
    }
    m := (l + r) / 2
    node.left = build(arr, l, m)
    node.right = build(arr, m+1, r)
    node.x = node.left.x ^ node.right.x
    return node
}
func push(node *Node) {
    if node.rev {
        node.left, node.right = node.right, node.left
        if node.left != nil {
            node.left.rev = !node.left.rev
        }
        if node.right != nil {
            node.right.rev = !node.right.rev
        }
        node.rev = false
    }
}
func reverse(node *Node, l, r int) {
    if node.r < l || node.l > r {
        return
    }
    if l <= node.l && node.r <= r {
        node.rev = !node.rev
        return
    }
    push(node)
    reverse(node.left, l, r)
    reverse(node.right, l, r)
    node.x = node.left.x ^ node.right.x
}
func query(node *Node, l, r int) int {
    if node.r < l || node.l > r {
        return 0
    }
    if l <= node.l && node.r <= r {
        return node.x
    }
    push(node)
    return query(node.left, l, r) ^ query(node.right, l, r)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// This is a template for the solution. Actual implementation may vary based on the problem's API.
class Solution {
    class Node {
        int l, r, x;
        boolean rev;
        Node left, right;
        Node(int l, int r) { this.l = l; this.r = r; }
    }
    Node build(int[] arr, int l, int r) {
        Node node = new Node(l, r);
        if (l == r) { node.x = arr[l]; return node; }
        int m = (l + r) / 2;
        node.left = build(arr, l, m);
        node.right = build(arr, m+1, r);
        node.x = node.left.x ^ node.right.x;
        return node;
    }
    void push(Node node) {
        if (node.rev) {
            Node tmp = node.left; node.left = node.right; node.right = tmp;
            if (node.left != null) node.left.rev ^= true;
            if (node.right != null) node.right.rev ^= true;
            node.rev = false;
        }
    }
    void reverse(Node node, int l, int r) {
        if (node.r < l || node.l > r) return;
        if (l <= node.l && node.r <= r) { node.rev ^= true; return; }
        push(node);
        reverse(node.left, l, r);
        reverse(node.right, l, r);
        node.x = node.left.x ^ node.right.x;
    }
    int query(Node node, int l, int r) {
        if (node.r < l || node.l > r) return 0;
        if (l <= node.l && node.r <= r) return node.x;
        push(node);
        return query(node.left, l, r) ^ query(node.right, l, r);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// This is a template for the solution. Actual implementation may vary based on the problem's API.
class Solution {
    inner class Node(val l: Int, val r: Int) {
        var x = 0
        var rev = false
        var left: Node? = null
        var right: Node? = null
    }
    fun build(arr: IntArray, l: Int, r: Int): Node {
        val node = Node(l, r)
        if (l == r) { node.x = arr[l]; return node }
        val m = (l + r) / 2
        node.left = build(arr, l, m)
        node.right = build(arr, m+1, r)
        node.x = node.left!!.x xor node.right!!.x
        return node
    }
    fun push(node: Node) {
        if (node.rev) {
            val tmp = node.left; node.left = node.right; node.right = tmp
            node.left?.rev = node.left?.rev != false
            node.right?.rev = node.right?.rev != false
            node.rev = false
        }
    }
    fun reverse(node: Node, l: Int, r: Int) {
        if (node.r < l || node.l > r) return
        if (l <= node.l && node.r <= r) { node.rev = !node.rev; return }
        push(node)
        reverse(node.left!!, l, r)
        reverse(node.right!!, l, r)
        node.x = node.left!!.x xor node.right!!.x
    }
    fun query(node: Node, l: Int, r: Int): Int {
        if (node.r < l || node.l > r) return 0
        if (l <= node.l && node.r <= r) return node.x
        push(node)
        return query(node.left!!, l, r) xor query(node.right!!, l, r)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# This is a template for the solution. Actual implementation may vary based on the problem's API.
from typing import List
class Node:
    def __init__(self, l: int, r: int):
        self.l = l
        self.r = r
        self.x = 0
        self.rev = False
        self.left = None
        self.right = None
def build(arr: List[int], l: int, r: int) -> Node:
    node = Node(l, r)
    if l == r:
        node.x = arr[l]
        return node
    m = (l + r) // 2
    node.left = build(arr, l, m)
    node.right = build(arr, m+1, r)
    node.x = node.left.x ^ node.right.x
    return node
def push(node: Node):
    if node.rev:
        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 reverse(node: Node, l: int, r: int):
    if node.r < l or node.l > r:
        return
    if l <= node.l and node.r <= r:
        node.rev ^= True
        return
    push(node)
    reverse(node.left, l, r)
    reverse(node.right, l, r)
    node.x = node.left.x ^ node.right.x
def query(node: Node, l: int, r: int) -> int:
    if node.r < l or node.l > r:
        return 0
    if l <= node.l and node.r <= r:
        return node.x
    push(node)
    return query(node.left, l, r) ^ query(node.right, l, r)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// This is a template for the solution. Actual implementation may vary based on the problem's API.
struct Node {
    l: usize,
    r: usize,
    x: i32,
    rev: bool,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}
impl Node {
    fn build(arr: &[i32], l: usize, r: usize) -> Box<Node> {
        let mut node = Box::new(Node { l, r, x: 0, rev: false, left: None, right: None });
        if l == r {
            node.x = arr[l];
            return node;
        }
        let m = (l + r) / 2;
        node.left = Some(Node::build(arr, l, m));
        node.right = Some(Node::build(arr, m+1, r));
        node.x = node.left.as_ref().unwrap().x ^ node.right.as_ref().unwrap().x;
        node
    }
    fn push(node: &mut Box<Node>) {
        if node.rev {
            std::mem::swap(&mut node.left, &mut node.right);
            if let Some(ref mut l) = node.left { l.rev ^= true; }
            if let Some(ref mut r) = node.right { r.rev ^= true; }
            node.rev = false;
        }
    }
    fn reverse(node: &mut Box<Node>, l: usize, r: usize) {
        if node.r < l || node.l > r { return; }
        if l <= node.l && node.r <= r { node.rev ^= true; return; }
        Node::push(node);
        Node::reverse(node.left.as_mut().unwrap(), l, r);
        Node::reverse(node.right.as_mut().unwrap(), l, r);
        node.x = node.left.as_ref().unwrap().x ^ node.right.as_ref().unwrap().x;
    }
    fn query(node: &mut Box<Node>, l: usize, r: usize) -> i32 {
        if node.r < l || node.l > r { return 0; }
        if l <= node.l && node.r <= r { return node.x; }
        Node::push(node);
        Node::query(node.left.as_mut().unwrap(), l, r) ^ Node::query(node.right.as_mut().unwrap(), l, r)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// This is a template for the solution. Actual implementation may vary based on the problem's API.
class Node {
    l: number; r: number; x: number; rev: boolean;
    left: Node | null; right: Node | null;
    constructor(l: number, r: number) {
        this.l = l; this.r = r; this.x = 0; this.rev = false;
        this.left = null; this.right = null;
    }
}
function build(arr: number[], l: number, r: number): Node {
    const node = new Node(l, r);
    if (l === r) { node.x = arr[l]; return node; }
    const m = Math.floor((l + r) / 2);
    node.left = build(arr, l, m);
    node.right = build(arr, m+1, r);
    node.x = node.left.x ^ node.right.x;
    return node;
}
function push(node: Node) {
    if (node.rev) {
        [node.left, node.right] = [node.right, node.left];
        if (node.left) node.left.rev = !node.left.rev;
        if (node.right) node.right.rev = !node.right.rev;
        node.rev = false;
    }
}
function reverse(node: Node, l: number, r: number) {
    if (node.r < l || node.l > r) return;
    if (l <= node.l && node.r <= r) { node.rev = !node.rev; return; }
    push(node);
    reverse(node.left!, l, r);
    reverse(node.right!, l, r);
    node.x = node.left!.x ^ node.right!.x;
}
function query(node: Node, l: number, r: number): number {
    if (node.r < l || node.l > r) return 0;
    if (l <= node.l && node.r <= r) return node.x;
    push(node);
    return query(node.left!, l, r) ^ query(node.right!, l, r);
}

Complexity

  • ⏰ Time complexity: O(log n) per query or update, since each operation traverses the height of the segment tree.
  • 🧺 Space complexity: O(n), for the segment tree nodes.