K-ésimo elemento más pequeño en un subarreglo

Dada una array arr de tamaño N . La tarea es encontrar el k-ésimo elemento más pequeño en el subarreglo (l a r, ambos inclusive). 

Nota : 

• Las consultas son de tipo consulta (l, r, k)
• 1 <= k <= r-l+1
• Puede haber múltiples consultas.

Ejemplos:  

Entrada: arr = {3, 2, 5, 4, 7, 1, 9}, consulta = (2, 6, 3) 
Salida: 4 
subarreglo ordenado en un rango de 2 a 6 es {1, 2, 4, 5, 7} y el tercer elemento es 4

Entrada: arr = {2, 3, 4, 1, 6, 5, 8}, consulta = (1, 5, 2) 
Salida: 2

Let, S = r - l + 1.

Enfoque ingenuo:  

• Copie el subarreglo en algún otro arreglo local. Después de ordenar, encuentre el k-ésimo elemento. 
  Complejidad del tiempo: Slog(S)
• Use una cola de prioridad máxima ‘p’ e itere en el subarreglo. Si el tamaño de ‘p’ es menor que ‘k’, inserte el elemento; de lo contrario, elimine el elemento superior e inserte el nuevo elemento en ‘p’ después de completar la interacción, la parte superior de ‘p’ será la respuesta.
  Complejidad del tiempo: Slog(k)

Enfoque eficiente: la idea es usar árboles de segmentos , para ser más precisos, usar el árbol de segmentos de clasificación por combinación . Aquí, en lugar de almacenar elementos ordenados, almacenamos índices de elementos ordenados.

Sea B la array después de ordenar arr y seg es nuestro árbol de segmentos. El Node c _i de seg almacena el orden ordenado de los índices de arr que están en el rango [st, end] .

If arr = {3, 1, 5, 2, 4, 7, 8, 6},
then B is {1, 2, 3, 4, 5, 6, 7, 8}

El árbol de segmentos se verá así: 

Supongamos que seg[ci]->left contiene p elementos. Si p es menor o igual a k , podemos encontrar el k-ésimo más pequeño en el elemento secundario izquierdo y si p es menor que k , pasar al elemento secundario derecho y encontrar (kp) el elemento más pequeño.

Uno puede encontrar el número de elementos en la array ordenada (A) que se encuentran entre los elementos X e Y por: 

límite_superior(A.comienzo(), A.fin(), Y)-límite_inferior(A.comienzo(), A.fin(), X)

A continuación se muestra la implementación del enfoque anterior:  

// C++ program to find the kth smallest element in a range
#include <bits/stdc++.h>
using namespace std;
#define N (int)1e5
 
// Declaring a global segment tree
vector<int> seg[N];
 
// Function to build the merge sort
// segment tree of indices
void build(int ci, int st, int end,
           pair<int, int>* B)
{
    if (st == end) {
        // Using second property of B
        seg[ci].push_back(B[st].second);
        return;
    }
 
    int mid = (st + end) / 2;
    build(2 * ci + 1, st, mid, B);
    build(2 * ci + 2, mid + 1, end, B);
 
    // Inbuilt merge function
    // this takes two sorted arrays and merge
    // them into a sorted array
    merge(seg[2 * ci + 1].begin(), seg[2 * ci + 1].end(),
          seg[2 * ci + 2].begin(), seg[2 * ci + 2].end(),
          back_inserter(seg[ci]));
}
 
// Function to return the index of
// kth smallest element in range [l, r]
int query(int ci, int st, int end,
          int l, int r, int k)
{
    // Base case
    if (st == end)
        return seg[ci][0];
 
    // Finding value of 'p' as described in article
    // seg[2*ci+1] is left node of seg[ci]
    int p = upper_bound(seg[2 * ci + 1].begin(),
                        seg[2 * ci + 1].end(), r)
            - lower_bound(seg[2 * ci + 1].begin(),
                          seg[2 * ci + 1].end(), l);
 
    int mid = (st + end) / 2;
    if (p >= k)
        return query(2 * ci + 1, st, mid, l, r, k);
    else
        return query(2 * ci + 2, mid + 1, end, l, r, k - p);
}
 
// Driver code
int main()
{
    int arr[] = { 3, 1, 5, 2, 4, 7, 8, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    pair<int, int> B[n];
 
    for (int i = 0; i < n; i++) {
        B[i] = { arr[i], i };
    }
 
    // After sorting, B's second property is
    // something upon which we will build our Tree
    sort(B, B + n);
 
    // Build the tree
    build(0, 0, n - 1, B);
 
    cout << "3rd smallest element in range 3 to 7 is: "
         << arr[query(0, 0, n - 1, 2, 6, 3)] << "\n";
}

3rd smallest element in range 3 to 7 is: 5

Complejidad del tiempo: 
Para construir el árbol de segmentos: O(n*log(n)) 
Para cada consulta: O(log(n)*log(n))