XOR de un subarreglo (rango de elementos) | conjunto 2

Dada una array entera arr[] de consultas de tamaño N y Q. Cada consulta tiene la forma (L, R) , donde L y R son índices de la array. La tarea es encontrar el valor XOR del subarreglo arr[L…R] . 

Ejemplos:  

Entrada: arr[] = {2, 5, 1, 6, 1, 2, 5} consulta[] = {{1, 4}} 
Salida: 3 
El valor XOR de arr[1…4] es 3.

Entrada: arr[] = {2, 5, 1, 6, 1, 2, 5} consulta[] = {{0, 6}} 
Salida: 6 
El valor XOR de arr[0…6] es 6.  

Aproximación al espacio auxiliar O(N): Consulte este artículo para obtener información sobre la aproximación al espacio auxiliar O(N).

Enfoque: aquí discutiremos una solución de espacio constante, pero modificaremos la array de entrada.  

1. Actualice la array de entrada del índice 1 a N – 1 , de modo que arr[i] almacene el XOR de arr[0] a arr[i] . 

array[i] = XOR(array[0], array[1], .., array[i]) 
 

2. Para procesar una consulta de L a R simplemente devuelva arr[L-1] ^ arr[R] .

Por ejemplo:  

Considere el ejemplo: arr[] = { 3, 2, 4, 5, 1, 1, 5, 3 }, query[] = {{1, 4 }, { 3, 7}} 
Después de tomar el XOR de elementos consecutivos , arr[] = {3, 1, 5, 0, 1, 0, 5, 6} 
Para la primera consulta {1, 4} ans = arr[0] ^ arr[4] = 3 ^ 1 = 2 
Para la segunda consulta {3, 7} respuesta = arr[2] ^ arr[7] = 5 ^ 6 = 3  

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to find XOR
// in a range from L to R
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find XOR
// in a range from L to R
void find_Xor(int arr[],
              pair<int, int> query[],
              int N, int Q)
{
    // Compute xor from arr[0] to arr[i]
    for (int i = 1; i < N; i++) {
        arr[i] = arr[i] ^ arr[i - 1];
    }
 
    int ans = 0;
 
    // process every query
    // in constant time
    for (int i = 0; i < Q; i++) {
 
        // if L==0
        if (query[i].first == 0)
            ans = arr[query[i].second];
        else
            ans = arr[query[i].first - 1]
                  ^ arr[query[i].second];
 
        cout << ans << endl;
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 2, 4, 5,
                  1, 1, 5, 3 };
    int N = 8;
    int Q = 2;
    pair<int, int> query[Q]
        = { { 1, 4 },
            { 3, 7 } };
 
    // query[]
    find_Xor(arr, query, N, Q);
    return 0;
}

// Java program to find XOR
// in a range from L to R
class GFG{
     
static class pair
{
    int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to find XOR
// in a range from L to R
static void find_Xor(int arr[],
                     pair query[],
                     int N, int Q)
{
     
    // Compute xor from arr[0] to arr[i]
    for(int i = 1; i < N; i++)
    {
       arr[i] = arr[i] ^ arr[i - 1];
    }
     
    int ans = 0;
 
    // Process every query
    // in constant time
    for(int i = 0; i < Q; i++)
    {
         
       // If L==0
       if (query[i].first == 0)
           ans = arr[query[i].second];
       else
           ans = arr[query[i].first - 1] ^
                 arr[query[i].second];
 
       System.out.print(ans + "\n");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 3, 2, 4, 5,
                  1, 1, 5, 3 };
    int N = 8;
    int Q = 2;
     
    pair query[] = { new pair(1, 4),
                     new pair(3, 7) };
 
    // query[]
    find_Xor(arr, query, N, Q);
}
}
 
// This code is contributed by gauravrajput1

# Python3 program to find XOR
# in a range from L to R
 
# Function to find XOR
# in a range from L to R
def find_Xor(arr, query, N, Q):
     
    # Compute xor from arr[0] to arr[i]
    for i in range(1, N):
        arr[i] = arr[i] ^ arr[i - 1]
         
    ans = 0
     
    # Process every query
    # in constant time
    for i in range(Q):
         
        # If L == 0
        if query[i][0] == 0:
            ans = arr[query[i][1]]
        else:
            ans = (arr[query[i][0] - 1] ^
                   arr[query[i][1]])
        print(ans)
     
# Driver code
def main():
     
    arr = [ 3, 2, 4, 5, 1, 1, 5, 3 ]
    N = 8
    Q = 2
     
    # query[]
    query = [ [ 1, 4 ],
              [ 3, 7 ] ]
               
    find_Xor(arr, query, N, Q)
     
main()
 
# This code is contributed by Stuti Pathak

// C# program to find XOR
// in a range from L to R
using System;
 
class GFG{   
class pair
{
    public int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
  
// Function to find XOR
// in a range from L to R
static void find_Xor(int []arr,
                     pair []query,
                     int N, int Q)
{
      
    // Compute xor from arr[0] to arr[i]
    for(int i = 1; i < N; i++)
    {
       arr[i] = arr[i] ^ arr[i - 1];
    }
      
    int ans = 0;
  
    // Process every query
    // in constant time
    for(int i = 0; i < Q; i++)
    {
          
       // If L==0
       if (query[i].first == 0)
           ans = arr[query[i].second];
       else
           ans = arr[query[i].first - 1] ^
                 arr[query[i].second];
  
       Console.Write(ans + "\n");
    }
}
  
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 3, 2, 4, 5,
                  1, 1, 5, 3 };
    int N = 8;
    int Q = 2;
      
    pair []query = { new pair(1, 4),
                     new pair(3, 7) };
  
    // query[]
    find_Xor(arr, query, N, Q);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program to find XOR
// in a range from L to R
 
// Function to find XOR
// in a range from L to R
function find_Xor(arr, query, N, Q)
{
    // Compute xor from arr[0] to arr[i]
    for (var i = 1; i < N; i++) {
        arr[i] = arr[i] ^ arr[i - 1];
    }
 
    var ans = 0;
 
    // process every query
    // in constant time
    for (var i = 0; i < Q; i++) {
 
        // if L==0
        if (query[i][0] == 0)
            ans = arr[query[i][1]];
        else
            ans = arr[query[i][0] - 1]
                  ^ arr[query[i][1]];
 
        document.write( ans + "<br>");
    }
}
 
// Driver Code
var arr = [3, 2, 4, 5,
              1, 1, 5, 3];
var N = 8;
var Q = 2;
var query
    = [[1, 4],
        [3, 7]];
// query[]
find_Xor(arr, query, N, Q);
 
 
</script>

2
3

Complejidad Temporal: O (N + Q)  
Espacio Auxiliar: O (1)