# [1310. XOR Queries of a Subarray](https://leetcode.com/problems/xor-queries-of-a-subarray/description)

# 1. Tóm tắt đề bài

Cho một mảng $arr$ gồm các số nguyên dương. Có $Q$ truy vấn, mỗi truy vấn hỏi $[L, R]$, và bạn phải tính tổng $xor$ của các phần tử từ $L$ đến $R$ trong dãy $arr$.

##### Giới hạn

$1 \le |arr| \le 30000$
$1 \le q \le 30000$
$1 \le arr_i \le 10^9$

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(n + q)$**

Ta có tính chất sau:

- $a \oplus b = c$
- $b \oplus c = a$
- $c \oplus a = b$

Vì vậy, khi mà ta áp dụng prefix sum trên $arr$ (đặt là $psum$), ta có thể tính được tổng xor trong đoạn từ $L$ đến $R$ trong $O(1)$, bằng công thức $arr_R \oplus arr_{L - 1}$.

# 3. Lời giải chi tiết

Sau khi ra được ý tưởng, lời giải trở nên chỉ còn 2 bước khá đơn giản:

- Tính mảng $psum$.
- Dựa vào công thức tính kết quả cho từng query.

Code mẫu (Golang):

func xorQueries(arr []int, queries [][]int) []int {
    n := len(arr)
    psum := make([]int, n + 1)
    for i := 0; i < n; i++ {
        psum[i + 1] = psum[i] ^ arr[i]
    }
    res := make([]int, 0)
    for _, c := range queries {
        res = append(res, psum[c[1] + 1] ^ psum[c[0]])
    }
    return res
}

### Độ phức tạp thuật toán

Thời gian: $O(n)$

Bộ nhớ mở rộng: $O(n)$