XOR de consultas de una subarray

Dada una array N * N y consultas q , cada una de las cuales contiene la posición de la esquina superior izquierda e inferior derecha de una subarray rectangular, la tarea es encontrar el xor de todos los elementos de esta subarray.
Ejemplos:

Entrada: arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, q[] = {{1, 1, 2, 2}, { 1, 2, 2, 2}}
Salida:
2
15
Consulta 1: 5 ^ 6 ^ 8 ^ 9 = 2
Consulta 2: 6 ^ 9 = 15
Entrada: arr[][] = {{21, 2}, { 14 , 5}}, q[] = {{0, 1, 1, 1}, {0, 0, 1, 1}}
Salida:
7
28

Una solución simple es encontrar el XOR de toda la subarray para cada consulta. Por lo tanto, la complejidad temporal del peor de los casos para cada consulta será O(n ² ).
Enfoque eficiente: todos estamos familiarizados con la idea del prefijo XOR en una array lineal, es decir

si arr[] = {1, 2, 3, 4} y calculamos prefixXOR[] = {1, 3, 0, 4} donde prefixXOR[i] almacena el XOR de los valores de arr[0] a arr[i]
Entonces, el XOR de la subarray array[i] a la array[j] se puede encontrar como prefijoXOR[j] ^ prefijoXOR[i – 1]
Por ejemplo, el XOR de la subarray {2, 3} será XOR(0 , 1) = 1
Esto se debe a que en los valores de prefijo XOR para {1, 2, 3} y {1}, el valor 1 se repitió dos veces, lo que dará 0 como resultado XOR y no afectará el valor de las otras operaciones XOR. .

Intentaremos extender lo mismo a la array 2-D. Calcularemos una array prefijo-XOR que nos ayudará a resolver cada consulta en O(1).
En este caso, nuestra array XOR de prefijo en la posición (R, C) almacenará el XOR de la subarray rectangular con la esquina superior izquierda en (0, 0) y la esquina inferior derecha en (R, C).
Calculamos el prefijo-XOR en dos pasos.

Calcule el prefijo-XOR para cada fila de la array original de izquierda a derecha.
En la array anterior, calcule el prefijo XOR para cada columna de arriba a abajo.

Una vez que tenemos el prefijo XOR-array requerido, podemos responder las consultas con sencillez. El XOR de una subarray de (R1, C1) a (R2, C2) se puede calcular como prefix_xor[R2][C2] ^ prefix_xor[R1 – 1][C2] ^ prefix_xor[R2][C1 – 1] ^ prefijo_xor[R1 – 1][C1 – 1] .
Nota: si R1 o C1 es igual a 0, entonces R1 – 1 o C1 – 1 también debería ser 0.
A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation of the approach
#include <iostream>
#define n 3
using namespace std;
 
// Function to pre-compute the xor
void preComputeXor(int arr[][n], int prefix_xor[][n])
{
    // Left to right prefix xor
    // for each row
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (j == 0)
                prefix_xor[i][j] = arr[i][j];
            else
                prefix_xor[i][j]
                    = (prefix_xor[i][j - 1] ^ arr[i][j]);
        }
 
    // Top to bottom prefix xor
    // for each column
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            prefix_xor[j][i]
                = (prefix_xor[j - 1][i] ^ prefix_xor[j][i]);
}
 
// Function to process the queries
// x1, x2, y1, y2 represent the
// positions of the top-left
// and bottom right corners
int ansQuerie(int prefix_xor[][n], int x1, int y1, int x2, int y2)
{
 
    // To store the xor values
    int xor_1 = 0, xor_2 = 0, xor_3 = 0;
 
    // Finding the values we need to xor
    // with value at (x2, y2) in prefix-xor
    // matrix
    if (x1 != 0)
        xor_1 = prefix_xor[x1 - 1][y2];
    if (y1 != 0)
        xor_2 = prefix_xor[x2][y1 - 1];
    if (x1 != 0 and y1 != 0)
        xor_3 = prefix_xor[x1 - 1][y1 - 1];
 
    // Return the required prefix xor
    return ((prefix_xor[x2][y2] ^ xor_1) ^ (xor_2 ^ xor_3));
}
 
// Driver code
int main()
{
    int arr[][n] = { { 1, 2, 3 },
                     { 4, 5, 6 },
                     { 7, 8, 9 } };
 
    // To store pre-computed xor
    int prefix_xor[n][n];
 
    // Pre-computing xor
    preComputeXor(arr, prefix_xor);
 
    // Queries
    cout << ansQuerie(prefix_xor, 1, 1, 2, 2) << endl;
    cout << ansQuerie(prefix_xor, 1, 2, 2, 2) << endl;
    return 0;
}

Java

// Java implementation of the approach
class GfG
{
     
static int n = 3;
 
// Function to pre-compute the xor
static void preComputeXor(int arr[][],
                            int prefix_xor[][])
{
    // Left to right prefix xor
    // for each row
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            if (j == 0)
                prefix_xor[i][j] = arr[i][j];
            else
                prefix_xor[i][j] =
                    (prefix_xor[i][j - 1] ^ arr[i][j]);
        }
 
    // Top to bottom prefix xor
    // for each column
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            prefix_xor[j][i] =
                (prefix_xor[j - 1][i] ^ prefix_xor[j][i]);
}
 
// Function to process the queries
// x1, x2, y1, y2 represent the
// positions of the top-left
// and bottom right corners
static int ansQuerie(int prefix_xor[][], int x1,
                    int y1, int x2, int y2)
{
 
    // To store the xor values
    int xor_1 = 0, xor_2 = 0, xor_3 = 0;
 
    // Finding the values we need to xor
    // with value at (x2, y2) in prefix-xor
    // matrix
    if (x1 != 0)
        xor_1 = prefix_xor[x1 - 1][y2];
    if (y1 != 0)
        xor_2 = prefix_xor[x2][y1 - 1];
    if (x1 != 0 && y1 != 0)
        xor_3 = prefix_xor[x1 - 1][y1 - 1];
 
    // Return the required prefix xor
    return ((prefix_xor[x2][y2] ^ xor_1) ^ (xor_2 ^ xor_3));
}
 
// Driver code
public static void main(String[] args)
{
    int arr[][] = new int[][]{{ 1, 2, 3 },
                            { 4, 5, 6 },
                            { 7, 8, 9 }};
 
    // To store pre-computed xor
    int prefix_xor[][] = new int[n][n];
 
    // Pre-computing xor
    preComputeXor(arr, prefix_xor);
 
    // Queries
    System.out.println(ansQuerie(prefix_xor, 1, 1, 2, 2));
    System.out.println(ansQuerie(prefix_xor, 1, 2, 2, 2));
}
}
 
// This code is contributed by
// Prerna Saini.

Python3

n = 3
 
# Function to pre-compute the xor
def preComputeXor(arr, prefix_xor):
     
    # Left to right prefix xor
    # for each row
    for i in range(n):
        for j in range(n):
            if (j == 0):
                prefix_xor[i][j] = arr[i][j]
            else:
                prefix_xor[i][j] = (prefix_xor[i][j - 1] ^
                                               arr[i][j])
 
    # Top to bottom prefix xor
    # for each column
    for i in range(n):
        for j in range(1, n):
            prefix_xor[j][i] = (prefix_xor[j - 1][i] ^
                                    prefix_xor[j][i])
 
# Function to process the queries
# x1, x2, y1, y2 represent the
# positions of the top-left
# and bottom right corners
def ansQuerie(prefix_xor, x1, y1, x2, y2):
 
    # To store the xor values
    xor_1, xor_2, xor_3 = 0, 0, 0
 
    # Finding the values we need to xor
    # with value at (x2, y2) in prefix-xor
    # matrix
    if (x1 != 0):
        xor_1 = prefix_xor[x1 - 1][y2]
    if (y1 != 0):
        xor_2 = prefix_xor[x2][y1 - 1]
    if (x1 != 0 and y1 != 0):
        xor_3 = prefix_xor[x1 - 1][y1 - 1]
 
    # Return the required prefix xor
    return ((prefix_xor[x2][y2] ^ xor_1) ^
                         (xor_2 ^ xor_3))
 
 
# Driver code
arr = [[ 1, 2, 3 ],
       [ 4, 5, 6 ],
       [ 7, 8, 9 ]]
 
# To store pre-computed xor
prefix_xor = [[0 for i in range(n)]
                 for i in range(n)]
 
# Pre-computing xor
preComputeXor(arr, prefix_xor)
 
# Queries
print(ansQuerie(prefix_xor, 1, 1, 2, 2))
print(ansQuerie(prefix_xor, 1, 2, 2, 2))
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach
using System;
 
class GfG
{
    static int n = 3;
     
    // Function to pre-compute the xor
    static void preComputeXor(int [,]arr,
                                int [,]prefix_xor)
    {
        // Left to right prefix xor
        // for each row
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                if (j == 0)
                    prefix_xor[i, j] = arr[i, j];
                else
                    prefix_xor[i, j] =
                   (prefix_xor[i, j - 1] ^ arr[i, j]);
            }
     
        // Top to bottom prefix xor
        // for each column
        for (int i = 0; i < n; i++)
            for (int j = 1; j < n; j++)
                prefix_xor[j, i] =
                    (prefix_xor[j - 1, i] ^
                     prefix_xor[j, i]);
    }
     
    // Function to process the queries
    // x1, x2, y1, y2 represent the
    // positions of the top-left
    // and bottom right corners
    static int ansQuerie(int [,]prefix_xor, int x1,
                         int y1, int x2, int y2)
    {
     
        // To store the xor values
        int xor_1 = 0, xor_2 = 0, xor_3 = 0;
     
        // Finding the values we need to xor
        // with value at (x2, y2) in prefix-xor
        // matrix
        if (x1 != 0)
            xor_1 = prefix_xor[x1 - 1, y2];
        if (y1 != 0)
            xor_2 = prefix_xor[x2, y1 - 1];
        if (x1 != 0 && y1 != 0)
            xor_3 = prefix_xor[x1 - 1, y1 - 1];
     
        // Return the required prefix xor
        return ((prefix_xor[x2,y2] ^ xor_1) ^
                            (xor_2 ^ xor_3));
    }
     
    // Driver code
    public static void Main()
    {
        int [,]arr = {{ 1, 2, 3 },
                      { 4, 5, 6 },
                      { 7, 8, 9 }};
     
        // To store pre-computed xor
        int [,]prefix_xor = new int[n, n];
     
        // Pre-computing xor
        preComputeXor(arr, prefix_xor);
     
        // Queries
        Console.WriteLine(ansQuerie(prefix_xor, 1, 1, 2, 2));
        Console.WriteLine(ansQuerie(prefix_xor, 1, 2, 2, 2));
    }
}
 
// This code is contributed by Ryuga

PHP

<?php
// PHP implementation of the approach
 
$n = 3;
 
// Function to pre-compute the xor
function preComputeXor($arr, &$prefix_xor)
{
    global $n;
     
    // Left to right prefix xor
    // for each row
    for ($i = 0; $i < $n; $i++)
        for ($j = 0; $j < $n; $j++)
        {
            if ($j == 0)
                $prefix_xor[$i][$j] = $arr[$i][$j];
            else
                $prefix_xor[$i][$j] = ($prefix_xor[$i][$j - 1] ^
                                              $arr[$i][$j]);
        }
 
    // Top to bottom prefix xor
    // for each column
    for ($i = 0; $i < $n; $i++)
        for ($j = 1; $j < $n; $j++)
            $prefix_xor[$j][$i] = ($prefix_xor[$j - 1][$i] ^
                                   $prefix_xor[$j][$i]);
}
 
// Function to process the queries
// x1, x2, y1, y2 represent the
// positions of the top-left
// and bottom right corners
function ansQuerie($prefix_xor, $x1,
                   $y1, $x2, $y2)
{
 
    // To store the xor values
    $xor_1 = $xor_2 = $xor_3 = 0;
 
    // Finding the values we need to xor
    // with value at (x2, y2) in prefix-xor
    // matrix
    if ($x1 != 0)
        $xor_1 = $prefix_xor[$x1 - 1][$y2];
    if ($y1 != 0)
        $xor_2 = $prefix_xor[$x2][$y1 - 1];
    if ($x1 != 0 and $y1 != 0)
        $xor_3 = $prefix_xor[$x1 - 1][$y1 - 1];
 
    // Return the required prefix xor
    return (($prefix_xor[$x2][$y2] ^ $xor_1) ^
                           ($xor_2 ^ $xor_3));
}
 
// Driver code
$arr = array(array( 1, 2, 3 ),
             array( 4, 5, 6 ),
             array( 7, 8, 9 ));
 
// To store pre-computed xor
$prefix_xor = array_fill(0, $n,
              array_fill(0, $n, 0));
 
// Pre-computing xor
preComputeXor($arr, $prefix_xor);
 
// Queries
echo ansQuerie($prefix_xor, 1, 1, 2, 2) . "\n";
echo ansQuerie($prefix_xor, 1, 2, 2, 2);
 
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript implementation of the approach
var n = 3;
 
    // Function to pre-compute the xor
    function preComputeXor(arr , prefix_xor)
    {
        // Left to right prefix xor
        // for each row
        for (i = 0; i < n; i++)
            for (j = 0; j < n; j++) {
                if (j == 0)
                    prefix_xor[i][j] = arr[i][j];
                else
                    prefix_xor[i][j] =
                    (prefix_xor[i][j - 1] ^ arr[i][j]);
            }
 
        // Top to bottom prefix xor
        // for each column
        for (i = 0; i < n; i++)
            for (j = 1; j < n; j++)
                prefix_xor[j][i] =
                (prefix_xor[j - 1][i] ^ prefix_xor[j][i]);
    }
 
    // Function to process the queries
    // x1, x2, y1, y2 represent the
    // positions of the top-left
    // and bottom right corners
    function ansQuerie(prefix_xor , x1 , y1 , x2 , y2) {
 
        // To store the xor values
        var xor_1 = 0, xor_2 = 0, xor_3 = 0;
 
        // Finding the values we need to xor
        // with value at (x2, y2) in prefix-xor
        // matrix
        if (x1 != 0)
            xor_1 = prefix_xor[x1 - 1][y2];
        if (y1 != 0)
            xor_2 = prefix_xor[x2][y1 - 1];
        if (x1 != 0 && y1 != 0)
            xor_3 = prefix_xor[x1 - 1][y1 - 1];
 
        // Return the required prefix xor
        return ((prefix_xor[x2][y2] ^ xor_1) ^
                               (xor_2 ^ xor_3));
    }
 
    // Driver code
     
        var arr = [[ 1, 2, 3 ], [ 4, 5, 6 ],
                                [ 7, 8, 9 ] ];
 
        // To store pre-computed xor
        var prefix_xor = Array(n);
        for(var i = 0;i<n;i++)
        prefix_xor[i] = Array(n).fill(0);
 
        // Pre-computing xor
        preComputeXor(arr, prefix_xor);
 
        // Queries
        document.write(ansQuerie(prefix_xor, 1, 1, 2, 2)+
        "<br/>");
        document.write(ansQuerie(prefix_xor, 1, 2, 2, 2));
 
// This code contributed by umadevi9616
 
</script>

Producción:

2
15

Complejidad temporal: O(n ² )

Espacio Auxiliar: O(n ² )

Publicación traducida automáticamente

Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta