Tenemos una array arr[0 . . . n-1]. Hay dos tipos de consultas
- Encuentre el XOR de elementos del índice l a r donde 0 <= l <= r <= n-1
- Cambia el valor de un elemento específico de la array a un nuevo valor x. Necesitamos hacer arr[i] = x donde 0 <= i <= n-1.
Habrá un total de q consultas.
Restricción de entrada
n <= 10^5, q <= 10^5
Solución 1: una solución simple es ejecutar un ciclo de l a r y calcular xor de elementos en un rango dado. Para actualizar un valor, simplemente haga arr[i] = x. La primera operación toma el tiempo O(n) y la segunda operación toma el tiempo O(1). En el peor de los casos, la complejidad del tiempo es O (n * q) para q consultas
, lo que llevará mucho tiempo para n ~ 10 ^ 5 y q ~ 10 ^ 5. Por lo tanto, esta solución excederá el límite de tiempo.
Solución 2: Otra solución es almacenar xor en todos los rangos posibles, pero hay O (n ^ 2) rangos posibles, por lo tanto, con n ~ 10 ^ 5 excederá la complejidad del espacio, por lo tanto, sin considerar la complejidad del tiempo, podemos afirmar que esta solución no lo hará trabajar.
Solución 3 (árbol de segmentos):
Requisito previo : Árbol de segmentos
Construimos un árbol de segmentos de una array dada de modo que los elementos de la array estén en las hojas y los Nodes internos almacenen XOR de las hojas cubiertas por ellos.
Implementación:
C++
// C++ program to show segment tree operations like construction,
// query and update
#include <iostream>
#include <math.h>
using namespace std;
// A utility function to get the middle index from corner indexes.
int getMid(int s, int e) { return s + (e -s)/2; }
/* A recursive function to get the xor of values in given range
of the array. The following are parameters for this function.
st --> Pointer to segment tree
si --> Index of current node in the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending indexes of the segment
represented by current node, i.e., st[si]
qs & qe --> Starting and ending indexes of query range */
int getXorUtil(int *st, int ss, int se, int qs, int qe, int si)
{
// If segment of this node is a part of given range, then return
// the xor of the segment
if (qs <= ss && qe >= se)
return st[si];
// If segment of this node is outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment overlaps with the given range
int mid = getMid(ss, se);
return getXorUtil(st, ss, mid, qs, qe, 2*si+1) ^
getXorUtil(st, mid+1, se, qs, qe, 2*si+2);
}
/* A recursive function to update the nodes which have the given
index in their range. The following are parameters
st, si, ss and se are same as getXorUtil()
i --> index of the element to be updated. This index is
in input array.
diff --> Value to be added to all nodes which have i in range */
void updateValueUtil(int *st, int ss, int se, int i, int diff, int si)
{
// Base Case: If the input index lies outside the range of
// this segment
if (i < ss || i > se)
return;
// If the input index is in range of this node, then update
// the value of the node and its children
st[si] = st[si] + diff;
if (se != ss)
{
int mid = getMid(ss, se);
updateValueUtil(st, ss, mid, i, diff, 2*si + 1);
updateValueUtil(st, mid+1, se, i, diff, 2*si + 2);
}
}
// The function to update a value in input array and segment tree.
// It uses updateValueUtil() to update the value in segment tree
void updateValue(int arr[], int *st, int n, int i, int new_val)
{
// Check for erroneous input index
if (i < 0 || i > n-1)
{
cout <<"Invalid Input";
return;
}
// Get the difference between new value and old value
int diff = new_val - arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of nodes in segment tree
updateValueUtil(st, 0, n-1, i, diff, 0);
}
// Return xor of elements in range from index qs (query start)
// to qe (query end). It mainly uses getXorUtil()
int getXor(int *st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n-1 || qs > qe)
{
cout <<"Invalid Input";
return -1;
}
return getXorUtil(st, 0, n-1, qs, qe, 0);
}
// A recursive function that constructs Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTUtil(int arr[], int ss, int se, int *st, int si)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements, then recur for left and
// right subtrees and store the xor of values in this node
int mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, st, si*2+1) ^
constructSTUtil(arr, mid+1, se, st, si*2+2);
return st[si];
}
/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
int *constructST(int arr[], int n)
{
// Allocate memory for segment tree
//Height of segment tree
int x = (int)(ceil(log2(n)));
//Maximum size of segment tree
int max_size = 2*(int)pow(2, x) - 1;
// Allocate memory
int *st = (int *)malloc(sizeof(int)*max_size);
// Fill the allocated memory st
constructSTUtil(arr, 0, n-1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver program to test above functions
int main()
{
int arr[] = {1, 3, 5, 7, 9, 11};
int n = sizeof(arr)/sizeof(arr[0]);
// Build segment tree from given array
int *st = constructST(arr, n);
// Print xor of values in array from index 1 to 3
cout <<"Xor of values in given range = "<< getXor(st, n, 1, 3) << endl;
// Update: set arr[1] = 10 and update corresponding
// segment tree nodes
updateValue(arr, st, n, 1, 10);
// Find xor after the value is updated
cout <<"Updated xor of values in given range = " << getXor(st, n, 1, 3) << endl;
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C program to show segment tree operations like construction,
// query and update
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
// A utility function to get the middle index from corner indexes.
int getMid(int s, int e) { return s + (e -s)/2; }
/* A recursive function to get the xor of values in given range
of the array. The following are parameters for this function.
st --> Pointer to segment tree
si --> Index of current node in the segment tree. Initially
0 is passed as root is always at index 0
ss & se --> Starting and ending indexes of the segment
represented by current node, i.e., st[si]
qs & qe --> Starting and ending indexes of query range */
int getXorUtil(int *st, int ss, int se, int qs, int qe, int si)
{
// If segment of this node is a part of given range, then return
// the xor of the segment
if (qs <= ss && qe >= se)
return st[si];
// If segment of this node is outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment overlaps with the given range
int mid = getMid(ss, se);
return getXorUtil(st, ss, mid, qs, qe, 2*si+1) ^
getXorUtil(st, mid+1, se, qs, qe, 2*si+2);
}
/* A recursive function to update the nodes which have the given
index in their range. The following are parameters
st, si, ss and se are same as getXorUtil()
i --> index of the element to be updated. This index is
in input array.
diff --> Value to be added to all nodes which have i in range */
void updateValueUtil(int *st, int ss, int se, int i, int diff, int si)
{
// Base Case: If the input index lies outside the range of
// this segment
if (i < ss || i > se)
return;
// If the input index is in range of this node, then update
// the value of the node and its children
st[si] = st[si] + diff;
if (se != ss)
{
int mid = getMid(ss, se);
updateValueUtil(st, ss, mid, i, diff, 2*si + 1);
updateValueUtil(st, mid+1, se, i, diff, 2*si + 2);
}
}
// The function to update a value in input array and segment tree.
// It uses updateValueUtil() to update the value in segment tree
void updateValue(int arr[], int *st, int n, int i, int new_val)
{
// Check for erroneous input index
if (i < 0 || i > n-1)
{
printf("Invalid Input");
return;
}
// Get the difference between new value and old value
int diff = new_val - arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of nodes in segment tree
updateValueUtil(st, 0, n-1, i, diff, 0);
}
// Return xor of elements in range from index qs (query start)
// to qe (query end). It mainly uses getXorUtil()
int getXor(int *st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n-1 || qs > qe)
{
printf("Invalid Input");
return -1;
}
return getXorUtil(st, 0, n-1, qs, qe, 0);
}
// A recursive function that constructs Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTUtil(int arr[], int ss, int se, int *st, int si)
{
// If there is one element in array, store it in current node of
// segment tree and return
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements, then recur for left and
// right subtrees and store the xor of values in this node
int mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, st, si*2+1) ^
constructSTUtil(arr, mid+1, se, st, si*2+2);
return st[si];
}
/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
int *constructST(int arr[], int n)
{
// Allocate memory for segment tree
//Height of segment tree
int x = (int)(ceil(log2(n)));
//Maximum size of segment tree
int max_size = 2*(int)pow(2, x) - 1;
// Allocate memory
int *st = (int *)malloc(sizeof(int)*max_size);
// Fill the allocated memory st
constructSTUtil(arr, 0, n-1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver program to test above functions
int main()
{
int arr[] = {1, 3, 5, 7, 9, 11};
int n = sizeof(arr)/sizeof(arr[0]);
// Build segment tree from given array
int *st = constructST(arr, n);
// Print xor of values in array from index 1 to 3
printf("Xor of values in given range = %d\n",
getXor(st, n, 1, 3));
// Update: set arr[1] = 10 and update corresponding
// segment tree nodes
updateValue(arr, st, n, 1, 10);
// Find xor after the value is updated
printf("Updated xor of values in given range = %d\n",
getXor(st, n, 1, 3));
return 0;
}
Java
// Java program to show segment tree operations
// like construction, query and update
class GFG{
// A utility function to get the middle
// index from corner indexes.
static int getMid(int s, int e)
{
return s + (e - s) / 2;
}
/*
* A recursive function to get the xor of values
* in given range of the array.
* The following are parameters for this function.
*
* st --> Pointer to segment tree
* si --> Index of current node in the segment tree. Initially
* 0 is passed as root is always at index 0
* ss & se --> Starting and ending indexes of the segment
* represented by current node, i.e., st[si]
* qs & qe --> Starting and ending indexes of query range
*/
static int getXorUtil(int[] st, int ss, int se,
int qs, int qe, int si)
{
// If segment of this node is a part of
// given range, then return the xor of
// the segment
if (qs <= ss && qe >= se)
return st[si];
// If segment of this node is
// outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment overlaps
// with the given range
int mid = getMid(ss, se);
return getXorUtil(st, ss, mid, qs,
qe, 2 * si + 1) ^
getXorUtil(st, mid + 1, se, qs,
qe, 2 * si + 2);
}
/*
* A recursive function to update the nodes which have the given
* index in their range. The following are parameters
* st, si, ss and se are same as getXorUtil()
* i --> index of the element to be updated. This index is in
* input array.
* diff --> Value to be added to all nodes which have i in range
*/
static void updateValueUtil(int[] st, int ss, int se,
int i, int diff, int si)
{
// Base Case: If the input index lies outside the
// range of this segment
if (i < ss || i > se)
return;
// If the input index is in range of this node,
// then update the value of the node and its children
st[si] = st[si] + diff;
if (se != ss)
{
int mid = getMid(ss, se);
updateValueUtil(st, ss, mid, i, diff,
2 * si + 1);
updateValueUtil(st, mid + 1, se, i, diff,
2 * si + 2);
}
}
// The function to update a value in input array
// and segment tree. It uses updateValueUtil()
// to update the value in segment tree
static void updateValue(int[] arr, int[] st, int n,
int i, int new_val)
{
// Check for erroneous input index
if (i < 0 || i > n - 1)
{
System.out.println("Invalid Input");
return;
}
// Get the difference between new
// value and old value
int diff = new_val - arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of nodes in segment tree
updateValueUtil(st, 0, n - 1, i, diff, 0);
}
// Return xor of elements in range from
// index qs (query start) to qe (query end).
// It mainly uses getXorUtil()
static int getXor(int[] st, int n, int qs, int qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe)
{
System.out.println("Invalid Input");
return -1;
}
return getXorUtil(st, 0, n - 1, qs, qe, 0);
}
// A recursive function that constructs Segment
// Tree for array[ss..se]. si is index of current
// node in segment tree st
static int constructSTUtil(int arr[], int ss,
int se, int[] st, int si)
{
// If there is one element in array, store
// it in current node of segment tree and return
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements,
// then recur for left and right subtrees
// and store the xor of values in this node
int mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, st,
si * 2 + 1) ^
constructSTUtil(arr, mid + 1, se, st,
si * 2 + 2);
return st[si];
}
/*
* Function to construct segment tree from
* given array. This function allocates memory
* for segment tree and calls constructSTUtil()
* to fill the allocated memory
*/
static int[] constructST(int arr[], int n)
{
// Allocate memory for segment tree
// Height of segment tree
int x = (int)(Math.ceil(Math.log(n) /
Math.log(2)));
// Maximum size of segment tree
int max_size = 2 * (int) Math.pow(2, x) - 1;
// Allocate memory
int[] st = new int[max_size];
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 3, 5, 7, 9, 11 };
int n = arr.length;
// Build segment tree from given array
int[] st = constructST(arr, n);
// Print xor of values in array from index 1 to 3
System.out.printf("Xor of values in given " +
"range = %d\n",
getXor(st, n, 1, 3));
// Update: set arr[1] = 10 and update
// corresponding segment tree nodes
updateValue(arr, st, n, 1, 10);
// Find xor after the value is updated
System.out.printf("Updated xor of values in " +
"given range = %d\n",
getXor(st, n, 1, 3));
}
}
// This code is contributed by sanjeev2552
Python3
# Python program to show segment tree operations
# like construction, query and update
import math as Math
# A utility function to get the middle
# index from corner indexes.
def getMid(s, e):
return s + ((e - s) // 2)
def getXorUtil(st, ss, se, qs, qe, si):
# If segment of this node is a part of
# given range, then return the xor of
# the segment
if (qs <= ss and qe >= se):
return st[si]
# If segment of this node is
# outside the given range
if (se < qs or ss > qe):
return 0
# If a part of this segment overlaps
# with the given range
mid = getMid(ss, se)
return getXorUtil(st, ss, mid, qs, qe, 2 * si + 1) ^ getXorUtil(st, mid + 1, se, qs, qe, 2 * si + 2)
def updateValueUtil(st, ss, se, i, diff, si):
# Base Case: If the input index lies outside the
# range of this segment
if (i < ss or i > se):
return
# If the input index is in range of this node,
# then update the value of the node and its children
st[si] = st[si] + diff
if (se != ss):
mid = getMid(ss, se)
updateValueUtil(st, ss, mid, i, diff,
2 * si + 1)
updateValueUtil(st, mid + 1, se, i, diff,
2 * si + 2)
# The function to update a value in input array
# and segment tree. It uses updateValueUtil()
# to update the value in segment tree
def updateValue(arr, st, n, i, new_val):
# Check for erroneous input index
if (i < 0 or i > n - 1):
print("Invalid Input")
return
# Get the difference between new
# value and old value
diff = new_val - arr[i]
# Update the value in array
arr[i] = new_val
# Update the values of nodes in segment tree
updateValueUtil(st, 0, n - 1, i, diff, 0)
# Return xor of elements in range from
# index qs (query start) to qe (query end).
# It mainly uses getXorUtil()
def getXor(st, n, qs, qe):
# Check for erroneous input values
if (qs < 0 or qe > n - 1 or qs > qe):
print("Invalid Input")
return -1
return getXorUtil(st, 0, n - 1, qs, qe, 0)
# A recursive function that constructs Segment
# Tree for array[ss..se]. si is index of current
# node in segment tree st
def constructSTUtil(arr, ss, se, st, si):
# If there is one element in array, store
# it in current node of segment tree and return
if (ss == se):
st[si] = arr[ss]
return arr[ss]
# If there are more than one elements,
# then recur for left and right subtrees
# and store the xor of values in this node
mid = getMid(ss, se)
st[si] = constructSTUtil(arr, ss, mid, st, si * 2 +
1) ^ constructSTUtil(arr, mid + 1, se, st, si * 2 + 2)
return st[si]
"""
* Function to construct segment tree from
* given array. This function allocates memory
* for segment tree and calls constructSTUtil()
* to fill the allocated memory
"""
def constructST(arr, n):
# Allocate memory for segment tree
# Height of segment tree
x = (Math.ceil(Math.log(n) / Math.log(2)))
# Maximum size of segment tree
max_size = Math.floor(2 * (Math.pow(2, x)) - 1)
# Allocate memory
st = [0] * max_size
# Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0)
# Return the constructed segment tree
return st
arr = [1, 3, 5, 7, 9, 11]
n = len(arr)
# Build segment tree from given array
st = constructST(arr, n)
# Print xor of values in array from index 1 to 3
print(f"Xor of values in given range = {getXor(st, n, 1, 3)}")
# Update: set arr[1] = 10 and update
# corresponding segment tree nodes
updateValue(arr, st, n, 1, 10)
# Find xor after the value is updated
print(f"Updated xor of values in given range = {getXor(st, n, 1, 3)}")
# This code is contributed by Saurabh Jaiswal
Javascript
<script>
// Javascript program to show segment tree operations
// like construction, query and update
// A utility function to get the middle
// index from corner indexes.
function getMid(s, e)
{
return s + parseInt((e - s) / 2, 10);
}
function getXorUtil(st, ss, se, qs, qe, si)
{
// If segment of this node is a part of
// given range, then return the xor of
// the segment
if (qs <= ss && qe >= se)
return st[si];
// If segment of this node is
// outside the given range
if (se < qs || ss > qe)
return 0;
// If a part of this segment overlaps
// with the given range
let mid = getMid(ss, se);
return getXorUtil(st, ss, mid, qs,
qe, 2 * si + 1) ^
getXorUtil(st, mid + 1, se, qs,
qe, 2 * si + 2);
}
function updateValueUtil(st, ss, se, i, diff, si)
{
// Base Case: If the input index lies outside the
// range of this segment
if (i < ss || i > se)
return;
// If the input index is in range of this node,
// then update the value of the node and its children
st[si] = st[si] + diff;
if (se != ss)
{
let mid = getMid(ss, se);
updateValueUtil(st, ss, mid, i, diff,
2 * si + 1);
updateValueUtil(st, mid + 1, se, i, diff,
2 * si + 2);
}
}
// The function to update a value in input array
// and segment tree. It uses updateValueUtil()
// to update the value in segment tree
function updateValue(arr, st, n, i, new_val)
{
// Check for erroneous input index
if (i < 0 || i > n - 1)
{
document.write("Invalid Input");
return;
}
// Get the difference between new
// value and old value
let diff = new_val - arr[i];
// Update the value in array
arr[i] = new_val;
// Update the values of nodes in segment tree
updateValueUtil(st, 0, n - 1, i, diff, 0);
}
// Return xor of elements in range from
// index qs (query start) to qe (query end).
// It mainly uses getXorUtil()
function getXor(st, n, qs, qe)
{
// Check for erroneous input values
if (qs < 0 || qe > n - 1 || qs > qe)
{
document.write("Invalid Input");
return -1;
}
return getXorUtil(st, 0, n - 1, qs, qe, 0);
}
// A recursive function that constructs Segment
// Tree for array[ss..se]. si is index of current
// node in segment tree st
function constructSTUtil(arr, ss, se, st, si)
{
// If there is one element in array, store
// it in current node of segment tree and return
if (ss == se)
{
st[si] = arr[ss];
return arr[ss];
}
// If there are more than one elements,
// then recur for left and right subtrees
// and store the xor of values in this node
let mid = getMid(ss, se);
st[si] = constructSTUtil(arr, ss, mid, st,
si * 2 + 1) ^
constructSTUtil(arr, mid + 1, se, st,
si * 2 + 2);
return st[si];
}
/*
* Function to construct segment tree from
* given array. This function allocates memory
* for segment tree and calls constructSTUtil()
* to fill the allocated memory
*/
function constructST(arr, n)
{
// Allocate memory for segment tree
// Height of segment tree
let x = (Math.ceil(Math.log(n) / Math.log(2)));
// Maximum size of segment tree
let max_size = 2 * parseInt(Math.pow(2, x), 10) - 1;
// Allocate memory
let st = new Array(max_size);
st.fill(0);
// Fill the allocated memory st
constructSTUtil(arr, 0, n - 1, st, 0);
// Return the constructed segment tree
return st;
}
let arr = [ 1, 3, 5, 7, 9, 11 ];
let n = arr.length;
// Build segment tree from given array
let st = constructST(arr, n);
// Print xor of values in array from index 1 to 3
document.write("Xor of values in given " +
"range = " +
getXor(st, n, 1, 3) + "</br>");
// Update: set arr[1] = 10 and update
// corresponding segment tree nodes
updateValue(arr, st, n, 1, 10);
// Find xor after the value is updated
document.write("Updated xor of values in " +
"given range = " +
getXor(st, n, 1, 3) + "</br>");
// This code is contributed by divyeshrabadiya07.
</script>
Producción
Xor of values in given range = 1 Updated xor of values in given range = 8
Complejidad de tiempo y espacio:
La complejidad del tiempo para la construcción del árbol es O(n).
Hay un total de 2n-1 Nodes, y el valor de cada Node se calcula solo una vez en la construcción del árbol.
La complejidad del tiempo para consultar es O (log n).
La complejidad temporal de la actualización también es O(log n).
La complejidad del tiempo total es: O(n) para la construcción + O(log n) para cada consulta = O(n) + O(n * log n) = O(n * log n)
Complejidad de Tiempo: O(n * log n)
Espacio Auxiliar: O(n)
Este artículo es una contribución de Pratik Chhajer . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA