Dado inicialmente un conjunto vacío y una serie de consultas sobre él, cada una posiblemente de los siguientes tipos:
- Insertar : inserta un nuevo elemento ‘x’.
- Eliminar : elimina un elemento existente ‘x’.
- Mediana : imprime el elemento mediano de los números actualmente en el conjunto
Ejemplo:
Input : Insert 1
Insert 4
Insert 7
Median
Output : The first three queries
should insert 1, 4 and 7
into an empty set. The
fourth query should return
4 (median of 1, 4, 7).
Para fines expositivos, asumimos lo siguiente, pero estas suposiciones no son las limitaciones del método discutido aquí:
1. En cualquier instancia, todos los elementos son distintos, es decir, ninguno de ellos ocurre más de una vez.
2. La consulta ‘Mediana’ se realiza solo cuando hay un número impar de elementos en el conjunto. (Tendremos que realizar dos consultas en nuestro árbol de segmentos, en el caso de números pares)
3. Los elementos en el conjunto van desde 1 a +10^6.
Método 1 (Ingenuo)
En la implementación ingenua, podemos hacer las dos primeras consultas en O(1), pero la última consulta en O(max_elem), donde max_elem es el elemento máximo de todos los tiempos (incluidos los elementos eliminados).
Supongamos una array count[] (de tamaño 10^6 + 1) para mantener el recuento de cada elemento en el subconjunto. Los siguientes son algoritmos simples y autoexplicativos para las 3 consultas:
Insertar x consulta:
count[x]++;
if (x > max_elem)
max_elem = x;
n++;
Eliminar x consulta:
if (count[x] > 0)
count[x]--;
n--;
Consulta mediana:
sum = 0;
i = 0;
while( sum <= n / 2 )
{
i++;
sum += count[i];
}
median = i;
return median;
Ilustración de la array count[], que representa el conjunto {1, 4, 7, 8, 9}, el elemento mediano es ‘7’:
La consulta ‘Mediana’ intenta encontrar el (n + 1)/2º ‘1’ en la array, en este caso, el 3er ‘1’; ahora hacemos lo mismo usando un árbol de segmentos.
Método 2 (usando el árbol de segmentos )
Hacemos un árbol de segmentos para almacenar la suma de los intervalos, donde un intervalo [a, b] representa el número de elementos presentes en el conjunto, actualmente, en el rango [a, b]. Por ejemplo, si consideramos el ejemplo anterior, la consulta (3, 7) devuelve 2, la consulta (4, 4) devuelve 1, la consulta (5, 5) devuelve 0.
Las consultas de inserción y eliminación son simples y ambas pueden implementarse mediante la actualización de funciones (int x, int diff) (agrega ‘diff’ en el índice ‘x’)
Algoritmo
// adds ‘diff’ at index ‘x’
update(node, a, b, x, diff)
// If leaf node
If a == b and a == x
segmentTree[node] += diff
// If non-leaf node and x lies in its range
If x is in [a, b]
// Update children recursively
update(2*node, a, (a + b)/2, x, diff)
update(2*node + 1, (a + b)/2 + 1, b, x, diff)
// Update node
segmentTree[node] = segmentTree[2 * node] +
segmentTree[2 * node + 1]
La función recursiva anterior se ejecuta en O (log (max_elem)) (en este caso, max_elem es 10 ^ 6) y se usa tanto para la inserción como para la eliminación con las siguientes llamadas:
- Insertar ‘x’ se hace usando update(1, 0, 10^6, x, 1). Tenga en cuenta que se pasa la raíz del árbol, el índice de inicio se pasa como 0 y el índice final como 10 ^ 6 para que todos los rangos que tienen x se actualicen.
- La eliminación de ‘x’ se realiza mediante la actualización (1, 0, 10^6, x, -1). Tenga en cuenta que se pasa la raíz del árbol, el índice de inicio se pasa como 0 y el índice final como 10 ^ 6 para que todos los rangos que tienen x se actualicen.
Ahora, la función para encontrar el índice con kth ‘1’, donde ‘k’ en este caso siempre será (n + 1) / 2, esto funcionará de manera muy similar a la búsqueda binaria, puede pensar en ello como un función de búsqueda binaria recursiva en un árbol de segmentos.
Tomemos un ejemplo para comprender, nuestro conjunto actualmente tiene elementos { 1, 4, 7, 8, 9 } y, por lo tanto, está representado por el siguiente árbol de segmentos.
Si estamos en un Node que no es una hoja, estamos seguros de que tiene ambos hijos, vemos si el hijo de la izquierda tiene más o el mismo número de uno que ‘k’, si es así, estamos seguros de que nuestro índice se encuentra en el subárbol izquierdo , de lo contrario, si el subárbol izquierdo tiene menos números 1 que k, entonces estamos seguros de que nuestro índice se encuentra en el subárbol derecho. Hacemos esto de forma recursiva para llegar a nuestro índice y desde allí, lo devolvemos.
Algoritmo
1.findKth(node, a, b, k)
2. If a != b
3. If segmentTree[ 2 * node ] >= k
4. return findKth(2*node, a, (a + b)/2, k)
5. else
6. return findKth(2*node + 1, (a + b)/2 + 1,
b, k - segmentTree[ 2 * node ])
7. else
8. return a
La función recursiva anterior se ejecuta en O( log(max_elem) ) .
C++
// A C++ program to implement insert, delete and
// median queries using segment tree
#include<bits/stdc++.h>
#define maxn 3000005
#define max_elem 1000000
using namespace std;
// A global array to store segment tree.
// Note: Since it is global, all elements are 0.
int segmentTree[maxn];
// Update 'node' and its children in segment tree.
// Here 'node' is index in segmentTree[], 'a' and
// 'b' are starting and ending indexes of range stored
// in current node.
// 'diff' is the value to be added to value 'x'.
void update(int node, int a, int b, int x, int diff)
{
// If current node is a leaf node
if (a == b && a == x )
{
// add 'diff' and return
segmentTree[node] += diff;
return ;
}
// If current node is non-leaf and 'x' is in its
// range
if (x >= a && x <= b)
{
// update both sub-trees, left and right
update(node*2, a, (a + b)/2, x, diff);
update(node*2 + 1, (a + b)/2 + 1, b, x, diff);
// Finally update current node
segmentTree[node] = segmentTree[node*2] +
segmentTree[node*2 + 1];
}
}
// Returns k'th node in segment tree
int findKth(int node, int a, int b, int k)
{
// non-leaf node, will definitely have both
// children; left and right
if (a != b)
{
// If kth element lies in the left subtree
if (segmentTree[node*2] >= k)
return findKth(node*2, a, (a + b)/2, k);
// If kth one lies in the right subtree
return findKth(node*2 + 1, (a + b)/2 + 1,
b, k - segmentTree[node*2]);
}
// if at a leaf node, return the index it stores
// information about
return (segmentTree[node])? a : -1;
}
// insert x in the set
void insert(int x)
{
update(1, 0, max_elem, x, 1);
}
// delete x from the set
void delete(int x)
{
update(1, 0, max_elem, x, -1);
}
// returns median element of the set with odd
// cardinality only
int median()
{
int k = (segmentTree[1] + 1) / 2;
return findKth(1, 0, max_elem, k);
}
// Driver code
int main()
{
insert(1);
insert(4);
insert(7);
cout << "Median for the set {1,4,7} = "
<< median() << endl;
insert(8);
insert(9);
cout << "Median for the set {1,4,7,8,9} = "
<< median() << endl;
delete(1);
delete(8);
cout << "Median for the set {4,7,9} = "
<< median() << endl;
return 0;
}
Java
// A Java program to implement insert, delete and
// median queries using segment tree
import java.io.*;
class GFG{
public static int maxn = 3000005;
public static int max_elem = 1000000;
// A global array to store segment tree.
// Note: Since it is global, all elements are 0.
public static int[] segmentTree = new int[maxn];
// Update 'node' and its children in segment tree.
// Here 'node' is index in segmentTree[], 'a' and
// 'b' are starting and ending indexes of range stored
// in current node.
// 'diff' is the value to be added to value 'x'.
public static void update(int node, int a, int b,
int x, int diff)
{
// If current node is a leaf node
if (a == b && a == x )
{
// Add 'diff' and return
segmentTree[node] += diff;
return ;
}
// If current node is non-leaf and 'x'
// is in its range
if (x >= a && x <= b)
{
// Update both sub-trees, left and right
update(node * 2, a, (a + b) / 2, x, diff);
update(node * 2 + 1, (a + b) / 2 + 1,
b, x, diff);
// Finally update current node
segmentTree[node] = segmentTree[node * 2] +
segmentTree[node * 2 + 1];
}
}
// Returns k'th node in segment tree
public static int findKth(int node, int a,
int b, int k)
{
// Non-leaf node, will definitely have both
// children; left and right
if (a != b)
{
// If kth element lies in the left subtree
if (segmentTree[node * 2] >= k)
{
return findKth(node * 2, a, (a + b) / 2, k);
}
// If kth one lies in the right subtree
return findKth(node * 2 + 1, (a + b) / 2 + 1,
b, k - segmentTree[node * 2]);
}
// If at a leaf node, return the index it stores
// information about
return (segmentTree[node] != 0) ? a : -1;
}
// Insert x in the set
public static void insert(int x)
{
update(1, 0, max_elem, x, 1);
}
// Delete x from the set
public static void delete(int x)
{
update(1, 0, max_elem, x, -1);
}
// Returns median element of the set
// with odd cardinality only
public static int median()
{
int k = (segmentTree[1] + 1) / 2;
return findKth(1, 0, max_elem, k);
}
// Driver code
public static void main(String[] args)
{
insert(1);
insert(4);
insert(7);
System.out.println("Median for the set {1,4,7} = " +
median());
insert(8);
insert(9);
System.out.println("Median for the set {1,4,7,8,9} = " +
median());
delete(1);
delete(8);
System.out.println("Median for the set {4,7,9} = " +
median());
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# A Python3 program to implement insert, delete and
# median queries using segment tree
maxn = 3000005
max_elem = 1000000
# A global array to store segment tree.
# Note: Since it is global, all elements are 0.
segmentTree = [0 for i in range(maxn)]
# Update 'node' and its children in segment tree.
# Here 'node' is index in segmentTree[], 'a' and
# 'b' are starting and ending indexes of range stored
# in current node.
# 'diff' is the value to be added to value 'x'.
def update(node, a, b, x, diff):
global segmentTree
# If current node is a leaf node
if (a == b and a == x ):
# add 'diff' and return
segmentTree[node] += diff
return
# If current node is non-leaf and 'x' is in its
# range
if (x >= a and x <= b):
# update both sub-trees, left and right
update(node * 2, a, (a + b)//2, x, diff)
update(node * 2 + 1, (a + b)//2 + 1, b, x, diff)
# Finally update current node
segmentTree[node] = segmentTree[node * 2] + segmentTree[node * 2 + 1]
# Returns k'th node in segment tree
def findKth(node, a, b, k):
global segmentTree
# non-leaf node, will definitely have both
# children left and right
if (a != b):
# If kth element lies in the left subtree
if (segmentTree[node * 2] >= k):
return findKth(node * 2, a, (a + b)//2, k)
# If kth one lies in the right subtree
return findKth(node * 2 + 1, (a + b)//2 + 1,
b, k - segmentTree[node * 2])
# if at a leaf node, return the index it stores
# information about
return a if (segmentTree[node]) else -1
# insert x in the set
def insert(x):
update(1, 0, max_elem, x, 1)
# delete x from the set
def delete(x):
update(1, 0, max_elem, x, -1)
# returns median element of the set with odd
# cardinality only
def median():
k = (segmentTree[1] + 1) // 2
return findKth(1, 0, max_elem, k)
# Driver code
if __name__ == '__main__':
insert(1)
insert(4)
insert(7)
print("Median for the set {1,4,7} =",median())
insert(8)
insert(9)
print("Median for the set {1,4,7,8,9} =",median())
delete(1)
delete(8)
print("Median for the set {4,7,9} =",median())
# This code is contributed by mohit kumar 29
C#
// A C# program to implement insert, delete
// and median queries using segment tree
using System;
class GFG{
public static int maxn = 3000005;
public static int max_elem = 1000000;
// A global array to store segment tree.
// Note: Since it is global, all elements are 0.
public static int[] segmentTree = new int[maxn];
// Update 'node' and its children in segment tree.
// Here 'node' is index in segmentTree[], 'a' and
// 'b' are starting and ending indexes of range stored
// in current node.
// 'diff' is the value to be added to value 'x'.
public static void update(int node, int a,
int b, int x, int diff)
{
// If current node is a leaf node
if (a == b && a == x)
{
// Add 'diff' and return
segmentTree[node] += diff;
return ;
}
// If current node is non-leaf and 'x'
// is in its range
if (x >= a && x <= b)
{
// Update both sub-trees, left and right
update(node * 2, a, (a + b) / 2, x, diff);
update(node * 2 + 1, (a + b) / 2 + 1,
b, x, diff);
// Finally update current node
segmentTree[node] = segmentTree[node * 2] +
segmentTree[node * 2 + 1];
}
}
// Returns k'th node in segment tree
public static int findKth(int node, int a,
int b, int k)
{
// Non-leaf node, will definitely have both
// children; left and right
if (a != b)
{
// If kth element lies in the left subtree
if (segmentTree[node * 2] >= k)
{
return findKth(node * 2, a,
(a + b) / 2, k);
}
// If kth one lies in the right subtree
return findKth(node * 2 + 1, (a + b) / 2 + 1,
b, k - segmentTree[node * 2]);
}
// If at a leaf node, return the index it
// stores information about
if (segmentTree[node] != 0)
{
return a;
}
else
{
return -1;
}
}
// Insert x in the set
public static void insert(int x)
{
update(1, 0, max_elem, x, 1);
}
// Delete x from the set
public static void delete(int x)
{
update(1, 0, max_elem, x, -1);
}
// Returns median element of the set
// with odd cardinality only
public static int median()
{
int k = (segmentTree[1] + 1) / 2;
return findKth(1, 0, max_elem, k);
}
// Driver code
static public void Main()
{
insert(1);
insert(4);
insert(7);
Console.WriteLine("Median for the set {1,4,7} = " +
median());
insert(8);
insert(9);
Console.WriteLine("Median for the set {1,4,7,8,9} = " +
median());
delete(1);
delete(8);
Console.WriteLine("Median for the set {4,7,9} = " +
median());
}
}
// This code is contributed by rag2127
Javascript
<script>
// A Javascript program to implement insert, delete and
// median queries using segment tree
let maxn = 3000005;
let max_elem = 1000000;
// A global array to store segment tree.
// Note: Since it is global, all elements are 0.
let segmentTree = new Array(maxn);
for(let i=0;i<maxn;i++)
{
segmentTree[i]=0;
}
// Update 'node' and its children in segment tree.
// Here 'node' is index in segmentTree[], 'a' and
// 'b' are starting and ending indexes of range stored
// in current node.
// 'diff' is the value to be added to value 'x'.
function update(node,a,b,x,diff)
{
// If current node is a leaf node
if (a == b && a == x )
{
// Add 'diff' and return
segmentTree[node] += diff;
return ;
}
// If current node is non-leaf and 'x'
// is in its range
if (x >= a && x <= b)
{
// Update both sub-trees, left and right
update(node * 2, a, Math.floor((a + b) / 2), x, diff);
update(node * 2 + 1, Math.floor((a + b) / 2) + 1,
b, x, diff);
// Finally update current node
segmentTree[node] = segmentTree[node * 2] +
segmentTree[node * 2 + 1];
}
}
// Returns k'th node in segment tree
function findKth(node,a,b,k)
{
// Non-leaf node, will definitely have both
// children; left and right
if (a != b)
{
// If kth element lies in the left subtree
if (segmentTree[node * 2] >= k)
{
return findKth(node * 2, a, Math.floor((a + b) / 2), k);
}
// If kth one lies in the right subtree
return findKth(node * 2 + 1, Math.floor((a + b) / 2) + 1,
b, k - segmentTree[node * 2]);
}
// If at a leaf node, return the index it stores
// information about
return (segmentTree[node] != 0) ? a : -1;
}
// Insert x in the set
function insert(x)
{
update(1, 0, max_elem, x, 1);
}
// Delete x from the set
function delet(x)
{
update(1, 0, max_elem, x, -1);
}
// Returns median element of the set
// with odd cardinality only
function median()
{
let k = (segmentTree[1] + 1) / 2;
return findKth(1, 0, max_elem, k);
}
// Driver code
insert(1);
insert(4);
insert(7);
document.write("Median for the set {1,4,7} = " +
median()+"<br>");
insert(8);
insert(9);
document.write("Median for the set {1,4,7,8,9} = " +
median()+"<br>");
delet(1);
delet(8);
document.write("Median for the set {4,7,9} = " +
median()+"<br>");
// This code is contributed by unknown2108
</script>
Producción:
Median for the set {1,4,7} = 4
Median for the set {1,4,7,8,9} = 7
Median for the set {4,7,9} = 7
Conclusión:
las tres consultas se ejecutan en O(log(max_elem)) , en este caso max_elem = 10^6, por lo que log(max_elem) es aproximadamente igual a 20.
El árbol de segmentos usa el espacio O(max_elem) .
Si la consulta de eliminación no estuviera allí, el problema también podría haberse solucionado con un algoritmo famoso aquí .
Este artículo es una contribución de Saumye Malhotra . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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