Рубрики

Сегментное дерево | Set 2 (Range Minimum Query)

Мы представили дерево сегментов с простым примером в предыдущем посте. В этом посте проблема Range Minimum Query обсуждается как еще один пример, где можно использовать дерево сегментов. Ниже приводится постановка проблемы.

У нас есть массив arr [0. , , н-1]. Мы должны быть в состоянии эффективно найти минимальное значение от индекса qs (начало запроса) до qe (конец запроса), где 0 <= qs <= qe <= n-1 .

Простое решение — запустить цикл от qs до qe и найти минимальный элемент в заданном диапазоне. Это решение занимает O (n) время в худшем случае.

Другое решение заключается в создании двумерного массива, в котором запись [i, j] хранит минимальное значение в диапазоне arr [i..j]. Минимум заданного диапазона теперь можно рассчитать за время O (1), но предварительная обработка занимает время O (n ^ 2). Кроме того, этот подход требует O (n ^ 2) дополнительного пространства, которое может стать огромным для больших входных массивов.

Сегментное дерево может использоваться для предварительной обработки и запроса в умеренное время. Для дерева сегментов время предварительной обработки равно O (n), а время для минимального диапазона запроса равно O (Logn). Требуется дополнительное пространство O (n) для хранения дерева сегментов.

Представление Сегментных деревьев
1. Конечные узлы являются элементами входного массива.
2. Каждый внутренний узел представляет минимум всех листьев под ним.

Представление массива дерева используется для представления деревьев сегментов. Для каждого узла по индексу i левый потомок имеет индекс 2 * i + 1, правый потомок — 2 * i + 2, а родительский — ,

Построение дерева сегментов из заданного массива
Начнем с сегмента arr [0. , , н-1]. и каждый раз, когда мы делим текущий сегмент на две половины (если он еще не стал сегментом длины 1), а затем вызываем одну и ту же процедуру для обеих половин, и для каждого такого сегмента мы сохраняем минимальное значение в дереве сегментов. узел.
Все уровни построенного дерева сегментов будут полностью заполнены, кроме последнего уровня. Кроме того, дерево будет полным двоичным деревом, потому что мы всегда делим сегменты на две половины на каждом уровне. Поскольку построенное дерево всегда является полным двоичным деревом с n листьями, будет иметься n-1 внутренних узлов. Таким образом, общее количество узлов будет 2 * n — 1.
Высота сегмента дерева будет , Поскольку дерево представлено с использованием массива, и необходимо поддерживать связь между родительскими и дочерними индексами, объем памяти, выделенной для дерева сегментов, будет ,

Запрос минимального значения заданного диапазона
Как только дерево построено, как сделать минимальный диапазон запроса, используя построенное дерево сегментов. Ниже приводится алгоритм, чтобы получить минимум.

// qs --> query start index, qe --> query end index
int RMQ(node, qs, qe) 
{
   if range of node is within qs and qe
        return value in node
   else if range of node is completely outside qs and qe
        return INFINITE
   else
    return min( RMQ(node's left child, qs, qe), RMQ(node's right child, qs, qe) )
}

Реализация:

C ++

// C ++ программа для минимального диапазона
// запрос с использованием дерева сегментов
#include <bits/stdc++.h>

using namespace std;

  
// Полезная функция для получения минимум двух чисел

int minVal(int x, int y) { return (x < y)? x: y; } 

  
// Полезная функция для получения
// средний индекс из угловых индексов.

int getMid(int s, int e) { return s + (e -s)/2; } 

  
/ * Рекурсивная функция для получения
минимальное значение в заданном диапазоне
индексов массива. Следующее
параметры для этой функции

  

    st -> Указатель на дерево сегментов

    index -> Индекс текущего узла в

           сегментное дерево. Изначально 0

           передается от имени root всегда с индексом 0

    ss & se -> Начальный и конечный индексы

                представленного сегмента

                текущим узлом, т. е. st [index]

    qs & qe -> начальные и конечные индексы диапазона запросов * /

int RMQUtil(int *st, int ss, int se, int qs, int qe, int index) 

    // Если сегмент этого узла является частью

    // заданного диапазона, затем возврат

    // мин отрезка

    if (qs <= ss && qe >= se) 

        return st[index]; 

  

    // Если сегмент этого узла

    // находится вне заданного диапазона

    if (se < qs || ss > qe) 

        return INT_MAX; 

  

    // Если часть этого сегмента

    // перекрывается с заданным диапазоном

    int mid = getMid(ss, se); 

    return minVal(RMQUtil(st, ss, mid, qs, qe, 2*index+1), 

                RMQUtil(st, mid+1, se, qs, qe, 2*index+2)); 

  
// Возвращаем минимум элементов в диапазоне
// из индекса qs (начало запроса) в
// qe (конец запроса). В основном использует RMQUtil ()

int RMQ(int *st, int n, int qs, int qe) 

    // Проверяем ошибочные входные значения

    if (qs < 0 || qe > n-1 || qs > qe) 

    

        cout<<"Invalid Input"

        return -1; 

    

  

    return RMQUtil(st, 0, n-1, qs, qe, 0); 

  
// Рекурсивная функция, которая создает
// Сегментное дерево для массива [ss..se].
// si - индекс текущего узла в сегментном дереве st

int constructSTUtil(int arr[], int ss, int se,

                                int *st, int si) 

    // Если в массиве есть один элемент,

    // сохранить его в текущем узле

    // сегментируем дерево и возвращаем

    if (ss == se) 

    

        st[si] = arr[ss]; 

        return arr[ss]; 

    

  

    // Если есть более одного элемента,

    // затем повторяем для левого и правого поддеревьев

    // и сохранить минимум двух значений в этом узле

    int mid = getMid(ss, se); 

    st[si] = minVal(constructSTUtil(arr, ss, mid, st, si*2+1), 

                    constructSTUtil(arr, mid+1, se, st, si*2+2)); 

    return st[si]; 

  
/ * Функция для построения дерева сегментов
из данного массива. Эта функция выделяет
память для дерева сегментов и вызовов constructSTUtil () для
заполнить выделенную память * /

int *constructST(int arr[], int n) 

    // Выделить память для дерева сегментов

  

    // Высота сегмента дерева

    int x = (int)(ceil(log2(n))); 

  

    // Максимальный размер дерева сегментов

    int max_size = 2*(int)pow(2, x) - 1; 

  

    int *st = new int[max_size]; 

  

    // Заполняем выделенную память st

    constructSTUtil(arr, 0, n-1, st, 0); 

  

    // Возвращаем построенное дерево сегментов

    return st; 

  
// Программа драйвера для проверки вышеуказанных функций

int main() 

    int arr[] = {1, 3, 2, 7, 9, 11}; 

    int n = sizeof(arr)/sizeof(arr[0]); 

  

    // Построить дерево сегментов из заданного массива

    int *st = constructST(arr, n); 

  

    int qs = 1; // Начальный индекс диапазона запроса

    int qe = 5; // Конечный индекс диапазона запроса

  

    // Вывести минимальное значение в arr [qs..qe]

    cout<<"Minimum of values in range ["<<qs<<", "<<qe<<"] "<<

    "is = "<<RMQ(st, n, qs, qe)<<endl; 

  

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// C программа для запроса минимального диапазона с использованием дерева сегментов
#include <stdio.h>
#include <math.h>
#include <limits.h>

  
// Полезная функция для получения минимум двух чисел

int minVal(int x, int y) { return (x < y)? x: y; }

  
// Полезная функция для получения среднего индекса из угловых индексов.

int getMid(int s, int e) {  return s + (e -s)/2;  }

  
/ * Рекурсивная функция для получения минимального значения в заданном диапазоне

     индексов массива. Ниже приведены параметры для этой функции.

  

    st -> Указатель на дерево сегментов

    index -> Индекс текущего узла в дереве сегментов. Первоначально

              0 передается как root всегда с индексом 0

    ss & se -> Начальный и конечный индексы представленного сегмента

                  текущим узлом, т. е. st [index]

    qs & qe -> начальные и конечные индексы диапазона запросов * /

int RMQUtil(int *st, int ss, int se, int qs, int qe, int index)

{

    // Если сегмент этого узла является частью заданного диапазона, возвращаем

    // мин отрезка

    if (qs <= ss && qe >= se)

        return st[index];

  

    // Если сегмент этого узла находится за пределами указанного диапазона

    if (se < qs || ss > qe)

        return INT_MAX;

  

    // Если часть этого сегмента перекрывается с заданным диапазоном

    int mid = getMid(ss, se);

    return minVal(RMQUtil(st, ss, mid, qs, qe, 2*index+1),

                  RMQUtil(st, mid+1, se, qs, qe, 2*index+2));

}

  
// Возвращаем минимум элементов в диапазоне от индекса qs (начало запроса) до
// qe (конец запроса). В основном использует RMQUtil ()

int RMQ(int *st, int n, int qs, int qe)

{

    // Проверяем ошибочные входные значения

    if (qs < 0 || qe > n-1 || qs > qe)

    {

        printf("Invalid Input");

        return -1;

    }

  

    return RMQUtil(st, 0, n-1, qs, qe, 0);

}

  
// Рекурсивная функция, которая создает дерево сегментов для массива [ss..se].
// si - индекс текущего узла в сегментном дереве st

int constructSTUtil(int arr[], int ss, int se, int *st, int si)

{

    // Если в массиве есть один элемент, сохраняем его в текущем узле

    // сегментируем дерево и возвращаем

    if (ss == se)

    {

        st[si] = arr[ss];

        return arr[ss];

    }

  

    // Если есть более одного элемента, то повторить для левого и

    // правильные поддеревья и храним минимум двух значений в этом узле

    int mid = getMid(ss, se);

    st[si] =  minVal(constructSTUtil(arr, ss, mid, st, si*2+1),

                     constructSTUtil(arr, mid+1, se, st, si*2+2));

    return st[si];

}

  
/ * Функция для построения дерева сегментов из заданного массива. Эта функция

   выделяет память для дерева сегментов и вызывает constructSTUtil () для

   заполнить выделенную память * /

int *constructST(int arr[], int n)

{

    // Выделить память для дерева сегментов

  

    // Высота сегмента дерева

    int x = (int)(ceil(log2(n))); 

  

    // Максимальный размер дерева сегментов

    int max_size = 2*(int)pow(2, x) - 1; 

  

    int *st = new int[max_size]; 

  

    // Заполняем выделенную память st

    constructSTUtil(arr, 0, n-1, st, 0);

  

    // Возвращаем построенное дерево сегментов

    return st;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr[] = {1, 3, 2, 7, 9, 11};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    // Построить дерево сегментов из заданного массива

    int *st = constructST(arr, n);

  

    int qs = 1;  // Начальный индекс диапазона запроса

    int qe = 5;  // Конечный индекс диапазона запроса

  

    // Вывести минимальное значение в arr [qs..qe]

    printf("Minimum of values in range [%d, %d] is = %d\n",

                           qs, qe, RMQ(st, n, qs, qe));

  

    return 0;

}

Джава

// Программа для запроса минимального диапазона с использованием дерева сегментов

class SegmentTreeRMQ

{

    int st[]; // массив для хранения дерева сегментов

  

    // Полезная функция для получения минимум двух чисел

    int minVal(int x, int y) {

        return (x < y) ? x : y;

    }

  

    // Полезная функция для получения среднего индекса из угла

    // индексы.

    int getMid(int s, int e) {

        return s + (e - s) / 2;

    }

  

    / * Рекурсивная функция для получения минимального значения в данном

        диапазон индексов массива. Ниже приведены параметры для

        эта функция.

  

        st -> Указатель на дерево сегментов

        index -> Индекс текущего узла в дереве сегментов. Первоначально

                   0 передается как root всегда с индексом 0

        ss & se -> Начальный и конечный индексы сегмента

                     представлен текущим узлом, т. е. st [index]

        qs & qe -> начальные и конечные индексы диапазона запросов * /

    int RMQUtil(int ss, int se, int qs, int qe, int index)

    {

        // Если сегмент этого узла является частью заданного диапазона, то

        // возвращаем минимум сегмента

        if (qs <= ss && qe >= se)

            return st[index];

  

        // Если сегмент этого узла находится за пределами указанного диапазона

        if (se < qs || ss > qe)

            return Integer.MAX_VALUE;

  

        // Если часть этого сегмента перекрывается с заданным диапазоном

        int mid = getMid(ss, se);

        return minVal(RMQUtil(ss, mid, qs, qe, 2 * index + 1),

                RMQUtil(mid + 1, se, qs, qe, 2 * index + 2));

    }

  

    // Возвращаем минимум элементов в диапазоне из индекса qs (запрос

    // начало) до qe (конец запроса). В основном использует RMQUtil ()

    int RMQ(int n, int qs, int qe)

    {

        // Проверяем ошибочные входные значения

        if (qs < 0 || qe > n - 1 || qs > qe) {

            System.out.println("Invalid Input");

            return -1;

        }

  

        return RMQUtil(0, n - 1, qs, qe, 0);

    }

  

    // Рекурсивная функция, которая создает дерево сегментов для

    // массив [ss..se]. si - индекс текущего узла в сегментном дереве st.

    int constructSTUtil(int arr[], int ss, int se, int si)

    {

        // Если в массиве есть один элемент, сохраняем его в текущем

        // узел дерева сегментов и возврат

        if (ss == se) {

            st[si] = arr[ss];

            return arr[ss];

        }

  

        // Если есть более одного элемента, то повторить для левого и

        // правильные поддеревья и храним минимум двух значений в этом узле

        int mid = getMid(ss, se);

        st[si] = minVal(constructSTUtil(arr, ss, mid, si * 2 + 1),

                constructSTUtil(arr, mid + 1, se, si * 2 + 2));

        return st[si];

    }

  

    / * Функция для построения дерева сегментов из заданного массива. Эта функция

       выделяет память для дерева сегментов и вызывает constructSTUtil () для

       заполнить выделенную память * /

    void constructST(int arr[], int n)

    {

        // Выделить память для дерева сегментов

  

        // Высота сегмента дерева

        int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));

  

        // Максимальный размер дерева сегментов

        int max_size = 2 * (int) Math.pow(2, x) - 1;

        st = new int[max_size]; // выделяем память

  

        // Заполняем выделенную память st

        constructSTUtil(arr, 0, n - 1, 0);

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[]) 

    {

        int arr[] = {1, 3, 2, 7, 9, 11};

        int n = arr.length;

        SegmentTreeRMQ tree = new SegmentTreeRMQ();

  

        // Построить дерево сегментов из заданного массива

        tree.constructST(arr, n);

  

        int qs = 1// Начальный индекс диапазона запроса

        int qe = 5// Конечный индекс диапазона запроса

  

        // Вывести минимальное значение в arr [qs..qe]

        System.out.println("Minimum of values in range [" + qs + ", "

                           + qe + "] is = " + tree.RMQ(n, qs, qe));

    }

}
// Этот код предоставлен Ankur Narain Verma

python3

# Python3 программа для минимального диапазона
# запрос с использованием дерева сегментов

import sys;

from math import ceil,log2;

  

INT_MAX = sys.maxsize;

  
# Полезная функция для получения
# минимум двух чисел

def minVal(x, y) :

    return x if (x < y) else y; 

  
# Полезная функция для получения
# средний индекс из угловых индексов.

def getMid(s, e) :

    return s + (e - s) // 2

  
"" "Рекурсивная функция для получения
минимальное значение в заданном диапазоне
индексов массива. Следующее
параметры для этой функции

  

    st -> Указатель на дерево сегментов

    index -> Индекс текущего узла в

        сегментное дерево. Изначально 0

        передается от имени root всегда с индексом 0

    ss & se -> Начальный и конечный индексы

                представленного сегмента

                текущим узлом, т. е. st [index]

    qs & qe -> Начальные и конечные индексы диапазона запросов "" "

def RMQUtil( st, ss, se, qs, qe, index) :

  

    # Если сегмент этого узла является частью

    # заданного диапазона, затем вернуть

    # мин сегмента

    if (qs <= ss and qe >= se) :

        return st[index]; 

  

    # Если сегмент этого узла

    # находится вне заданного диапазона

    if (se < qs or ss > qe) :

        return INT_MAX; 

  

    # Если часть этого сегмента

    # перекрывается с заданным диапазоном

    mid = getMid(ss, se); 

    return minVal(RMQUtil(st, ss, mid, qs, 

                          qe, 2 * index + 1), 

                  RMQUtil(st, mid + 1, se,

                          qs, qe, 2 * index + 2)); 

  
# Вернуть минимум элементов в диапазоне
# от индекса qs (начало запроса) до
# qe (конец запроса). В основном использует RMQUtil ()

def RMQ( st, n, qs, qe) : 

  

    # Проверьте ошибочные входные значения

    if (qs < 0 or qe > n - 1 or qs > qe) :

      

        print("Invalid Input"); 

        return -1

      

    return RMQUtil(st, 0, n - 1, qs, qe, 0); 

  
# Рекурсивная функция, которая создает
# Сегментное дерево для массива [ss..se].
# si - индекс текущего узла в дереве сегментов st

def constructSTUtil(arr, ss, se, st, si) :

  

    # Если в массиве есть один элемент,

    # сохранить его в текущем узле

    # сегмент дерева и возврат

    if (ss == se) :

  

        st[si] = arr[ss]; 

        return arr[ss]; 

  

    # Если есть более одного элемента,

    # затем повторить для левого и правого поддеревья

    # и сохранить минимум двух значений в этом узле

    mid = getMid(ss, se); 

    st[si] = minVal(constructSTUtil(arr, ss, mid,

                                    st, si * 2 + 1),

                    constructSTUtil(arr, mid + 1, se,

                                    st, si * 2 + 2)); 

      

    return st[si]; 

  
"" "Функция для построения дерева сегментов
из данного массива. Эта функция выделяет
память для дерева сегментов и вызовов constructSTUtil ()
заполнить выделенную память "" "

def constructST( arr, n) :

  

    # Выделить память для дерева сегментов

  

    # Высота сегмента дерева

    x = (int)(ceil(log2(n))); 

  

    # Максимальный размер дерева сегментов

    max_size = 2 * (int)(2**x) - 1

   

    st = [0] * (max_size); 

  

    # Заполнить выделенную память st

    constructSTUtil(arr, 0, n - 1, st, 0); 

  

    # Вернуть построенное дерево сегментов

    return st; 

  
Код водителя

if __name__ == "__main__"

  

    arr = [1, 3, 2, 7, 9, 11]; 

    n = len(arr); 

  

    # Построить дерево сегментов из заданного массива

    st = constructST(arr, n); 

  

    qs = 1; # Начальный индекс диапазона запроса

    qe = 5; # Конечный индекс диапазона запроса

  

    # Вывести минимальное значение в arr [qs..qe]

    print("Minimum of values in range [", qs, 

          ",", qe, "]", "is =", RMQ(st, n, qs, qe)); 

  
# Этот код предоставлен AnkitRai01

C #

// C # Программа для минимального диапазона
// запрос с использованием дерева сегментов

using System;

      

public class SegmentTreeRMQ

{

    int []st; // массив для хранения дерева сегментов

  

    // Функция полезности для

    // получить минимум два числа

    int minVal(int x, int y) 

    {

        return (x < y) ? x : y;

    }

  

    // Полезная функция для получения

    // средний индекс из угловых индексов.

    int getMid(int s, int e) 

    {

        return s + (e - s) / 2;

    }

  

    / * Рекурсивная функция для получения

        минимальное значение в данном

        диапазон индексов массива.

        Ниже приведены параметры для

        эта функция.

  

        st -> Указатель на дерево сегментов

        index -> Индекс текущего узла в

        сегментное дерево. Изначально 0 пройдено

        как корень всегда в индексе 0

        ss & se -> Начальный и конечный индексы сегмента

                    представлен текущим узлом, т. е. st [index]

        qs & qe -> начальные и конечные индексы диапазона запросов * /

    int RMQUtil(int ss, int se, int qs, int qe, int index)

    {

        // Если сегмент этого узла

        // часть заданного диапазона, затем

        // возвращаем минимум сегмента

        if (qs <= ss && qe >= se)

            return st[index];

  

        // Если сегмент этого узла

        // находится вне заданного диапазона

        if (se < qs || ss > qe)

            return int.MaxValue;

  

        // Если часть этого сегмента

        // перекрывается с заданным диапазоном

        int mid = getMid(ss, se);

        return minVal(RMQUtil(ss, mid, qs, qe, 2 * index + 1),

                RMQUtil(mid + 1, se, qs, qe, 2 * index + 2));

    }

  

    // Возвращаем минимум элементов

    // в диапазоне от индекса qs (запрос

    // начало) до qe (конец запроса).

    // Он в основном использует RMQUtil ()

    int RMQ(int n, int qs, int qe)

    {

        // Проверяем ошибочные входные значения

        if (qs < 0 || qe > n - 1 || qs > qe) 

        {

            Console.WriteLine("Invalid Input");

            return -1;

        }

  

        return RMQUtil(0, n - 1, qs, qe, 0);

    }

  

    // Рекурсивная функция, которая

    // строит дерево сегментов для

    // массив [ss..se]. си индекс

    // текущего узла в сегментном дереве st

    int constructSTUtil(int []arr, int ss, int se, int si)

    {

        // Если в массиве есть один элемент,

        // сохранить его в текущем узле

        // сегментируем дерево и возвращаем

        if (ss == se) 

        {

            st[si] = arr[ss];

            return arr[ss];

        }

  

        // Если есть более одного элемента,

        // затем повторяем для левого и правого поддеревьев

        // и сохранить минимум двух значений в этом узле

        int mid = getMid(ss, se);

        st[si] = minVal(constructSTUtil(arr, ss, mid, si * 2 + 1),

                constructSTUtil(arr, mid + 1, se, si * 2 + 2));

        return st[si];

    }

  

    / * Функция для построения сегмента

    дерево из данного массива. Эта функция

    выделяет память для дерева сегментов

    и вызывает constructSTUtil () для

    заполнить выделенную память * /

    void constructST(int []arr, int n)

    {

        // Выделить память для дерева сегментов

  

        // Высота сегмента дерева

        int x = (int) (Math.Ceiling(Math.Log(n) / Math.Log(2)));

  

        // Максимальный размер дерева сегментов

        int max_size = 2 * (int) Math.Pow(2, x) - 1;

        st = new int[max_size]; // выделяем память

  

        // Заполняем выделенную память st

        constructSTUtil(arr, 0, n - 1, 0);

    }

  

    // Код драйвера

    public static void Main() 

    {

        int []arr = {1, 3, 2, 7, 9, 11};

        int n = arr.Length;

        SegmentTreeRMQ tree = new SegmentTreeRMQ();

  

        // Построить дерево сегментов из заданного массива

        tree.constructST(arr, n);

  

        int qs = 1; // Начальный индекс диапазона запроса

        int qe = 5; // Конечный индекс диапазона запроса

  

        // Вывести минимальное значение в arr [qs..qe]

        Console.WriteLine("Minimum of values in range [" + qs + ", "

                        + qe + "] is = " + tree.RMQ(n, qs, qe));

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /


Выход:

 
Minimum of values in range [1, 5] is = 2

Сложность времени:
Сложность времени для построения дерева O (n). Всего существует 2n-1 узлов, и значение каждого узла вычисляется только один раз при построении дерева.

Временная сложность запроса составляет O (Logn). Чтобы запросить минимум диапазона, мы обрабатываем не более двух узлов на каждом уровне, и количество уровней равно O (Logn).

Пожалуйста, перейдите по следующим ссылкам, чтобы найти больше решений для определения минимальной проблемы запроса.
http://espressocode.top/range-minimum-query-for-static-array/
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Range_Minimum_Query_(RMQ)
http://wcipeg.com/wiki/Range_minimum_query

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Сегментное дерево | Set 2 (Range Minimum Query)

0.00 (0%) 0 votes