Reconstructing Segment Tree

Last Updated : 09 Mar, 2023

We are given 2*N – 1 integers. We need to check whether it is possible to construct a Range Minimum Query segment tree for an array of N distinct integers from these integers. If so, we must output the segment tree array. N is given to be a power of 2.
An RMQ segment tree is a binary tree where each node is equal to the minimum value of its children. This type of tree is used to efficiently find the minimum value of elements in a given range.

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.

What we first do is iterate through the given integers counting the number of occurrences of each number, then sorting them by value. In C++, we can use the data structure map, which stores elements in sorted order.
Now we maintain a queue for each possible level of the segment tree. We put the initial root of the tree (array index 0) into the queue for the max level. We then insert the smallest element into the leftmost nodes. We then detach these nodes from the main tree. As we detach a node, we create a new tree of height h – 1, where h is the height of the current node. We can see this in figure 2. We insert the root node of this new tree into the appropriate queue based on its height.
We go through each element, getting a tree of the appropriate height based on the number of occurrences of that element. If at any point such a tree does not exist, then it is not possible to create a segment tree.

CPP

// 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;
}

Java

import java.util.*;
 
public class RMQSegmentTree {
 
    // Returns true if it is possible to construct
    // a range minimum segment tree from given array.
    public static boolean createTree(int[] arr, int N)
    {
        // Store the height of the final tree
        final int height
            = (int)(Math.log(N) / Math.log(2)) + 1;
 
        // Container to sort and store occurrences of
        // elements
        Map<Integer, Integer> multi = new HashMap<>();
 
        // Insert elements into the container
        for (int i = 0; i < 2 * N - 1; ++i)
            multi.put(arr[i],
                      multi.getOrDefault(arr[i], 0) + 1);
 
        // Used to store new subtrees created
        Set<Integer>[] Q = new HashSet[height];
        for (int i = 0; i < height; i++) {
            Q[i] = new HashSet<Integer>();
        }
 
        // Insert root into set
        Q[height - 1].add(0);
 
        // Iterate through each unique element in set
        for (Map.Entry<Integer, Integer> entry :
             multi.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();
 
            // Number of occurrences is greater than height
            // Or, no subtree exists that can accommodate it
            if (value > height || Q[value - 1].isEmpty())
                return false;
 
            // Get the appropriate subtree
            int node = Q[value - 1].iterator().next();
 
            // Delete the subtree we grabbed
            Q[value - 1].remove(node);
 
            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[value - level - 1].add(2 * i + 2);
 
                // Insert element into array at position
                arr[i] = key;
            }
        }
        return true;
    }
 
    // Driver program
    public static void main(String[] args)
    {
        int N = 8;
        int[] arr = { 1, 1, 1, 1, 2, 2, 3, 3,
                      3, 4, 4, 5, 6, 7, 8 };
 
        if (createTree(arr, N)) {
            System.out.println("YES");
            for (int i = 0; i < 2 * N - 1; ++i)
                System.out.print(arr[i] + " ");
        }
        else {
            System.out.println("NO");
        }
    }
}

Python3

# 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

C#

// C# Program to Create RMQ Segment Tree
using System;
using System.Collections.Generic;
 
public class RMQSegmentTree {
     
    // Returns true if it is possible to construct
    // a range minimum segment tree from given array.
    static bool CreateTree(int[] arr, int N)
    {
        // Store the height of the final tree
        int height = (int)(Math.Log(N) / Math.Log(2)) + 1;
 
        // Container to sort and store occurrences of
        // elements
        Dictionary<int, int> multi
            = new Dictionary<int, int>();
 
        // Insert elements into the container
        for (int i = 0; i < 2 * N - 1; ++i)
            if (multi.ContainsKey(arr[i]))
                multi[arr[i]]++;
            else
                multi[arr[i]] = 1;
 
        // Used to store new subtrees created
        SortedSet<int>[] Q = new SortedSet<int>[ height ];
 
        // Initialize each set in the array
        for (int i = 0; i < height; i++)
            Q[i] = new SortedSet<int>();
 
        // Insert root into set
        Q[height - 1].Add(0);
 
        // Iterate through each unique element in set
        foreach(KeyValuePair<int, int> entry in multi)
        {
            int count = entry.Value;
            int key = entry.Key;
 
            // Number of occurrences is greater than height
            // Or, no subtree exists that can accommodate it
            if (count > height || Q[count - 1].Count == 0)
                return false;
 
            // Get the appropriate subtree
            int node = Q[count - 1].Min;
 
            // Delete the subtree we grabbed
            Q[count - 1].Remove(node);
 
            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[count - level - 1].Add(2 * i + 2);
 
                // Insert element into array at position
                arr[i] = key;
            }
        }
        return true;
    }
 
    // Driver program
    static public void Main()
    {
        int N = 8;
        int[] arr = { 1, 1, 1, 1, 2, 2, 3, 3,
                      3, 4, 4, 5, 6, 7, 8 };
 
        if (CreateTree(arr, N)) {
            Console.WriteLine("YES");
            for (int i = 0; i < 2 * N - 1; ++i)
                Console.Write(arr[i] + " ");
        }
        else
            Console.WriteLine("NO");
 
        Console.ReadLine();
    }
}
// This code is contributed by prasad264

Javascript

// JavaScript Program to Create RMQ Segment Tree
 
// Returns true if it is possible to construct
// a range minimum segment tree from given array.
function createTree(arr, N) {
 
// Store the height of the final tree
const height = Math.floor(Math.log2(N)) + 1;
 
// Container to sort and store occurrences of elements
const multi = {};
 
// Insert elements into the container
for (let i = 0; i < 2 * N - 1; i++) {
if (multi[arr[i]] == undefined) {
multi[arr[i]] = 0;
}
multi[arr[i]] += 1;
}
 
// Used to store new subtrees created
const Q = new Array(height);
for (let i = 0; i < height; i++) {
Q[i] = new Set();
}
 
// Insert root into set
Q[height - 1].add(0);
 
// Iterate through each unique element in set
for (const [k, v] of Object.entries(multi)) {// Number of occurrences is greater than height
// Or, no subtree exists that can accommodate it
if (v > height || Q[v - 1].size == 0) {
  return false;
}
 
// Get the appropriate subtree
const node = Math.min(...Q[v - 1]);
 
// Delete the subtree we grabbed
Q[v - 1].delete(node);
let level = 1;
let 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
const N = 8;
const arr = [1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 6, 7, 8];
if (createTree(arr, N)) {
console.log("YES");
let ans="";
for (let i = 0; i < 2 * N - 1; i++) {
ans = ans + arr[i] + " ";
}
console.log(ans);
} else {
console.log("No");
}

Output:

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

Main time complexity is caused by sorting elements.
Time Complexity: O(N log N)
Space Complexity: O(N)

Lazy Propagation

Range Queries

Problems on Segement Tree

Reconstructing Segment Tree

CPP

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?