Dada una array arr[] de N elementos y dos números enteros A a B , la tarea es responder Q consultas, cada una de las cuales tiene dos números enteros L y R. Para cada consulta, la tarea es encontrar el número de elementos en el subarreglo arr[L…R] que se encuentra dentro del rango A a B (ambos incluidos).
Ejemplos:
Entrada: arr[] = {7, 3, 9, 13, 5, 4}, A=4, B=7
consulta = { 1, 5 }
Salida: 2
Explicación:
solo 5 y 4 se encuentran entre 4 y 7
en el subarreglo {3, 9, 13, 5, 4}.Entrada: arr[] = {0, 1, 2, 3, 4, 5, 6, 7}, A=1, B=5 consulta =
{ 3, 5 }
Salida: 3
Explicación:
Todos los elementos 3, 4 y 5 se encuentra entre 1 y 5
en el subarreglo {3, 4, 5}.
Requisito previo: árbol de segmentos
Enfoque ingenuo: encuentre la respuesta para cada consulta simplemente recorriendo la array desde el índice L hasta el R y siga agregando 1 al conteo siempre que el elemento de la array se encuentre dentro del rango A a B . La complejidad temporal de este enfoque será O(n * q) .
Enfoque eficiente:
construir un árbol de segmentos .
Representación de árboles de segmentos
1. Los Nodes hoja son los elementos del arreglo de entrada.
2. Cada Node interno contiene el número de hojas que se encuentra dentro del rango A a B de todas las hojas debajo de él.
Construcción de un árbol de segmentos a partir de una array dada
Comenzamos con un segmento arr[0 . . . n-1]. y cada vez que dividimos el segmento actual en dos mitades (si aún no se ha convertido en un segmento de longitud 1), y luego llamamos al mismo procedimiento en ambas mitades, y para cada uno de esos segmentos, almacenamos el número de elementos que se encuentran dentro el rango A a B de todos los Nodes debajo de él.
La complejidad temporal de este enfoque será O(q * log(n))
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Procedure to build the segment tree
void buildTree(vector<int>& tree, int* arr,
int index, int s, int e, int A, int B)
{
// Reached the leaf node
// of the segment tree
if (s == e) {
if (arr[s] >= A && arr[s] <= B)
tree[index] = 1;
else
tree[index] = 0;
return;
}
// Recursively call the buildTree
// on both the nodes of the tree
int mid = (s + e) / 2;
buildTree(tree, arr, 2 * index, s, mid, A, B);
buildTree(tree, arr, 2 * index + 1, mid + 1, e, A, B);
tree[index] = tree[2 * index] + tree[2 * index + 1];
}
// Query procedure to get the answer
// for each query l and r are query range
int query(vector<int> tree, int index, int s,
int e, int l, int r)
{
// out of bound or no overlap
if (r < s || l > e)
return 0;
// Complete overlap
// Query range completely lies in
// the segment tree node range
if (s >= l && e <= r) {
return tree[index];
}
// Partially overlap
// Query range partially lies in
// the segment tree node range
int mid = (s + e) / 2;
return (query(tree, 2 * index, s, mid, l, r)
+ query(tree, 2 * index + 1, mid + 1, e, l, r));
}
// Driver code
int main()
{
int arr[] = { 7, 3, 9, 13, 5, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
vector<int> tree(4 * n + 1);
int L = 1, R = 5, A = 4, B = 7;
buildTree(tree, arr, 1, 0, n - 1, A, B);
cout << query(tree, 1, 0, n - 1, L, R)
<< endl;
return 0;
}
Java
// Java implementation of the approach
class GFG{
// Procedure to build the segment tree
static void buildTree(int tree[] , int arr[] ,
int index, int s, int e,
int A, int B)
{
// Reached the leaf node
// of the segment tree
if (s == e)
{
if (arr[s] >= A && arr[s] <= B)
tree[index] = 1;
else
tree[index] = 0;
return;
}
// Recursively call the buildTree
// on both the nodes of the tree
int mid = (s + e) / 2;
buildTree(tree, arr, 2 * index,
s, mid, A, B);
buildTree(tree, arr, 2 * index + 1,
mid + 1, e, A, B);
tree[index] = tree[2 * index] +
tree[2 * index + 1];
}
// Query procedure to get the answer
// for each query l and r are query range
static int query(int tree[], int index, int s,
int e, int l, int r)
{
// Out of bound or no overlap
if (r < s || l > e)
return 0;
// Complete overlap
// Query range completely lies in
// the segment tree node range
if (s >= l && e <= r)
{
return tree[index];
}
// Partially overlap
// Query range partially lies in
// the segment tree node range
int mid = (s + e) / 2;
return (query(tree, 2 * index,
s, mid, l, r) +
query(tree, 2 * index + 1,
mid + 1, e, l, r));
}
// Driver code
public static void main (String []args)
{
int arr[] = { 7, 3, 9, 13, 5, 4 };
int n = arr.length;
int tree[] = new int [(4 * n + 1)];
int L = 1, R = 5, A = 4, B = 7;
buildTree(tree, arr, 1, 0, n - 1, A, B);
System.out.print(query(tree, 1, 0, n - 1, L, R));
}
}
// This code is contributed by chitranayal
Python3
# Python3 implementation of the approach # Procedure to build the segment tree def buildTree(tree,arr,index, s, e, A, B): # Reached the leaf node # of the segment tree if (s == e): if (arr[s] >= A and arr[s] <= B): tree[index] = 1 else: tree[index] = 0 return # Recursively call the buildTree # on both the nodes of the tree mid = (s + e) // 2 buildTree(tree, arr, 2 * index, s, mid, A, B) buildTree(tree, arr, 2 * index + 1, mid + 1, e, A, B) tree[index] = tree[2 * index] + tree[2 * index + 1] # Query procedure to get the answer # for each query l and r are query range def query(tree, index, s, e, l, r): # out of bound or no overlap if (r < s or l > e): return 0 # Complete overlap # Query range completely lies in # the segment tree node range if (s >= l and e <= r): return tree[index] # Partially overlap # Query range partially lies in # the segment tree node range mid = (s + e) // 2 return (query(tree, 2 * index, s, mid, l, r) + query(tree, 2 * index + 1, mid + 1, e, l, r)) # Driver code if __name__ == '__main__': arr=[7, 3, 9, 13, 5, 4] n = len(arr) tree=[0]*(4 * n + 1) L = 1 R = 5 A = 4 B = 7 buildTree(tree, arr, 1, 0, n - 1, A, B) print(query(tree, 1, 0, n - 1, L, R)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG{
// Procedure to build the segment tree
static void buildTree(int[] tree, int[] arr,
int index, int s, int e,
int A, int B)
{
// Reached the leaf node
// of the segment tree
if (s == e)
{
if (arr[s] >= A && arr[s] <= B)
tree[index] = 1;
else
tree[index] = 0;
return;
}
// Recursively call the buildTree
// on both the nodes of the tree
int mid = (s + e) / 2;
buildTree(tree, arr, 2 * index,
s, mid, A, B);
buildTree(tree, arr, 2 * index + 1,
mid + 1, e, A, B);
tree[index] = tree[2 * index] +
tree[2 * index + 1];
}
// Query procedure to get the answer
// for each query l and r are query range
static int query(int[] tree, int index, int s,
int e, int l, int r)
{
// Out of bound or no overlap
if (r < s || l > e)
return 0;
// Complete overlap
// Query range completely lies in
// the segment tree node range
if (s >= l && e <= r)
{
return tree[index];
}
// Partially overlap
// Query range partially lies in
// the segment tree node range
int mid = (s + e) / 2;
return (query(tree, 2 * index,
s, mid, l, r) +
query(tree, 2 * index + 1,
mid + 1, e, l, r));
}
// Driver code
public static void Main ()
{
int[] arr = new int[] { 7, 3, 9, 13, 5, 4 };
int n = arr.Length;
int[] tree = new int [(4 * n + 1)];
int L = 1, R = 5, A = 4, B = 7;
buildTree(tree, arr, 1, 0, n - 1, A, B);
Console.Write(query(tree, 1, 0, n - 1, L, R));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript implementation of the approach
// Procedure to build the segment tree
function buildTree(tree, arr, index, s, e, A, B)
{
// Reached the leaf node
// of the segment tree
if (s == e)
{
if (arr[s] >= A && arr[s] <= B)
tree[index] = 1;
else
tree[index] = 0;
return;
}
// Recursively call the buildTree
// on both the nodes of the tree
let mid = Math.floor((s + e) / 2);
buildTree(tree, arr, 2 * index,
s, mid, A, B);
buildTree(tree, arr, 2 * index + 1,
mid + 1, e, A, B);
tree[index] = tree[2 * index] +
tree[2 * index + 1];
}
// Query procedure to get the answer
// for each query l and r are query range
function query(tree, index, s, e, l, r)
{
// Out of bound or no overlap
if (r < s || l > e)
return 0;
// Complete overlap
// Query range completely lies in
// the segment tree node range
if (s >= l && e <= r)
{
return tree[index];
}
// Partially overlap
// Query range partially lies in
// the segment tree node range
let mid = Math.floor((s + e) / 2);
return (query(tree, 2 * index,
s, mid, l, r) +
query(tree, 2 * index + 1,
mid + 1, e, l, r));
}
// Driver code
let arr = [ 7, 3, 9, 13, 5, 4 ];
let n = arr.length;
let tree = new Array(4 * n + 1);
let L = 1, R = 5, A = 4, B = 7;
buildTree(tree, arr, 1, 0, n - 1, A, B);
document.write(query(tree, 1, 0, n - 1, L, R));
// This code is contributed by avanitrachhadiya2155
</script>
2
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA