Dada una array de n números, la tarea es responder a las siguientes consultas:
kthSmallest(start, end, k) : Find the Kth smallest
number in the range from array
index 'start' to 'end'.
Ejemplos:
Input : arr[] = {3, 2, 5, 1, 8, 9|
Query 1: start = 2, end = 5, k = 2
Query 2: start = 1, end = 6, k = 4
Output : 2
5
Explanation:
[2, 5, 1, 8] represents the range from 2 to
5 and 2 is the 2nd smallest number
in the range[3, 2, 5, 1, 8, 9] represents
the range from 1 to 6 and 5 is the 4th
smallest number in the range
La idea clave es construir un árbol de segmentos con un vector en cada Node y el vector contiene todos los elementos del subrango en un orden ordenado. Y si observamos esta estructura de árbol de segmentos, es algo similar al árbol formado durante el algoritmo de clasificación por combinación (es por eso que se llama árbol de clasificación por combinación) . rango)En primer lugar, mantenemos un vector de pares donde cada par {valor, índice} es tal que el primer elemento del par representa el elemento de la array de entrada y el segundo elemento del par representa el índice en el que se produce. Ahora ordenamos este vector de pares sobre la base del primer elemento de cada par. Después de esto, construimos un árbol de clasificación combinado donde cada Node tiene un vector de índices en el rango ordenado. Cuando tenemos que responder a una consulta, encontramos si el K- ésimo número más pequeño se encuentra en el subárbol izquierdo o en el subárbol derecho. La idea es usar dos búsquedas binarias y encontrar la cantidad de elementos en el subárbol izquierdo de modo que los índices se encuentren dentro del rango de consulta dado. Sea M el número de dichos índices. Si M>=K, significa que podremos encontrar el K thNúmero más pequeño en el subárbol izquierdo, por lo que llamamos al subárbol izquierdo. De lo contrario, el K -ésimo número más pequeño se encuentra en el subárbol derecho, pero esta vez no tenemos que buscar el K- ésimo número más pequeño porque ya tenemos los primeros M números más pequeños del rango en el sub-árbol izquierdo, por lo que deberíamos buscar para la parte restante, es decir, el (KM) ésimo número en el subárbol derecho. Este es el Índice del K número más pequeño. El valor en este índice es el número requerido.
CPP
// CPP program to implement k-th order statistics
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// Constructs a segment tree and stores tree[]
void buildTree(int treeIndex, int l, int r,
vector<pair<int, int> > &a, vector<int> tree[])
{
/* l => start of range,
r => ending of a range
treeIndex => index in the Segment Tree/Merge
Sort Tree */
/* leaf node */
if (l == r) {
tree[treeIndex].push_back(a[l].second);
return;
}
int mid = (l + r) / 2;
/* building left subtree */
buildTree(2 * treeIndex, l, mid, a, tree);
/* building left subtree */
buildTree(2 * treeIndex + 1, mid + 1, r, a, tree);
/* merging left and right child in sorted order */
merge(tree[2 * treeIndex].begin(),
tree[2 * treeIndex].end(),
tree[2 * treeIndex + 1].begin(),
tree[2 * treeIndex + 1].end(),
back_inserter(tree[treeIndex]));
}
// Returns the Kth smallest number in query range
int queryRec(int segmentStart, int segmentEnd,
int queryStart, int queryEnd, int treeIndex,
int K, vector<int> tree[])
{
/*
segmentStart => start of a Segment,
segmentEnd => ending of a Segment,
queryStart => start of a query range,
queryEnd => ending of a query range,
treeIndex => index in the Segment
Tree/Merge Sort Tree,
K => kth smallest number to find */
if (segmentStart == segmentEnd)
return tree[treeIndex][0];
int mid = (segmentStart + segmentEnd) / 2;
// finds the last index in the segment
// which is <= queryEnd
int last_in_query_range =
(upper_bound(tree[2 * treeIndex].begin(),
tree[2 * treeIndex].end(),
queryEnd)
- tree[2 * treeIndex].begin());
// finds the first index in the segment
// which is >= queryStart
int first_in_query_range =
(lower_bound(tree[2 * treeIndex].begin(),
tree[2 * treeIndex].end(),
queryStart)
- tree[2 * treeIndex].begin());
int M = last_in_query_range - first_in_query_range;
if (M >= K) {
// Kth smallest is in left subtree,
// so recursively call left subtree for Kth
// smallest number
return queryRec(segmentStart, mid, queryStart,
queryEnd, 2 * treeIndex, K, tree);
}
else {
// Kth smallest is in right subtree,
// so recursively call right subtree for the
// (K-M)th smallest number
return queryRec(mid + 1, segmentEnd, queryStart,
queryEnd, 2 * treeIndex + 1, K - M, tree);
}
}
// A wrapper over query()
int query(int queryStart, int queryEnd, int K, int n,
vector<pair<int, int> > &a, vector<int> tree[])
{
return queryRec(0, n - 1, queryStart - 1, queryEnd - 1,
1, K, tree);
}
// Driver code
int main()
{
int arr[] = { 3, 2, 5, 1, 8, 9 };
int n = sizeof(arr)/sizeof(arr[0]);
// vector of pairs of form {element, index}
vector<pair<int, int> > v;
for (int i = 0; i < n; i++) {
v.push_back(make_pair(arr[i], i));
}
// sort the vector
sort(v.begin(), v.end());
// Construct segment tree in tree[]
vector<int> tree[MAX];
buildTree(1, 0, n - 1, v, tree);
// Answer queries
// kSmallestIndex hold the index of the kth smallest number
int kSmallestIndex = query(2, 5, 2, n, v, tree);
cout << arr[kSmallestIndex] << endl;
kSmallestIndex = query(1, 6, 4, n, v, tree);
cout << arr[kSmallestIndex] << endl;
return 0;
}
2 5
Por lo tanto, podemos obtener la K- ésima consulta del número más pequeño en el rango L a R, en O(n(logn) 2 ) construyendo el árbol de ordenación por combinación en los índices.