Dada una array de N números y Q consultas, cada consulta consta de L y R. Necesitamos escribir un programa que imprima el número de ocurrencia del elemento más pequeño en el rango LR.
Ejemplos:
Input: a[] = {1, 1, 2, 4, 3, 3}
Q = 2
L = 1 R = 4
L = 3 R = 6
Output: 2
1
Explanation: The smallest element in range 1-4
is 1 which occurs 2 times. The smallest element
in the range 3-6 is 2 which occurs once.
Input : a[] = {1, 2, 3, 3, 1}
Q = 2
L = 1 R = 5
L = 3 R = 4
Output : 2
2
Un enfoque normal será iterar desde LR y encontrar el elemento más pequeño en el rango. Vuelva a iterar en el rango LR y cuente el número de veces que aparece el elemento más pequeño en el rango LR. En el peor de los casos, la complejidad será O(N) si L=1 y R=N.
Un enfoque eficiente será usar árboles de segmentos para resolver el problema anterior. En cada Node del árbol de segmentos, se almacena el elemento más pequeño y el recuento del elemento más pequeño. En los Nodes de hoja, el elemento de array se almacena en el mínimo y el conteo almacena 1. Para todos los demás Nodes excepto los Nodes de hoja, fusionamos los Nodes derecho e izquierdo siguiendo las condiciones dadas:
1. min(subárbol_izquierdo) < min(subárbol_derecho):
Node.min=min(subárbol_izquierdo), Node.contar = subárbol_izquierdo.contar
2. min(subárbol_izquierdo) > min(subárbol_derecho):
Node.min=min(subárbol_derecho), Node .count=right_subtree.count
3. min(left_subtree) = min(right_subtree):
node.min=min(left_subtree) o min(right_subtree), node.count=left_subtree.count + right_subtree.count
A continuación se muestra la implementación del enfoque anterior:
// CPP program to Count number of occurrence of
// smallest element in range L-R
#include <bits/stdc++.h>
using namespace std;
#define N 100005
// predefines the tree with nodes
// storing min and count
struct node {
int min;
int cnt;
} tree[5 * N];
// function to construct the tree
void buildtree(int low, int high, int pos, int a[])
{
// base condition
if (low == high) {
// leaf node has a single element
tree[pos].min = a[low];
tree[pos].cnt = 1;
return;
}
int mid = (low + high) >> 1;
// left-subtree
buildtree(low, mid, 2 * pos + 1, a);
// right-subtree
buildtree(mid + 1, high, 2 * pos + 2, a);
// left subtree has the minimum element
if (tree[2 * pos + 1].min < tree[2 * pos + 2].min) {
tree[pos].min = tree[2 * pos + 1].min;
tree[pos].cnt = tree[2 * pos + 1].cnt;
}
// right subtree has the minimum element
else if (tree[2 * pos + 1].min > tree[2 * pos + 2].min) {
tree[pos].min = tree[2 * pos + 2].min;
tree[pos].cnt = tree[2 * pos + 2].cnt;
}
// both subtree has the same minimum element
else {
tree[pos].min = tree[2 * pos + 1].min;
tree[pos].cnt = tree[2 * pos + 1].cnt + tree[2 * pos + 2].cnt;
}
}
// function that answers every query
node query(int s, int e, int low, int high, int pos)
{
node dummy;
// out of range
if (e < low or s > high) {
dummy.min = dummy.cnt = INT_MAX;
return dummy;
}
// in range
if (s >= low and e <= high) {
return tree[pos];
}
int mid = (s + e) >> 1;
// left-subtree
node ans1 = query(s, mid, low, high, 2 * pos + 1);
// right-subtree
node ans2 = query(mid + 1, e, low, high, 2 * pos + 2);
node ans;
ans.min = min(ans1.min, ans2.min);
// add count when min is same of both subtree
if (ans1.min == ans2.min)
ans.cnt = ans2.cnt + ans1.cnt;
// store the minimal's count
else if (ans1.min < ans2.min)
ans.cnt = ans1.cnt;
else
ans.cnt = ans2.cnt;
return ans;
}
// function to answer query in range l-r
int answerQuery(int a[], int n, int l, int r)
{
// calls the function which returns a node
// this function returns the count which
// will be the answer
return query(0, n - 1, l - 1, r - 1, 0).cnt;
}
// Driver Code
int main()
{
int a[] = { 1, 1, 2, 4, 3, 3 };
int n = sizeof(a) / sizeof(a[0]);
buildtree(0, n - 1, 0, a);
int l = 1, r = 4;
// answers 1-st query
cout << answerQuery(a, n, l, r) << endl;
l = 2, r = 6;
// answers 2nd query
cout << answerQuery(a, n, l, r) << endl;
return 0;
}
Producción:
2 1
Complejidad temporal: O(n) para la construcción del árbol. O(log n) para cada consulta.