Considere un arr[] que se puede definir como:
Se le dan Q consultas de la forma [l, r] . La tarea es generar el valor de arr[l] ⊕ arr[l+1] ⊕ ….. ⊕ arr[r-1] ⊕ arr[r] para cada consulta.
Ejemplos:
Input : q = 3 q1 = { 2, 4 } q2 = { 2, 8 } q3 = { 5, 9 } Output : 7 9 15 The beginning of the array with constraint look like: arr[] = { 0, 1, 3, 0, 4, 1, 7, 0, 8, 1, 11, .... } For q1, 3 ⊕ 0 ⊕ 4 = 7 For q2, 3 ⊕ 0 ⊕ 4 ⊕ 1 ⊕ 7 ⊕ 0 ⊕ 8 = 9 For q3, 1 ⊕ 7 ⊕ 0 ⊕ 8 ⊕ 1 = 15
Observemos arr[]
arr[0] = 0 arr[1] = 1 arr[2] = 1 ⊕ 2 arr[3] = 1 ⊕ 2 ⊕ 3 arr[4] = 1 ⊕ 2 ⊕ 3 ⊕ 4 arr[5] = 1 ⊕ 2 ⊕ 3 ⊕ 4 ⊕ 5 ....
Hagamos otra array, digamos brr[], donde brr[i] = arr[0] ⊕ arr[1] ⊕ arr[2] ⊕ ….. ⊕ arr[i].
brr[i] = arr[0] ⊕ arr[1] ⊕ arr[2] ⊕ … ⊕ arr[i-1] ⊕ arr[i] = brr[j] ⊕ arr[j+1] ⊕ arr[j+ 2] ⊕ ….. ⊕ arr[i], para cualquier 0 <= j <= i.
Entonces, arr[l] ⊕ arr[l+1] ⊕ ….. ⊕ arr[r] = brr[l-1] ⊕ brr[r].
Ahora, observemos brr[]:
brr[1] = 1 brr[2] = 2 brr[3] = 1 ⊕ 3 brr[4] = 2 ⊕ 4 brr[5] = 1 ⊕ 3 ⊕ 5 brr[6] = 2 ⊕ 4 ⊕ 6 brr[7] = 1 ⊕ 3 ⊕ 5 ⊕ 7 brr[8] = 2 ⊕ 4 ⊕ 6 ⊕ 8
Es fácil observar que en índices impares brr[i] = 1 ⊕ 3 ⊕ 5 ⊕ …. ⊕ i y para índices pares brr[i] = 2 ⊕ 4 ⊕ 6 ⊕ …. ⊕ yo.
Para índices pares hay números de 1 a i/2 multiplicados por 2, lo que significa que los bits se mueven a la izquierda por 1, entonces, brr[i] = 2 ⊕ 4 ⊕ 6 ⊕ …. ⊕ i = (1 ⊕ 2 ⊕ 3 ⊕ ….. ⊕ i/2) * 2.
Y para índices impares hay números de 0 a (i – 1)/2 multiplicados por 2 y más 1. Eso significa que los bits se mueven a la izquierda por 1, y el último bit se convierte en 1. Entonces, brr[i] = 1 ⊕ 3 ⊕ 5 ⊕ …. ⊕ yo = (0 ⊕ 1 ⊕ 2 ⊕ …. ⊕ (i – 1)/2) * 2 + x.
x es 1 ⊕ 1 ⊕ 1 ⊕ ….. ⊕ 1 “unos” se repiten (i – 1)/2 + 1 veces. Entonces, si (i-1)/2 + 1 es impar entonces x = 1 sino x = 0.
Ahora, cálculo de 1 ⊕ 2 ⊕ 3 ⊕ …. ⊕ X.
Probemos que (4K) ⊕ (4K + 1) ⊕ (4K + 2) ⊕ (4K + 3) = 0 para 0 <= k.
bitmask(K)00=4K xorsum bitmask(K)01=4K+1 bitmask(K)10=4K+2 bitmask(K)11=4k+3 --------------------- 000000000000=0
Entonces como 0 ⊕ Y = Y entonces 1 ⊕ 2 ⊕ 3 ⊕ … ⊕ x = (piso(x/4) x 4) ⊕ … ⊕ x aquí hay un máximo de 3 números para que podamos calcular en O(1).
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program to solve range query on array // whose each element is XOR of index value // and previous element. #include <bits/stdc++.h> using namespace std; // function return derived formula value. int fun(int x) { int y = (x / 4) * 4; // finding xor value of range [y...x] int ans = 0; for (int i = y; i <= x; i++) ans ^= i; return ans; } // function to solve query for l and r. int query(int x) { // if l or r is 0. if (x == 0) return 0; int k = (x + 1) / 2; // finding x is divisible by 2 or not. return (x %= 2) ? 2 * fun(k) : ((fun(k - 1) * 2) ^ (k & 1)); } void allQueries(int q, int l[], int r[]) { for (int i = 0; i < q; i++) cout << (query(r[i]) ^ query(l[i] - 1)) << endl; } // Driven Program int main() { int q = 3; int l[] = { 2, 2, 5 }; int r[] = { 4, 8, 9 }; allQueries(q, l, r); return 0; }
Java
// Java Program to solve range query on array // whose each element is XOR of index value // and previous element. import java.io.*; class GFG { // function return derived formula value. static int fun(int x) { int y = (x / 4) * 4; // finding xor value of range [y...x] int ans = 0; for (int i = y; i <= x; i++) ans ^= i; return ans; } // function to solve query for l and r. static int query(int x) { // if l or r is 0. if (x == 0) return 0; int k = (x + 1) / 2; // finding x is divisible by 2 or not. return ((x %= 2) != 0) ? 2 * fun(k) : ((fun(k - 1) * 2) ^ (k & 1)); } static void allQueries(int q, int l[], int r[]) { for (int i = 0; i < q; i++) System.out.println((query(r[i]) ^ query(l[i] - 1))) ; } // Driven Program public static void main (String[] args) { int q = 3; int []l = { 2, 2, 5 }; int []r = { 4, 8, 9 }; allQueries(q, l, r); } } // This code is contributed by vt_m.
Python3
# Python3 Program to solve range query # on array whose each element is XOR of # index value and previous element. # function return derived formula value. def fun(x): y = (x // 4) * 4 # finding xor value of range [y...x] ans = 0 for i in range(y, x + 1): ans ^= i return ans # function to solve query for l and r. def query(x): # if l or r is 0. if (x == 0): return 0 k = (x + 1) // 2 # finding x is divisible by 2 or not. if x % 2 == 0: return((fun(k - 1) * 2) ^ (k & 1)) else: return(2 * fun(k)) def allQueries(q, l, r): for i in range(q): print(query(r[i]) ^ query(l[i] - 1)) # Driver Code q = 3 l = [ 2, 2, 5 ] r = [ 4, 8, 9 ] allQueries(q, l, r) # This code is contributed # by sahishelangia
C#
// C# Program to solve range query on array // whose each element is XOR of index value // and previous element. using System; class GFG { // function return derived formula value. static int fun(int x) { int y = (x / 4) * 4; // finding xor value of range [y...x] int ans = 0; for (int i = y; i <= x; i++) ans ^= i; return ans; } // function to solve query for l and r. static int query(int x) { // if l or r is 0. if (x == 0) return 0; int k = (x + 1) / 2; // finding x is divisible by 2 or not. return ((x %= 2)!=0) ? 2 * fun(k) : ((fun(k - 1) * 2) ^ (k & 1)); } static void allQueries(int q, int []l, int []r) { for (int i = 0; i < q; i++) Console.WriteLine((query(r[i]) ^ query(l[i] - 1))) ; } // Driven Program public static void Main () { int q = 3; int []l = { 2, 2, 5 }; int []r = { 4, 8, 9 }; allQueries(q, l, r); } } // This code is contributed by vt_m.
PHP
<?php // PHP Program to solve range // query on array whose each // element is XOR of index // value and previous element. // function return derived // formula value. function fun($x) { $y = ((int)($x / 4) * 4); // finding xor value // of range [y...x] $ans = 0; for ($i = $y; $i <= $x; $i++) $ans ^= $i; return $ans; } // function to solve // query for l and r. function query($x) { // if l or r is 0. if ($x == 0) return 0; $k = (int)(($x + 1) / 2); // finding x is divisible // by 2 or not. return ($x %= 2) ? 2 * fun($k) : ((fun($k - 1) * 2) ^ ($k & 1)); } function allQueries($q, $l, $r) { for ($i = 0; $i < $q; $i++) echo (query($r[$i]) ^ query($l[$i] - 1)) , "\n"; } // Driver Code $q = 3; $l = array( 2, 2, 5 ); $r = array ( 4, 8, 9 ); allQueries($q, $l, $r); // This code is contributed by ajit ?>
Javascript
<script> // Javascript Program to solve range query on array // whose each element is XOR of index value // function return derived formula value. function fun(x) { let y = parseInt(x / 4) * 4; // finding xor value of range [y...x] let ans = 0; for (let i = y; i <= x; i++) ans ^= i; return ans; } // function to solve query for l and r. function query(x) { // if l or r is 0. if (x == 0) return 0; let k = parseInt((x + 1) / 2); // finding x is divisible by 2 or not. return (x %= 2) ? 2 * fun(k) : ((fun(k - 1) * 2) ^ (k & 1)); } function allQueries(q, l, r) { for (let i = 0; i < q; i++) document.write((query(r[i]) ^ query(l[i] - 1)) + "<br>"); } // Driven Program let q = 3; let l = [ 2, 2, 5 ]; let r = [ 4, 8, 9 ]; allQueries(q, l, r); </script>
Producción :
0 2 0