Dada una array donde cada elemento es un vector que contiene números enteros ordenados. La tarea es responder a las siguientes consultas:
count(start, end, k) : Count the numbers smaller than or equal
to k in range from array index 'start'
to 'end'.
Por conveniencia, consideramos una array bidimensional n * n donde cada fila corresponde a un vector entero. Ejemplos:
Input : ar[][] = {{2, 4, 5},
{3, 4, 9},
{6, 8, 10}}
Queries[] = (0, 1, 5)
(1, 2, 1)
(0, 2, 6)
Output : 5
0
6
Count of elements (smaller than or equal to 5) from
1st row (index 0) to 2nd row (index 1) is 5.
Count of elements (smaller than or equal to 1) from
2nd row to 3nd row is 0
Count of elements (smaller than or equal to 6) from
1st row to 3nd row is 6.
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 fusión (por eso se llama árbol de clasificación por fusión)
CPP
// C++ program to count number of smaller or
// equal to given number and given row range.
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// Constructs a segment tree and stores sTree[]
void buildTree(int idx, int ss, int se, vector<int> a[],
vector<int> sTree[])
{
/*leaf node*/
if (ss == se)
{
sTree[idx] = a[ss];
return;
}
int mid = (ss+se)/2;
/* building left subtree */
buildTree(2*idx+1, ss, mid, a, sTree);
/* building right subtree */
buildTree(2*idx+2, mid+1, se, a, sTree);
/* merging left and right child in sorted order */
merge(sTree[2*idx+1].begin(), sTree[2*idx+1].end(),
sTree[2*idx+2].begin(), sTree[2*idx+2].end(),
back_inserter(sTree[idx]));
}
// Recursive function to count smaller elements from row
// a[ss] to a[se] and value smaller than or equal to k.
int queryRec(int node, int start, int end, int ss, int se,
int k, vector<int> a[], vector<int> sTree[])
{
/* If out of range return 0 */
if (ss > end || start > se)
return 0;
/* if inside the range return count */
if (ss <= start && se >= end)
{
/* binary search over the sorted vector
to return count >= X */
return upper_bound(sTree[node].begin(),
sTree[node].end(), k) -
sTree[node].begin();
}
int mid = (start+end)/2;
/*searching in left subtree*/
int p1 = queryRec(2*node+1, start, mid, ss, se, k, a, sTree);
/*searching in right subtree*/
int p2 = queryRec(2*node+2, mid+1, end, ss, se, k, a, sTree);
/*adding both the result*/
return p1 + p2;
}
// A wrapper over query().
int query(int start, int end, int k, vector<int> a[], int n,
vector<int> sTree[])
{
return queryRec(0, 0, n-1, start, end, k, a, sTree);
}
// Driver code
int main()
{
int n = 3;
int arr[][3] = { {2, 4, 5},
{3, 4, 9},
{6, 8, 10}};
// build an array of vectors from above input
vector<int> a[n];
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
a[i].push_back(arr[i][j]);
// Construct segment tree
vector<int> sTree[MAX];
buildTree(0, 0, n-1, a, sTree);
/* un-comment to print merge sort tree*/
/*for (int i=0;i<2*n-1;i++)
{
cout << i << " ";
for (int j=0;j<sTree[i].size();j++)
cout << sTree[i][j]<<" ";
cout << endl;
}*/
// Answer queries
cout << query(0, 1, 5, a, n, sTree) << endl;
cout << query(1, 2, 1, a, n, sTree) << endl;
cout << query(0, 2, 6, a, n, sTree) << endl;
return 0;
}
Producción:
5 0 6
Análisis de buildTree(): construir un árbol de ordenación de combinación toma un tiempo O (N log N), que es lo mismo que el algoritmo de ordenación de combinación. También ocupa O(n log n) espacio extra. análisis de consulta(): un rango de ‘inicio’ a ‘final’ se puede dividir en la mayoría de las partes Log (n), donde realizaremos una búsqueda binaria en cada parte. La búsqueda binaria requiere O (Log n). Por lo tanto complejidad total O(Log n * Log n). Este artículo es una contribución de Vineet Jha . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.orgo envíe su 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