Un árbol de ondículas es una estructura de datos que divide recursivamente un flujo en dos partes hasta que nos quedan datos homogéneos. El nombre deriva de una analogía con la transformada wavelet para señales, que descompone recursivamente una señal en componentes de baja y alta frecuencia. Los árboles de wavelet se pueden usar para responder consultas de rango de manera eficiente.
Considere el problema de encontrar el número de elementos en un rango [L, R] de una array A dada que son menores que x. Una forma de resolver este problema de manera eficiente es utilizar la estructura de datos del árbol de segmentos persistentes . Pero también podemos resolver esto fácilmente usando Wavelet Trees. ¡Veamos cómo!
Construcción de árboles de ondículas
Cada Node en un árbol de ondículas está representado por una array que es la subsecuencia de la array original y un rango [L, R]. Aquí [L, R] es el rango en el que se encuentran los elementos de la array. Es decir, ‘R’ denota el elemento máximo en la array y ‘L’ denota el elemento más pequeño. Entonces, el Node raíz contendrá la array original en la que los elementos están en el rango [L, R]. Ahora calcularemos la mitad del rango [L, R] y dividiremos de manera estable la array en dos mitades para los niños izquierdo y derecho. Por lo tanto, el hijo izquierdo contendrá elementos que se encuentran en el rango [L, mid] y el hijo derecho contendrá elementos que se encuentran en el rango [mid+1, R].
Supongamos que nos dan una array de números enteros. Ahora calculamos el medio (Max + Min / 2) y formamos dos hijos.
Niños Izquierdos: Números enteros menores que/igual a Mid
Right Children : Números enteros mayores que Mid
Realizamos recursivamente esta operación hasta que se forman todos los Nodes de elementos similares.
Array dada: 0 0 9 1 2 1 7 6 4 8 9 4 3 7 5 9 2 7 0 5 1 0
Para construir un árbol Wavelet, veamos qué necesitaremos almacenar en cada Node. Entonces, en cada Node del árbol, almacenaremos dos arrays, digamos S[] y freq[]. El arreglo S[] será una subsecuencia del arreglo original A[] y el arreglo freq[] almacenará el conteo de los elementos que irán a los hijos izquierdo y derecho del Node. Es decir, freq[i] denotará el recuento de elementos de los primeros i elementos de S[] que irán al hijo izquierdo. Por lo tanto, el recuento de elementos que irán al hijo derecho se puede calcular fácilmente como (i – freq[i]).
El siguiente ejemplo muestra cómo mantener la array freq[]:
Array : 1 5 2 6 4 4 Mid = (1 + 6) / 2 = 3 Left Child : 1 2 Right Child : 5 6 4 4
Para mantener la array de frecuencias, verificaremos si el elemento es menor que Mid o no. En caso afirmativo, agregaremos 1 al último elemento de la array de frecuencias, de lo contrario, 0 y retrocederemos nuevamente.
Para, array anterior: array
Freq : {1, 1, 2, 2, 2, 2}
Implica que 1 elemento irá al hijo izquierdo de este Node desde el índice 1 y 2, y 2 elementos irán al hijo izquierdo de los índices 3 a 6. Esto se puede representar fácilmente a partir de la array anterior.
Para calcular el número de elementos que se mueven al subárbol derecho, restamos freq[i] de i.
From index 1, 0 elements go to right subtree. From index 2, 1 element go to right subtree. From index 3, 1 element go to right subtree. From index 4, 2 elements go to right subtree. From index 5, 3 elements go to right subtree. From index 6, 4 elements go to right subtree.
Podemos usar la función stable_partition y la expresión lambda en C++ STL para particionar fácilmente la array alrededor de un pivote sin distorsionar el orden de los elementos en la secuencia original. Se recomienda encarecidamente leer los artículos de expresión lambda y de partición estable antes de pasar a la implementación.
A continuación se muestra la implementación de la construcción de Wavelet Trees:
CPP
// CPP code to implement wavelet trees
#include <bits/stdc++.h>
using namespace std;
#define N 100000
// Given array
int arr[N];
// wavelet tree class
class wavelet_tree {
public:
// Range to elements
int low, high;
// Left and Right children
wavelet_tree* l, *r;
vector<int> freq;
// Default constructor
// Array is in range [x, y]
// Indices are in range [from, to]
wavelet_tree(int* from, int* to, int x, int y)
{
// Initialising low and high
low = x, high = y;
// Array is of 0 length
if (from >= to)
return;
// Array is homogeneous
// Example : 1 1 1 1 1
if (high == low) {
// Assigning storage to freq array
freq.reserve(to - from + 1);
// Initialising the Freq array
freq.push_back(0);
// Assigning values
for (auto it = from; it != to; it++)
// freq will be increasing as there'll
// be no further sub-tree
freq.push_back(freq.back() + 1);
return;
}
// Computing mid
int mid = (low + high) / 2;
// Lambda function to check if a number is
// less than or equal to mid
auto lessThanMid = [mid](int x) {
return x <= mid;
};
// Assigning storage to freq array
freq.reserve(to - from + 1);
// Initialising the freq array
freq.push_back(0);
// Assigning value to freq array
for (auto it = from; it != to; it++)
// If lessThanMid returns 1(true), we add
// 1 to previous entry. Otherwise, we add
// 0 (element goes to right sub-tree)
freq.push_back(freq.back() + lessThanMid(*it));
// std::stable_partition partitions the array w.r.t Mid
auto pivot = stable_partition(from, to, lessThanMid);
// Left sub-tree's object
l = new wavelet_tree(from, pivot, low, mid);
// Right sub-tree's object
r = new wavelet_tree(pivot, to, mid + 1, high);
}
};
// Driver code
int main()
{
int size = 5, high = INT_MIN;
int arr[] = {1 , 2, 3, 4, 5};
for (int i = 0; i < size; i++)
high = max(high, arr[i]);
// Object of class wavelet tree
wavelet_tree obj(arr, arr + size, 1, high);
return 0;
}
Altura del árbol : O(log(max(A)) , donde max(A) es el elemento máximo en la array A[].
Consultas en árboles Wavelet
Ya hemos construido nuestro árbol wavelet para el arreglo dado. Ahora pasaremos a nuestro problema para calcular el número de elementos menores o iguales ax en el rango [L,R] en la array dada.
Entonces, para cada Node tenemos una subsecuencia de la array original, los valores más bajos y más altos presentes en la array y el recuento de elementos en los elementos secundarios izquierdo y derecho.
Ahora,
If high <= x, we return R - L + 1. i.e. all the elements in the current range is less than x.
De lo contrario, usaremos la variable LtCount = freq[ L-1 ] (es decir, elementos que van al subárbol izquierdo desde L-1), RtCount = freq[ R ] (es decir, elementos que van al subárbol derecho desde R)
Ahora, llame recursivamente y agregue los valores de retorno de:
left sub-tree with range[ LtCount + 1, RtCount ] and, right sub-tree with range[ L - Ltcount,R - RtCount ]
A continuación se muestra la implementación en C++:
CPP
// CPP program for querying in
// wavelet tree Data Structure
#include <bits/stdc++.h>
using namespace std;
#define N 100000
// Given Array
int arr[N];
// wavelet tree class
class wavelet_tree {
public:
// Range to elements
int low, high;
// Left and Right child
wavelet_tree* l, *r;
vector<int> freq;
// Default constructor
// Array is in range [x, y]
// Indices are in range [from, to]
wavelet_tree(int* from, int* to, int x, int y)
{
// Initialising low and high
low = x, high = y;
// Array is of 0 length
if (from >= to)
return;
// Array is homogeneous
// Example : 1 1 1 1 1
if (high == low) {
// Assigning storage to freq array
freq.reserve(to - from + 1);
// Initialising the Freq array
freq.push_back(0);
// Assigning values
for (auto it = from; it != to; it++)
// freq will be increasing as there'll
// be no further sub-tree
freq.push_back(freq.back() + 1);
return;
}
// Computing mid
int mid = (low + high) / 2;
// Lambda function to check if a number
// is less than or equal to mid
auto lessThanMid = [mid](int x) {
return x <= mid;
};
// Assigning storage to freq array
freq.reserve(to - from + 1);
// Initialising the freq array
freq.push_back(0);
// Assigning value to freq array
for (auto it = from; it != to; it++)
// If lessThanMid returns 1(true), we add
// 1 to previous entry. Otherwise, we add 0
// (element goes to right sub-tree)
freq.push_back(freq.back() + lessThanMid(*it));
// std::stable_partition partitions the array w.r.t Mid
auto pivot = stable_partition(from, to, lessThanMid);
// Left sub-tree's object
l = new wavelet_tree(from, pivot, low, mid);
// Right sub-tree's object
r = new wavelet_tree(pivot, to, mid + 1, high);
}
// Count of numbers in range[L..R] less than
// or equal to k
int kOrLess(int l, int r, int k)
{
// No elements int range is less than k
if (l > r or k < low)
return 0;
// All elements in the range are less than k
if (high <= k)
return r - l + 1;
// Computing LtCount and RtCount
int LtCount = freq[l - 1];
int RtCount = freq[r];
// Answer is (no. of element <= k) in
// left + (those <= k) in right
return (this->l->kOrLess(LtCount + 1, RtCount, k) +
this->r->kOrLess(l - LtCount, r - RtCount, k));
}
};
// Driver code
int main()
{
int size = 5, high = INT_MIN;
int arr[] = {1, 2, 3, 4, 5};
// Array : 1 2 3 4 5
for (int i = 0; i < size; i++)
high = max(high, arr[i]);
// Object of class wavelet tree
wavelet_tree obj(arr, arr + size, 1, high);
// count of elements less than 2 in range [1,3]
cout << obj.kOrLess(0, 3, 2) << '\n';
return 0;
}
Producción :
2
Complejidad de tiempo : O(log(max(A)) , donde max(A) es el elemento máximo en la array A[].
En esta publicación hemos discutido sobre un solo problema en consultas de rango sin actualización. Más adelante estaremos discutiendo sobre actualizaciones de rango
también .
- https://users.dcc.uchile.cl/~jperez/papers/ioiconf16.pdf
- https://en.wikipedia.org/wiki/Wavelet_Tree
- https://www.youtube.com/watch?v=K7tju9j7UWU
Este artículo es una contribución de Rohit Thapliyal . 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