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.