Dada una array arr[] de tamaño N y un conjunto Q[][] que contiene M consultas, la tarea es ejecutar las consultas en la array dada de modo que pueda haber dos tipos de consultas:
- Tipo 1: [i, x]: actualice el elemento en el i -ésimo índice a x.
- Tipo 2: [k]: encuentre el k -ésimo elemento más pequeño de la array.
Ejemplos:
Entrada: arr[] = {4, 3, 6, 2}, Q[][] = {{1, 2, 5}, {2, 3}, {1, 1, 7}, {2, 1} }
Salida: 5 2
Explicación:
Para la primera consulta: arr[] = {4, 5, 6, 2}
Para la segunda consulta: el tercer elemento más pequeño sería 5.
Para la tercera consulta: arr [] = {7, 5, 6, 2}
Para la 4ª consulta: el 1er elemento más pequeño sería 2.Entrada: arr[] = {1, 0, 4, 2, 0}, Q[][] = {{1, 2, 1}, {2, 2}, {1, 4, 5}, {1, 3, 7}, {2, 1}, {2, 5}}
Salida: 1 0 7
Enfoque ingenuo: el enfoque ingenuo para este problema es actualizar el i -ésimo elemento en una array en tiempo constante y usar la clasificación para encontrar el K -ésimo elemento más pequeño .
Complejidad de tiempo: O(M * (N * log(N))) donde M es el número de consultas y N es el tamaño de la array.
Enfoque eficiente: la idea es utilizar una estructura de datos basada en políticas similar a un conjunto .
Aquí, se utiliza un contenedor basado en árbol para almacenar la array en forma de árbol ordenado de modo que todos los Nodes de la izquierda sean más pequeños que la raíz y todos los Nodes de la derecha sean más grandes que la raíz. Las siguientes son las propiedades de la estructura de datos:
- Se indexa manteniendo el Node invariable donde cada Node contiene un recuento de Nodes en su subárbol.
- Cada vez que insertamos un nuevo Node o eliminamos un Node, podemos mantener el invariante en el tiempo O (logN) aumentando hasta la raíz.
- Entonces, el recuento del Node en su subárbol izquierdo da el índice de ese Node en orden porque el valor de cada Node del subárbol izquierdo es más pequeño que el Node principal.
Por lo tanto, la idea es seguir el siguiente enfoque para cada consulta:
- Tipo 1: para esta consulta, actualizamos el i -ésimo elemento de la array. Por lo tanto, necesitamos actualizar el elemento tanto en la array como en la estructura de datos. Para actualizar el valor en el contenedor del árbol, el valor arr[i] se encuentra en el árbol, se elimina del árbol y el valor actualizado se vuelve a insertar en el árbol.
- Tipo 2: Para encontrar el K -ésimo elemento más pequeño, se usa find_by_order(K – 1) en el árbol ya que los datos son datos ordenados. Esto es similar a la operación de búsqueda binaria en la array ordenada.
A continuación se muestra la implementación del enfoque anterior:
// C++ implementation of the above approach
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// Defining the policy based Data Structure
typedef tree<pair<int, int>,
null_type,
less<pair<int, int> >,
rb_tree_tag,
tree_order_statistics_node_update>
indexed_set;
// Elements in the array are not unique,
// so a pair is used to give uniqueness
// by incrementing cnt and assigning
// with array elements to insert in mySet
int cnt = 0;
// Variable to store the data in the
// policy based Data Structure
indexed_set mySet;
// Function to insert the elements
// of the array in mySet
void insert(int n, int arr[])
{
for (int i = 0; i < n; i++) {
mySet.insert({ arr[i], cnt });
cnt++;
}
}
// Function to update the value in
// the data structure
void update(int x, int y)
{
// Get the pointer of the element
// in mySet which has to be updated
auto it = mySet.lower_bound({ y, 0 });
// Delete from mySet
mySet.erase(it);
// Insert the updated value in mySet
mySet.insert({ x, cnt });
cnt++;
}
// Function to find the K-th smallest
// element in the set
int get(int k)
{
// Find the pointer to the kth smallest element
auto it = mySet.find_by_order(k - 1);
return (it->first);
}
// Function to perform the queries on the set
void operations(int arr[], int n,
vector<vector<int> > query, int m)
{
// To insert the element in mySet
insert(n, arr);
// Iterating through the queries
for (int i = 0; i < m; i++) {
// Checking if the query is of type 1
// or type 2
if (query[i][0] == 1) {
// The array is 0-indexed
int j = query[i][1] - 1;
int x = query[i][2];
// Update the element in mySet
update(x, arr[j]);
// Update the element in the array
arr[j] = x;
}
else {
int K = query[i][1];
// Print Kth smallest element
cout << get(K) << endl;
}
}
}
// Driver code
int main()
{
int n = 5, m = 6, arr[] = { 1, 0, 4, 2, 0 };
vector<vector<int> > query = { { 1, 2, 1 },
{ 2, 2 },
{ 1, 4, 5 },
{ 1, 3, 7 },
{ 2, 1 },
{ 2, 5 } };
operations(arr, n, query, m);
return 0;
}
1 0 7
Complejidad de tiempo: dado que cada operación requiere un tiempo de O(Log(N)) y hay M consultas, la complejidad de tiempo general es O(M * Log(N)) .