Рубрики

Сегментное дерево | Установите 2 (Range Maximum Query с обновлением узла)

Продвинутые Структуры данных

Дан массив arr [0. , , н-1]. Найти максимум элементов от индекса l до r, где 0 <= l <= r <= n-1. Кроме того, измените значение указанного элемента массива на новое значение x. Нам нужно сделать arr [i] = x, где 0 <= i <= n-1, а затем найти максимальный элемент данного диапазона с обновленными значениями.

Пример :

Input : {1, 3, 5, 7, 9, 11}
Maximum Query : L = 1, R = 3
update : set arr[1] = 8
Output : 
Max of values in given range = 7
Updated max of values in given range = 8

Простое решение — запустить цикл от l до r и вычислить максимум элементов в заданном диапазоне. Чтобы обновить значение, просто сделайте arr [i] = x. Первая операция занимает время O (n), а вторая операция занимает время O (1).

Эффективный подход. Здесь нам необходимо выполнить операции за O (Logn), чтобы мы могли использовать дерево сегментов для выполнения обеих операций за O (Logn) .

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

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

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

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

node--> node number, l --> 
query start index, r --> query end index;

int getMax(node, l, r) 
{
   if range of node is within l and r
        return value of node
   else if range of node is completely outside l and r
        return -1
   else
    return max(getMax(node's left child, l, r),
           getMax(node's right child, l, r))
}

Ниже приведена реализация вышеуказанного подхода:

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

using namespace std;

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

int getMid(int s, int e) 

{

    return s + (e - s) / 2;

}

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

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

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

    функция.

  

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

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

                сегментное дерево.

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

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

                по текущему узлу, т.е. st [node]

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

                диапазона запроса * /

int MaxUtil(int* st, int ss, int se, int l, 

            int r, int node)

{

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

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

    // максимум сегмента

    if (l <= ss && r >= se)

        return st[node];

  

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

    // принадлежат данному диапазону

    if (se < l || ss > r)

        return -1;

  

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

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

    int mid = getMid(ss, se);

      

    return max(MaxUtil(st, ss, mid, l, r, 

                       2 * node + 1),

               MaxUtil(st, mid + 1, se, l, 

                       r, 2 * node + 2));

}

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

   имеют данный индекс в своем диапазоне. Следующее

   параметры st, ss и se совпадают с заданными

   Указанный выше индекс -> индекс обновляемого элемента. * /

void updateValue(int arr[], int* st, int ss, int se, 

                 int index, int value, int node)

{

    if (index < ss || index > se) 

    {

        cout << "Invalid Input" << endl;

        return;

    }

      

    if (ss == se) 

    {   

        // обновляем значение в массиве и в дереве сегментов

        arr[index] = value;

        st[node] = value;

    }

    else {

            int mid = getMid(ss, se);

              

            if (index >= ss && index <= mid)

                updateValue(arr, st, ss, mid, index, 

                            value, 2 * node + 1);

            else

                updateValue(arr, st, mid + 1, se, 

                            index, value, 2 * node + 2);

              

            st[node] = max(st[2 * node + 1], 

                       st[2 * node + 2]);

    }

    return;

}

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

int getMax(int* st, int n, int l, int r)

{

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

    if (l < 0 || r > n - 1 || l > r) 

    {

        printf("Invalid Input");

        return -1;

    }

  

    return MaxUtil(st, 0, n - 1, l, r, 0);

}

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

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

                    int* st, int si)

{

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

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

    if (ss == se) 

    {

        st[si] = arr[ss];

        return arr[ss];

    }

  

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

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

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

    int mid = getMid(ss, se);

      

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

                                 si * 2 + 1),

                 constructSTUtil(arr, mid + 1, se, 

                                 st, si * 2 + 2));

      

    return st[si];

}

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

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

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, 5, 7, 9, 11 };

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

  

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

    int* st = constructST(arr, n);

  

    // Выводим максимум значений в массив

    // из индекса 1 в 3

    cout << "Max of values in given range = " 

         << getMax(st, n, 1, 3) << endl;

  

    // Обновление: установите arr [1] = 8 и обновите

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

    updateValue(arr, st, 0, n - 1, 1, 8, 0);

  

    // Находим макс после обновления значения

    cout << "Updated max of values in given range = " 

         << getMax(st, n, 1, 3) << endl;

      

    return 0;

}

Выход:

Max of values in given range = 7
Updated max of values in given range = 8

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

Сегментное дерево | Установите 2 (Range Maximum Query с обновлением узла)

0.00 (0%) 0 votes