Skip to Content
CTRL K

Range Xor Queries

Explicación

Cuando nos encontramos con consultas de rango, las sumas de prefijos deberían venir inmediatamente a la mente. Sin embargo, como tratamos con sumas XOR sobre un rango, tenemos que usar un arreglo de XOR de prefijos en lugar de un arreglo de sumas de prefijos. Para ello, podemos definir prefix\texttt{prefix} como un arreglo tal que prefix[i]=arr[0]⊕arr[1]⊕⋯⊕arr[i]\texttt{prefix}[i]= \texttt{arr}[0] \oplus \texttt{arr}[1] \oplus \dots \oplus \texttt{arr}[i]. Así, para cada consulta (a,b)(a, b), nuestra respuesta es simplemente prefix[a−1]⊕prefix[b]\texttt{prefix}[a-1]\oplus \texttt{prefix}[b].

Demostración

Sabemos que prefix[a−1]=arr[0]⊕arr[1]⊕⋯⊕arr[a−1]\texttt{prefix}[a-1]= \texttt{arr}[0] \oplus \texttt{arr}[1] \oplus \dots \oplus \texttt{arr}[a-1]. También sabemos que prefix[b]=arr[0]⊕arr[1]⊕⋯⊕arr[b]\texttt{prefix}[b]= \texttt{arr}[0] \oplus \texttt{arr}[1] \oplus \dots \oplus \texttt{arr}[b].

Por lo tanto, como x⊕x=0x\oplus x = 0 para cualquier xx:

prefix[a−1]⊕prefix[b]=arr[0]⊕arr[0]⊕arr[1]⊕arr[1]⊕⋯⊕arr[a−1]⊕arr[a−1]⏟cancels out to 0⊕arr[a]⊕arr[a+1]⋯⊕arr[b]\texttt{prefix}[a-1] \oplus \texttt{prefix}[b]= \underbrace{\texttt{arr}[0] \oplus \texttt{arr}[0] \oplus \texttt{arr}[1] \oplus \texttt{arr}[1] \oplus \dots \oplus \texttt{arr}[a-1] \oplus \texttt{arr}[a-1]}_{\text{cancels out to 0}} \oplus \texttt{arr}[a] \oplus \texttt{arr}[a+1] \dots \oplus \texttt{arr}[b].

Esto se simplifica a arr[a]⊕arr[a+1]⋯⊕arr[b]\texttt{arr}[a] \oplus \texttt{arr}[a+1] \dots \oplus \texttt{arr}[b], que es exactamente lo que buscamos.

Implementación

Complejidad temporal: O(N+Q)\mathcal{O}(N+Q)

#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 2e5;
 
int n, q, arr[MAX_N + 1], prefix[MAX_N + 1], a, b;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
	cin >> n >> q;
	// arr and prefix use 1-based indexing
	for (int i = 1; i <= n; ++i) { cin >> arr[i]; }
	// Build prefix XOR array
	prefix[1] = arr[1];
	for (int i = 2; i <= n; i++) { prefix[i] = prefix[i - 1] ^ arr[i]; }
 
	while (q--) {
		cin >> a >> b;
		cout << (prefix[a - 1] ^ prefix[b]) << endl;
	}
}
import java.io.*;
import java.util.*;
 
public class RangeXorQueries {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int q = io.nextInt();
 
		// arr and prefix use 1-based indexing
		int[] arr = new int[n + 1];
		for (int i = 1; i <= n; i++) { arr[i] = io.nextInt(); }
		// Build prefix XOR array
		int[] prefix = new int[n + 1];
		prefix[1] = arr[1];
		for (int i = 2; i <= n; i++) { prefix[i] = prefix[i - 1] ^ arr[i]; }
 
		for (int i = 0; i < q; i++) {
			int a = io.nextInt();
			int b = io.nextInt();
			io.println(prefix[a - 1] ^ prefix[b]);
		}
		io.close();
	}
 
	// CodeSnip{Kattio}
}
n, q = map(int, input().split())
arr = list(map(int, input().split()))
 
 
xor_arr = [0] * (n + 1)
for i in range(1, n + 1):
	xor_arr[i] = arr[i - 1] ^ xor_arr[i - 1]
 
for _ in range(q):
	a, b = map(int, input().split())
	print(xor_arr[b] ^ xor_arr[a - 1])
Fundamentos