XOR de elementos en un rango dado con actualizaciones usando Fenwick Tree

Dada una array A[] de enteros y una array Q que consta de consultas de los siguientes dos tipos:

  • (1, L, R) : Devuelve XOR de todos los elementos presentes entre los índices L y R .
  • (2, I, val) : actualice A[I] a A[I] XOR val .

La tarea es resolver cada consulta e imprimir el XOR para cada Consulta de 1er tipo, utilizando Fenwick Tree .
Ejemplos:

Entrada: A[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9} 
Q = {{ 1, 3, 8}, {2, 4, 6}, {1, 3, 8}} 
Salida: 
XOR de elementos en el rango de 3 a 8 es 5 
XOR de elementos en el rango de 3 a 8 es 3 
Explicación: 
XOR de subarreglo { 3, 2, 3, 4, 5, 6 } es 5 Después de 
la segunda consulta, arr[4] se reemplaza por 4. 
Xor del subarreglo { 3, 4, 3, 4, 5, 6 } es 3.
Entrada: A[] = {2, 1, 1, 3, 2, 3 , 4, 5, 6, 7, 8, 9} 
Q = {{1, 0, 9}, {2, 3, 6}, {2, 5, 5}, {2, 8, 1}, {1 , 0, 9}} 
Salida: 
XOR de elementos en el rango de 0 a 9 es 0 
XOR de elementos en el rango de 0 a 9 es 2

Acercarse:

  • Para la consulta de tipo 1, devuelve el Xor de los elementos en el rango [1, R] y el rango [1, L-1] usando getXor().
  • En getXor(), para i a partir del índice de todos sus ancestros hasta 1, siga calculando XOR con BITree[i] . Para obtener el ancestro del i-ésimo índice en la vista getXor() , solo necesitamos restar el LSB (bit menos significativo) de i por i = i – i&(-i) . Finalmente devuelva el valor XOR final.
  • Para consultas de tipo 2, actualice A[index] a A[index] ^ val . Actualice todos los rangos que incluyen este elemento en BITree[] llamando a updateBIT() .
  • En updateBIT(), para cada i a partir del índice de todos sus ancestros hasta N , actualice BITree[i] como BITree[i] ^ val . Para obtener el ancestro del i-ésimo índice en la vista updateBit() , solo necesitamos agregar LSB (bit menos significativo) de i by i = i + i&(-i) .

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

C++

// C++ Program to find XOR of
// elements in given range [L, R].
 
#include <bits/stdc++.h>
using namespace std;
 
// Returns XOR of arr[0..index].
// This function assumes that the
// array is preprocessed and partial
// XORs of array elements are stored
// in BITree[].
int getXOR(int BITree[], int index)
{
    int ans = 0;
    index += 1;
 
    // Traverse ancestors
    // of BITree[index]
    while (index > 0) {
 
        // XOR current element
        // of BIT to ans
        ans ^= BITree[index];
 
        // Update index to that
        // of the parent node in
        // getXor() view by
        // subtracting LSB(Least
        // Significant Bit)
        index -= index & (-index);
    }
    return ans;
}
 
// Updates the Binary Index Tree by
// replacing all ancestors of index
// by their respective XOR with val
void updateBIT(int BITree[], int n,
               int index, int val)
{
    index = index + 1;
 
    // Traverse all ancestors
    // and XOR with 'val'.
    while (index <= n) {
 
        // XOR 'val' to current
        // node of BIT
        BITree[index] ^= val;
 
        // Update index to that
        // of the parent node in
        // updateBit() view by
        // adding LSB(Least
        // Significant Bit)
        index += index & (-index);
    }
}
 
// Constructs and returns a Binary
// Indexed Tree for the given array
int* constructBITree(int arr[], int n)
{
    // Create and initialize
    // the Binary Indexed Tree
    int* BITree = new int[n + 1];
    for (int i = 1; i <= n; i++)
        BITree[i] = 0;
 
    // Store the actual values in
    // BITree[] using update()
    for (int i = 0; i < n; i++)
        updateBIT(BITree, n, i, arr[i]);
 
    return BITree;
}
 
int rangeXor(int BITree[], int l, int r)
{
    return getXOR(BITree, r)
           ^ getXOR(BITree, l - 1);
}
 
// Driver Code
int main()
{
    int A[] = { 2, 1, 1, 3, 2, 3,
                4, 5, 6, 7, 8, 9 };
    int n = sizeof(A) / sizeof(A[0]);
 
    vector<vector<int> > q
        = { { 1, 0, 9 },
            { 2, 3, 6 },
            { 2, 5, 5 },
            { 2, 8, 1 },
            { 1, 0, 9 } };
 
    // Create the Binary Indexed Tree
    int* BITree = constructBITree(A, n);
 
    // Solve each query in Q
    for (int i = 0; i < q.size(); i++) {
        int id = q[i][0];
 
        if (id == 1) {
            int L = q[i][1];
            int R = q[i][2];
            cout << "XOR of elements "
                 << "in given range is "
                 << rangeXor(BITree, L, R)
                 << "\n";
        }
        else {
            int idx = q[i][1];
            int val = q[i][2];
            A[idx] ^= val;
 
            // Update the values of all
            // ancestors of idx
            updateBIT(BITree, n, idx, val);
        }
    }
 
    return 0;
}

Java

// Java Program to find XOR of
// elements in given range [L, R].
import java.util.*;
 
class GFG{
 
// Returns XOR of arr[0..index].
// This function assumes that the
// array is preprocessed and partial
// XORs of array elements are stored
// in BITree[].
static int getXOR(int BITree[], int index)
{
    int ans = 0;
    index += 1;
 
    // Traverse ancestors
    // of BITree[index]
    while (index > 0)
    {
 
        // XOR current element
        // of BIT to ans
        ans ^= BITree[index];
 
        // Update index to that
        // of the parent node in
        // getXor() view by
        // subtracting LSB(Least
        // Significant Bit)
        index -= index & (-index);
    }
    return ans;
}
 
// Updates the Binary Index Tree by
// replacing all ancestors of index
// by their respective XOR with val
static void updateBIT(int BITree[], int n,
                      int index, int val)
{
    index = index + 1;
 
    // Traverse all ancestors
    // and XOR with 'val'.
    while (index <= n)
    {
 
        // XOR 'val' to current
        // node of BIT
        BITree[index] ^= val;
 
        // Update index to that
        // of the parent node in
        // updateBit() view by
        // adding LSB(Least
        // Significant Bit)
        index += index & (-index);
    }
}
 
// Constructs and returns a Binary
// Indexed Tree for the given array
static int[] constructBITree(int arr[], int n)
{
    // Create and initialize
    // the Binary Indexed Tree
    int []BITree = new int[n + 1];
    for (int i = 1; i <= n; i++)
        BITree[i] = 0;
 
    // Store the actual values in
    // BITree[] using update()
    for (int i = 0; i < n; i++)
        updateBIT(BITree, n, i, arr[i]);
 
    return BITree;
}
 
static int rangeXor(int BITree[], int l, int r)
{
    return getXOR(BITree, r) ^
           getXOR(BITree, l - 1);
}
 
// Driver Code
public static void main(String[] args)
{
    int A[] = { 2, 1, 1, 3, 2, 3,
                4, 5, 6, 7, 8, 9 };
    int n = A.length;
 
    int [][]q = { { 1, 0, 9 },
                  { 2, 3, 6 },
                  { 2, 5, 5 },
                  { 2, 8, 1 },
                  { 1, 0, 9 } };
 
    // Create the Binary Indexed Tree
    int []BITree = constructBITree(A, n);
 
    // Solve each query in Q
    for (int i = 0; i < q.length; i++)
    {
        int id = q[i][0];
 
        if (id == 1)
        {
            int L = q[i][1];
            int R = q[i][2];
            System.out.print("XOR of elements " +
                           "in given range is " +
                         rangeXor(BITree, L, R) + "\n");
        }
        else
        {
            int idx = q[i][1];
            int val = q[i][2];
            A[idx] ^= val;
 
            // Update the values of all
            // ancestors of idx
            updateBIT(BITree, n, idx, val);
        }
    }
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program to find XOR of
# elements in given range [L, R].
 
# Returns XOR of arr[0..index].
# This function assumes that the
# array is preprocessed and partial
# XORs of array elements are stored
# in BITree[].
def getXOR(BITree, index):
 
    ans = 0
    index += 1
 
    # Traverse ancestors
    # of BITree[index]
    while (index > 0):
     
        # XOR current element
        # of BIT to ans
        ans ^= BITree[index]
 
        # Update index to that
        # of the parent node in
        # getXor() view by
        # subtracting LSB(Least
        # Significant Bit)
        index -= index & (-index)
     
    return ans
 
# Updates the Binary Index Tree by
# replacing all ancestors of index
# by their respective XOR with val
def updateBIT(BITree, n, index, val):
 
    index = index + 1
 
    # Traverse all ancestors
    # and XOR with 'val'.
    while (index <= n):
     
        # XOR 'val' to current
        # node of BIT
        BITree[index] ^= val
 
        # Update index to that
        # of the parent node in
        # updateBit() view by
        # adding LSB(Least
        # Significant Bit)
        index += index & (-index)
     
# Constructs and returns a Binary
# Indexed Tree for the given array
def constructBITree(arr, n):
 
    # Create and initialize
    # the Binary Indexed Tree
    BITree = [0] * (n + 1)
     
    # Store the actual values in
    # BITree[] using update()
    for i in range(n):
        updateBIT(BITree, n, i, arr[i])
 
    return BITree
 
def rangeXor(BITree, l, r):
 
    return (getXOR(BITree, r) ^
            getXOR(BITree, l - 1))
            
# Driver Code
if __name__ == "__main__":
     
    A = [ 2, 1, 1, 3, 2, 3,
          4, 5, 6, 7, 8, 9 ]
    n = len(A)
 
    q = [ [ 1, 0, 9 ], [ 2, 3, 6 ],
          [ 2, 5, 5 ], [ 2, 8, 1 ],
          [ 1, 0, 9 ] ]
 
    # Create the Binary Indexed Tree
    BITree = constructBITree(A, n)
 
    # Solve each query in Q
    for i in range(len(q)):
        id = q[i][0]
 
        if (id == 1):
            L = q[i][1]
            R = q[i][2]
            print("XOR of elements in "
                  "given range is ",
                  rangeXor(BITree, L, R))
        else:
            idx = q[i][1]
            val = q[i][2]
            A[idx] ^= val
 
            # Update the values of all
            # ancestors of idx
            updateBIT(BITree, n, idx, val)
 
# This code is contributed by jana_sayantan

C#

// C# program to find XOR of
// elements in given range [L, R].
using System;
 
class GFG{
 
// Returns XOR of arr[0..index].
// This function assumes that the
// array is preprocessed and partial
// XORs of array elements are stored
// in BITree[].
static int getXOR(int []BITree, int index)
{
    int ans = 0;
    index += 1;
 
    // Traverse ancestors
    // of BITree[index]
    while (index > 0)
    {
 
        // XOR current element
        // of BIT to ans
        ans ^= BITree[index];
 
        // Update index to that
        // of the parent node in
        // getXor() view by
        // subtracting LSB(Least
        // Significant Bit)
        index -= index & (-index);
    }
    return ans;
}
 
// Updates the Binary Index Tree by
// replacing all ancestors of index
// by their respective XOR with val
static void updateBIT(int []BITree, int n,
                      int index, int val)
{
    index = index + 1;
 
    // Traverse all ancestors
    // and XOR with 'val'.
    while (index <= n)
    {
 
        // XOR 'val' to current
        // node of BIT
        BITree[index] ^= val;
 
        // Update index to that
        // of the parent node in
        // updateBit() view by
        // adding LSB(Least
        // Significant Bit)
        index += index & (-index);
    }
}
 
// Constructs and returns a Binary
// Indexed Tree for the given array
static int[] constructBITree(int []arr,
                             int n)
{
     
    // Create and initialize
    // the Binary Indexed Tree
    int []BITree = new int[n + 1];
    for(int i = 1; i <= n; i++)
       BITree[i] = 0;
 
    // Store the actual values in
    // BITree[] using update()
    for(int i = 0; i < n; i++)
       updateBIT(BITree, n, i, arr[i]);
 
    return BITree;
}
 
static int rangeXor(int []BITree, int l,
                                  int r)
{
    return getXOR(BITree, r) ^
           getXOR(BITree, l - 1);
}
 
// Driver Code
public static void Main(String[] args)
{
    int []A = { 2, 1, 1, 3, 2, 3,
                4, 5, 6, 7, 8, 9 };
    int n = A.Length;
     
    int [,]q = { { 1, 0, 9 },
                 { 2, 3, 6 },
                 { 2, 5, 5 },
                 { 2, 8, 1 },
                 { 1, 0, 9 } };
 
    // Create the Binary Indexed Tree
    int []BITree = constructBITree(A, n);
 
    // Solve each query in Q
    for(int i = 0; i < q.GetLength(0); i++)
    {
       int id = q[i, 0];
        
       if (id == 1)
       {
           int L = q[i, 1];
           int R = q[i, 2];
           Console.Write("XOR of elements " +
                       "in given range is " +
                     rangeXor(BITree, L, R) + "\n");
       }
       else
       {
           int idx = q[i, 1];
           int val = q[i, 2];
           A[idx] ^= val;
            
           // Update the values of
           // all ancestors of idx
           updateBIT(BITree, n, idx, val);
       }
    }
}
}
 
// This code is contributed by sapnasingh4991

Javascript

<script>
 
// Javascript Program to find XOR of
// elements in given range [L, R].
 
// Returns XOR of arr[0..index].
// This function assumes that the
// array is preprocessed and partial
// XORs of array elements are stored
// in BITree[].
function getXOR(BITree, index)
{
    let ans = 0;
    index += 1;
 
    // Traverse ancestors
    // of BITree[index]
    while (index > 0) {
 
        // XOR current element
        // of BIT to ans
        ans ^= BITree[index];
 
        // Update index to that
        // of the parent node in
        // getXor() view by
        // subtracting LSB(Least
        // Significant Bit)
        index -= index & (-index);
    }
    return ans;
}
 
// Updates the Binary Index Tree by
// replacing all ancestors of index
// by their respective XOR with val
function updateBIT(BITree, n, index, val)
{
    index = index + 1;
 
    // Traverse all ancestors
    // and XOR with 'val'.
    while (index <= n) {
 
        // XOR 'val' to current
        // node of BIT
        BITree[index] ^= val;
 
        // Update index to that
        // of the parent node in
        // updateBit() view by
        // adding LSB(Least
        // Significant Bit)
        index += index & (-index);
    }
}
 
// Constructs and returns a Binary
// Indexed Tree for the given array
function constructBITree(arr, n)
{
    // Create and initialize
    // the Binary Indexed Tree
    let BITree = new Array(n + 1);
    for (let i = 1; i <= n; i++)
        BITree[i] = 0;
 
    // Store the actual values in
    // BITree[] using update()
    for (let i = 0; i < n; i++)
        updateBIT(BITree, n, i, arr[i]);
 
    return BITree;
}
 
function rangeXor(BITree, l, r)
{
    return getXOR(BITree, r)
           ^ getXOR(BITree, l - 1);
}
 
// Driver Code
    let A = [ 2, 1, 1, 3, 2, 3,
                4, 5, 6, 7, 8, 9 ];
    let n = A.length;
 
    let q
        = [ [ 1, 0, 9 ],
            [ 2, 3, 6 ],
            [ 2, 5, 5 ],
            [ 2, 8, 1 ],
            [ 1, 0, 9 ] ];
 
    // Create the Binary Indexed Tree
    let BITree = constructBITree(A, n);
 
    // Solve each query in Q
    for (let i = 0; i < q.length; i++) {
        let id = q[i][0];
 
        if (id == 1) {
            let L = q[i][1];
            let R = q[i][2];
            document.write("XOR of elements "
                 + "in given range is "
                 + rangeXor(BITree, L, R)
                 + "<br>");
        }
        else {
            let idx = q[i][1];
            let val = q[i][2];
            A[idx] ^= val;
 
            // Update the values of all
            // ancestors of idx
            updateBIT(BITree, n, idx, val);
        }
    }
 
</script>
Producción: 

XOR of elements in given range is 0
XOR of elements in given range is 2

Complejidad temporal de getXor(): O(log N)  
Complejidad temporal de updateBIT(): O(log N)  
Complejidad temporal general: O(M * log N) donde M y N son el número de consultas y el tamaño de la array dada respectivamente.
 

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *