Reconstrucción del árbol de segmentos

Nos dan 2*N – 1 enteros. Necesitamos verificar si es posible construir un árbol de segmentos de consulta de rango mínimo para una array de N enteros distintos a partir de estos enteros. Si es así, debemos generar la array de árbol de segmentos. N se da como una potencia de 2.
Un árbol de segmentos RMQ es un árbol binario donde cada Node es igual al valor mínimo de sus hijos. Este tipo de árbol se usa para encontrar de manera eficiente el valor mínimo de los elementos en un rango dado.
 

Input  : 1 1 1 1 2 2 3 3 3 4 4 5 6 7 8
Output : 1 1 3 1 2 3 4 1 5 2 6 3 7 4 8
The segment tree is shown below



Input  : -381 -460 -381 95 -460 855 -242
          405 -460 982 -381 -460 95 981 855
Output : -460 -460 -381 -460 95 -381 855
         -460 -242 95 405 -381 981 855 982 
By constructing a segment tree from the output,
we can see that it a valid tree for RMQ and the
leaves are all distinct integers.

Lo primero que hacemos es iterar a través de los enteros dados contando el número de ocurrencias de cada número, luego ordenándolos por valor. En C++, podemos usar el mapa de estructura de datos, que almacena elementos ordenados. 
Ahora mantenemos una cola para cada nivel posible del árbol de segmentos. Ponemos la raíz inicial del árbol (índice de array 0) en la cola para el nivel máximo. Luego insertamos el elemento más pequeño en los Nodes más a la izquierda. Luego separamos estos Nodes del árbol principal. A medida que separamos un Node, creamos un nuevo árbol de altura h – 1, donde h es la altura del Node actual. Podemos ver esto en la figura 2. Insertamos el Node raíz de este nuevo árbol en la cola adecuada en función de su altura.
Pasamos por cada elemento, obteniendo un árbol de la altura adecuada según el número de ocurrencias de ese elemento. Si en algún momento dicho árbol no existe, entonces no es posible crear un árbol de segmentos. 
 

// C++ Program to Create RMQ Segment Tree
#include <bits/stdc++.h>
using namespace std;
  
// Returns true if it is possible to construct
// a range minimum segment tree from given array.
bool createTree(int arr[], int N)
{
    // Store the height of the final tree
    const int height = log2(N) + 1;
  
    // Container to sort and store occurrences of elements
    map<int, int> multi;
  
    // Insert elements into the container
    for (int i = 0; i < 2 * N - 1; ++i)
        ++multi[arr[i]];
  
    // Used to store new subtrees created
    set<int> Q[height];
  
    // Insert root into set
    Q[height - 1].emplace(0);
  
    // Iterate through each unique element in set
    for (map<int, int>::iterator it = multi.begin();
        it != multi.end(); ++it)
    {
        // Number of occurrences is greater than height
        // Or, no subtree exists that can accommodate it
        if (it->second > height || Q[it->second - 1].empty())
            return false;
  
        // Get the appropriate subtree
        int node = *Q[it->second - 1].begin();
  
        // Delete the subtree we grabbed
        Q[it->second - 1].erase(Q[it->second - 1].begin());
  
        int level = 1;
        for (int i = node; i < 2 * N - 1;
            i = 2 * i + 1, ++level)
        {
            // Insert new subtree created into root
            if (2 * i + 2 < 2 * N - 1)
                Q[it->second - level - 1].emplace(2 * i + 2);
  
            // Insert element into array at position
            arr[i] = it->first;
        }
    }
    return true;
}
  
// Driver program
int main()
{
    int N = 8;
    int arr[2 * N - 1] = {1, 1, 1, 1, 2, 2,
                 3, 3, 3, 4, 4, 5, 6, 7, 8};
    if (createTree(arr, N))
    {
        cout << "YES\n";
        for (int i = 0; i < 2 * N - 1; ++i)
            cout << arr[i] << " ";
    }
    else
        cout << "NO\n";
    return 0;
}

# Python Program to Create RMQ Segment Tree
from typing import List
from math import log2
  
# Returns true if it is possible to construct
# a range minimum segment tree from given array.
def createTree(arr: List[int], N: int) -> bool:
  
    # Store the height of the final tree
    height = int(log2(N)) + 1
  
    # Container to sort and store occurrences of elements
    multi = {}
  
    # Insert elements into the container
    for i in range(2 * N - 1):
        if arr[i] not in multi:
            multi[arr[i]] = 0
        multi[arr[i]] += 1
  
    # Used to store new subtrees created
    Q = [set() for _ in range(height)]
  
    # Insert root into set
    Q[height - 1].add(0)
  
    # Iterate through each unique element in set
    for k, v in multi.items():
  
        # Number of occurrences is greater than height
        # Or, no subtree exists that can accommodate it
        if (v > height or len(Q[v - 1]) == 0):
            return False
  
        # Get the appropriate subtree
        node = sorted(Q[v - 1])[0]
  
        # Delete the subtree we grabbed
        Q[v - 1].remove(sorted(Q[v - 1])[0])
        level = 1
          
        # for (int i = node; i < 2 * N - 1;
        #     i = 2 * i + 1, ++level)
        i = node
        while i < 2 * N - 1:
  
            # Insert new subtree created into root
            if (2 * i + 2 < 2 * N - 1):
                Q[v - level - 1].add(2 * i + 2)
  
            # Insert element into array at position
            arr[i] = k
            level += 1
            i = 2 * i + 1
    return True
  
  
# Driver program
if __name__ == "__main__":
  
    N = 8
    arr = [1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 6, 7, 8]
    if (createTree(arr, N)):
  
        print("YES")
        # for (int i = 0; i < 2 * N - 1; ++i)
        for i in range(2 * N - 1):
            print(arr[i], end=" ")
  
    else:
        print("No")
  
# This code is contributed by sanjeev2552

Producción: 
 

YES
1 1 3 1 2 3 4 1 5 2 6 3 7 4 8 

La complejidad del tiempo principal es causada por la clasificación de elementos. 
Complejidad de tiempo: O(N log N) 
Complejidad de espacio: O(N)

Tema relacionado: Árbol de segmentos

Este artículo es una contribución de Aditya Kamath . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu 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.