Recuento de números distintos en una array en un rango para consultas en línea utilizando el árbol de ordenación de combinación

Dada una array arr[] de tamaño N y Q consultas de la forma [L, R], la tarea es encontrar el número de valores distintos en esta array en el rango dado. Ejemplos:

Entrada: arr[] = {4, 1, 9, 1, 3, 3}, Q = {{1, 3}, {1, 5}} Salida: 3 4 Explicación: Para consulta {1, 3}, elementos son {4, 1, 9}. Por lo tanto, cuenta de elementos distintos = 3 Para la consulta {1, 5}, los elementos son {4, 1, 9, 1, 3}. Por lo tanto, cuenta de elementos distintos = 4 Entrada: arr[] = {4, 2, 1, 1, 4}, Q = {{2, 4}, {3, 5}} Salida: 3 2

Enfoque ingenuo: una solución simple es que para cada consulta, itere la array de L a R e inserte elementos en un conjunto. Finalmente, el Tamaño del conjunto da el número de elementos distintos de L a R. Complejidad de tiempo: O(Q * N) Enfoque eficiente: La idea es usar Merge Sort Tree para resolver este problema.

  1. Almacenaremos la próxima aparición del elemento en una array temporal.
  2. Luego, para cada consulta de L a R, encontraremos la cantidad de elementos en la array temporal cuyos valores son mayores que R en el rango de L a R.

Paso 1: tome una array next_right, donde next_right[i] contiene el siguiente índice derecho del número i en la array a. Inicialice esta array como N (longitud de la array). Paso 2: Cree un árbol de clasificación de combinación a partir de la array next_right y realice consultas. Las consultas para calcular el número de elementos distintos de L a R equivalen a encontrar el número de elementos de L a R que son mayores que R.

Construcción de Merge Sort Tree a partir de una array dada

  • Empezamos con un segmento arr[0 . . . n-1].
  • Cada vez que dividimos el segmento actual en dos mitades si aún no se ha convertido en un segmento de longitud 1. Luego llamamos al mismo procedimiento en ambas mitades, y para cada uno de esos segmentos, almacenamos la array ordenada en cada segmento como en la ordenación por fusión.
  • Además, el árbol será un árbol binario completo porque siempre dividimos los segmentos en dos mitades en cada nivel.
  • Dado que el árbol construido siempre es un árbol binario completo con n hojas, habrá N-1 Nodes internos. Entonces, el número total de Nodes será 2*N – 1.

Aquí hay un ejemplo. Digamos que 1 5 2 6 9 4 7 1 sea una array.

|1 1 2 4 5 6 7 9|
|1 2 5 6|1 4 7 9|
|1 5|2 6|4 9|1 7|
|1|5|2|6|9|4|7|1|

Construcción de la array next_right

  • Almacenamos la siguiente ocurrencia correcta de cada elemento.
  • Si el elemento tiene la última aparición, almacenamos ‘N’ (Longitud de la array) Ejemplo:
arr = [2, 3, 2, 3, 5, 6];
next_right = [2, 3, 6, 6, 6, 6]

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

C++

// C++ implementation to find
// count of distinct elements
// in a range L to R for Q queries
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to merge the right
// and the left tree
void merge(vector<int> tree[],
                 int treeNode)
{
    int len1 =
      tree[2 * treeNode].size();
    int len2 =
      tree[2 * treeNode + 1].size();
    int index1 = 0, index2 = 0;
 
    // Fill this array in such a
    // way such that values
    // remain sorted similar to mergesort
    while (index1 < len1 && index2 < len2) {
 
        // If the element on the left part
        // is greater than the right part
        if (tree[2 * treeNode][index1] >
              tree[2 * treeNode + 1][index2]) {
 
            tree[treeNode].push_back(
                tree[2 * treeNode + 1][index2]
                );
            index2++;
        }
        else {
            tree[treeNode].push_back(
                tree[2 * treeNode][index1]
                );
            index1++;
        }
    }
 
    // Insert the leftover elements
    // from the left part
    while (index1 < len1) {
        tree[treeNode].push_back(
            tree[2 * treeNode][index1]
            );
        index1++;
    }
 
    // Insert the leftover elements
    // from the right part
    while (index2 < len2) {
        tree[treeNode].push_back(
            tree[2 * treeNode + 1][index2]
            );
        index2++;
    }
    return;
}
 
// Recursive function to build
// segment tree by merging the
// sorted segments in sorted way
void build(vector<int> tree[],
    int* arr, int start, int end,
                  int treeNode)
{
    // Base case
    if (start == end) {
        tree[treeNode].push_back(
            arr[start]);
        return;
    }
    int mid = (start + end) / 2;
 
    // Building the left tree
    build(tree, arr, start,
          mid, 2 * treeNode);
 
    // Building the right tree
    build(tree, arr, mid + 1, end,
                 2 * treeNode + 1);
 
    // Merges the right tree
    // and left tree
    merge(tree, treeNode);
    return;
}
 
// Function similar to query() method
// as in segment tree
int query(vector<int> tree[],
     int treeNode, int start, int end,
            int left, int right)
{
 
    // Current segment is out of the range
    if (start > right || end < left) {
        return 0;
    }
    // Current segment completely
    // lies inside the range
    if (start >= left && end <= right) {
 
        // as the elements are in sorted order
        // so number of elements greater than R
        // can be find using binary
        // search or upper_bound
        return tree[treeNode].end() -
          upper_bound(tree[treeNode].begin(),
            tree[treeNode].end(), right);
    }
 
    int mid = (start + end) / 2;
 
    // Query on the left tree
    int op1 = query(tree, 2 * treeNode,
              start, mid, left, right);
    // Query on the Right tree
    int op2 = query(tree, 2 * treeNode + 1,
            mid + 1, end, left, right);
    return op1 + op2;
}
 
// Driver Code
int main()
{
 
    int n = 5;
    int arr[] = { 1, 2, 1, 4, 2 };
 
    int next_right[n];
    // Initialising the tree
    vector<int> tree[4 * n];
 
    unordered_map<int, int> ump;
 
    // Construction of next_right
    // array to store the
    // next index of occurrence
    // of elements
    for (int i = n - 1; i >= 0; i--) {
        if (ump[arr[i]] == 0) {
            next_right[i] = n;
            ump[arr[i]] = i;
        }
        else {
            next_right[i] = ump[arr[i]];
            ump[arr[i]] = i;
        }
    }
    // building the mergesort tree
    // by using next_right array
    build(tree, next_right, 0, n - 1, 1);
 
    int ans;
    // Queries one based indexing
    // Time complexity of each
    // query is log(N)
 
    // first query
    int left1 = 0;
    int right1 = 2;
    ans = query(tree, 1, 0, n - 1,
                  left1, right1);
    cout << ans << endl;
 
    // Second Query
    int left2 = 1;
    int right2 = 4;
    ans = query(tree, 1, 0, n - 1,
                  left2, right2);
    cout << ans << endl;
}
Producción:

2
3

Complejidad del tiempo: O(Q*log N)

Publicación traducida automáticamente

Artículo escrito por piyushbhutani y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *