Рубрики

Сегментное дерево | Набор 1 (сумма заданного диапазона)

Давайте рассмотрим следующую проблему, чтобы понять деревья сегментов.

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

2 Измените значение указанного элемента массива на новое значение x. Нам нужно сделать arr [i] = x, где 0 <= i <= n-1.

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

Другое решение состоит в том, чтобы создать другой массив и сохранить сумму от начала до i в i-м индексе в этом массиве. Сумма заданного диапазона теперь может быть рассчитана за время O (1), но операция обновления теперь занимает время O (n). Это хорошо работает, если количество операций с запросами велико и очень мало обновлений.

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

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

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

Как выглядит дерево сегментов в памяти?
Как и куча, дерево сегментов также представляется в виде массива. Разница здесь в том, что это не полное двоичное дерево. Это скорее полное двоичное дерево (каждый узел имеет 0 или 2 дочерних элемента), и все уровни заполнены, кроме, возможно, последнего уровня. В отличие от кучи, последний уровень может иметь промежутки между узлами. Ниже приведены значения в массиве дерева сегментов для приведенной выше диаграммы.

Below is memory representation of segment tree for input array {1, 3, 5, 7, 9, 11}
st[] = {36, 9, 27, 4, 5, 16, 11, 1, 3, DUMMY, DUMMY, 7, 9, DUMMY, DUMMY}

Фиктивные значения никогда не доступны и не имеют смысла. Это некоторая потеря пространства из-за простого представления массива. Мы можем оптимизировать эту потерю, используя некоторые умные реализации, но код для суммирования и обновления становится более сложным.

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

Каков общий размер массива, представляющего дерево сегментов?
Если n — степень 2, то фиктивные узлы отсутствуют. Таким образом, размер дерева сегментов составляет 2n-1 (n листовых узлов и n-1) внутренних узлов. Если n не является степенью 2, то размер дерева будет 2 * x — 1, где x — наименьшая степень 2, превышающая n. Например, когда n = 10, тогда размер массива, представляющего дерево сегментов, составляет 2 * 16-1 = 31.
Альтернативное объяснение размера основано на хейгенте. Высота сегмента дерева будет , Поскольку дерево представлено с использованием массива, и необходимо поддерживать связь между родительскими и дочерними индексами, объем памяти, выделенной для дерева сегментов, будет ,

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

int getSum(node, l, r) 
{
   if the range of the node is within l and r
        return value in the node
   else if the range of the node is completely outside l and r
        return 0
   else
    return getSum(node's left child, l, r) + 
           getSum(node's right child, l, r)
}

Обновить значение
Подобно построению дерева и операциям запроса, обновление также может быть выполнено рекурсивно. Нам дан индекс, который необходимо обновить. Пусть diff будет значением, которое будет добавлено. Мы начинаем с корня дерева сегментов и добавляем diff ко всем узлам, которые имеют индекс в своем диапазоне. Если узел не имеет заданного индекса в своем диапазоне, мы не вносим никаких изменений в этот узел.

Реализация:
Ниже приводится реализация дерева сегментов. Программа реализует построение дерева сегментов для любого заданного массива. Он также реализует операции запроса и обновления.

C ++

// C ++ программа для отображения операций с сегментным деревом, таких как конструкция, запрос
// и обновляем
#include <bits/stdc++.h>

using namespace std;

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

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

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

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

  

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

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

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

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

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

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

int getSumUtil(int *st, int ss, int se, int qs, int qe, int si) 

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

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

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

        return st[si]; 

  

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

    if (se < qs || ss > qe) 

        return 0; 

  

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

    int mid = getMid(ss, se); 

    return getSumUtil(st, ss, mid, qs, qe, 2*si+1) + 

        getSumUtil(st, mid+1, se, qs, qe, 2*si+2); 

  
/ * Рекурсивная функция для обновления узлов, которые имеют данный
Индекс в их диапазоне. Ниже приведены параметры

    st, si, ss и se такие же, как getSumUtil ()

    я -> индекс элемента, который будет обновлен. Этот индекс

            во входном массиве.

diff -> Значение, которое будет добавлено ко всем узлам с i в диапазоне * /

void updateValueUtil(int *st, int ss, int se, int i, int diff, int si) 

    // Базовый случай: если входной индекс лежит вне диапазона

    // этот сегмент

    if (i < ss || i > se) 

        return

  

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

    // значение узла и его потомков

    st[si] = st[si] + diff; 

    if (se != ss) 

    

        int mid = getMid(ss, se); 

        updateValueUtil(st, ss, mid, i, diff, 2*si + 1); 

        updateValueUtil(st, mid+1, se, i, diff, 2*si + 2); 

    

  
// Функция для обновления значения во входном массиве и сегментном дереве.
// Он использует updateValueUtil () для обновления значения в дереве сегментов

void updateValue(int arr[], int *st, int n, int i, int new_val) 

    // Проверяем ошибочный индекс ввода

    if (i < 0 || i > n-1) 

    

        cout<<"Invalid Input"

        return

    

  

    // Получить разницу между новым значением и старым значением

    int diff = new_val - arr[i]; 

  

    // Обновляем значение в массиве

    arr[i] = new_val; 

  

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

    updateValueUtil(st, 0, n-1, i, diff, 0); 

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

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

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

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

    

        cout<<"Invalid Input"

        return -1; 

    

  

    return getSumUtil(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] = 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, 5, 7, 9, 11}; 

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

  

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

    int *st = constructST(arr, n); 

  

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

    cout<<"Sum of values in given range = "<<getSum(st, n, 1, 3)<<endl; 

  

    // Обновление: установить arr [1] = 10 и обновить соответствующее

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

    updateValue(arr, st, n, 1, 10); 

  

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

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

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

    return 0; 


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

С

// C-программа для отображения операций с сегментным деревом, таких как конструкция, запрос
// и обновляем
#include <stdio.h>
#include <math.h>

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

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

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

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

  

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

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

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

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

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

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

int getSumUtil(int *st, int ss, int se, int qs, int qe, int si)

{

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

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

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

        return st[si];

  

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

    if (se < qs || ss > qe)

        return 0;

  

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

    int mid = getMid(ss, se);

    return getSumUtil(st, ss, mid, qs, qe, 2*si+1) +

           getSumUtil(st, mid+1, se, qs, qe, 2*si+2);

}

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

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

    st, si, ss и se такие же, как getSumUtil ()

    я -> индекс элемента, который будет обновлен. Этот индекс

             во входном массиве.

   diff -> Значение, которое будет добавлено ко всем узлам с i в диапазоне * /

void updateValueUtil(int *st, int ss, int se, int i, int diff, int si)

{

    // Базовый случай: если входной индекс лежит вне диапазона

    // этот сегмент

    if (i < ss || i > se)

        return;

  

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

    // значение узла и его потомков

    st[si] = st[si] + diff;

    if (se != ss)

    {

        int mid = getMid(ss, se);

        updateValueUtil(st, ss, mid, i, diff, 2*si + 1);

        updateValueUtil(st, mid+1, se, i, diff, 2*si + 2);

    }

}

  
// Функция для обновления значения во входном массиве и сегментном дереве.
// Он использует updateValueUtil () для обновления значения в дереве сегментов

void updateValue(int arr[], int *st, int n, int i, int new_val)

{

    // Проверяем ошибочный индекс ввода

    if (i < 0 || i > n-1)

    {

        printf("Invalid Input");

        return;

    }

  

    // Получить разницу между новым значением и старым значением

    int diff = new_val - arr[i];

  

    // Обновляем значение в массиве

    arr[i] = new_val;

  

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

    updateValueUtil(st, 0, n-1, i, diff, 0);

}

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

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

{

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

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

    {

        printf("Invalid Input");

        return -1;

    }

  

    return getSumUtil(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] =  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, 5, 7, 9, 11};

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

  

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

    int *st = constructST(arr, n);

  

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

    printf("Sum of values in given range = %dn"

            getSum(st, n, 1, 3));

  

    // Обновление: установить arr [1] = 10 и обновить соответствующее

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

    updateValue(arr, st, n, 1, 10);

  

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

    printf("Updated sum of values in given range = %dn",

             getSum(st, n, 1, 3));

    return 0;

}

Джава

// Java-программа для отображения операций с сегментным деревом, таких как конструкция
// запрос и обновление

class SegmentTree 

{

    int st[]; // Массив, в котором хранятся узлы дерева сегментов

  

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

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

       constructSTUtil () для заполнения выделенной памяти * /

    SegmentTree(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]; // Выделение памяти

  

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

    }

  

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

    int getMid(int s, int e) {

        return s + (e - s) / 2;

    }

  

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

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

  

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

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

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

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

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

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

    int getSumUtil(int ss, int se, int qs, int qe, int si)

    {

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

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

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

            return st[si];

  

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

        if (se < qs || ss > qe)

            return 0;

  

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

        int mid = getMid(ss, se);

        return getSumUtil(ss, mid, qs, qe, 2 * si + 1) +

                getSumUtil(mid + 1, se, qs, qe, 2 * si + 2);

    }

  

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

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

        st, si, ss и se такие же, как getSumUtil ()

        я -> индекс элемента, который будет обновлен. Этот индекс находится в

                 входной массив.

       diff -> Значение, которое будет добавлено ко всем узлам с i в диапазоне * /

    void updateValueUtil(int ss, int se, int i, int diff, int si)

    {

        // Базовый случай: если входной индекс лежит вне диапазона

        // этот сегмент

        if (i < ss || i > se)

            return;

  

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

        // значение узла и его потомков

        st[si] = st[si] + diff;

        if (se != ss) {

            int mid = getMid(ss, se);

            updateValueUtil(ss, mid, i, diff, 2 * si + 1);

            updateValueUtil(mid + 1, se, i, diff, 2 * si + 2);

        }

    }

  

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

   // Он использует updateValueUtil () для обновления значения в дереве сегментов

    void updateValue(int arr[], int n, int i, int new_val)

    {

        // Проверяем ошибочный индекс ввода

        if (i < 0 || i > n - 1) {

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

            return;

        }

  

        // Получить разницу между новым значением и старым значением

        int diff = new_val - arr[i];

  

        // Обновляем значение в массиве

        arr[i] = new_val;

  

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

        updateValueUtil(0, n - 1, i, diff, 0);

    }

  

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

   // qe (конец запроса). Он в основном использует getSumUtil ()

    int getSum(int n, int qs, int qe)

    {

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

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

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

            return -1;

        }

        return getSumUtil(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] = constructSTUtil(arr, ss, mid, si * 2 + 1) +

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

        return st[si];

    }

  

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

    public static void main(String args[])

    {

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

        int n = arr.length;

        SegmentTree  tree = new SegmentTree(arr, n);

  

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

  

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

        System.out.println("Sum of values in given range = " +

                           tree.getSum(n, 1, 3));

  

        // Обновить: установить arr [1] = 10 и обновить соответствующий сегмент

        // узлы дерева

        tree.updateValue(arr, n, 1, 10);

  

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

        System.out.println("Updated sum of values in given range = " +

                tree.getSum(n, 1, 3));

    }

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

python3

# Программа Python3 для отображения операций с сегментным деревом, например
# конструкция, запрос и обновление

from math import ceil, log2;

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

def getMid(s, e) :

    return s + (e -s) // 2

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

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

    параметры для этой функции

  

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

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

           Первоначально 0 передается как корень всегда с индексом 0

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

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

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

def getSumUtil(st, ss, se, qs, qe, si) : 

  

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

    # затем вернуть сумму сегмента

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

        return st[si]; 

  

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

    # вне заданного диапазона

    if (se < qs or ss > qe) :

        return 0

  

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

    # с заданным диапазоном

    mid = getMid(ss, se); 

      

    return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) + \

           getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2); 

  
"" "Рекурсивная функция для обновления узлов
которые имеют данный индекс в своем диапазоне.
Ниже приведены параметры st, si, ss и se.
такие же, как getSumUtil ()
я -> индекс элемента, который будет обновлен.

      Этот индекс находится во входном массиве.

diff -> Значение, которое будет добавлено ко всем узлам
у которого я в диапазоне "" "

def updateValueUtil(st, ss, se, i, diff, si) : 

  

    # Базовый случай: если входной индекс лежит

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

    if (i < ss or i > se) :

        return

  

    # Если входной индекс находится в диапазоне этого узла,

    # затем обновить значение узла и его потомков

    st[si] = st[si] + diff; 

      

    if (se != ss) :

      

        mid = getMid(ss, se); 

        updateValueUtil(st, ss, mid, i, 

                        diff, 2 * si + 1); 

        updateValueUtil(st, mid + 1, se, i, 

                         diff, 2 * si + 2); 

  
# Функция для обновления значения во входном массиве
# и дерево сегментов. Он использует updateValueUtil ()
# обновить значение в дереве сегментов

def updateValue(arr, st, n, i, new_val) : 

  

    # Проверка на ошибочный индекс ввода

    if (i < 0 or i > n - 1) :

          

        print("Invalid Input", end = ""); 

        return

  

    # Получите разницу между

    # новое значение и старое значение

    diff = new_val - arr[i]; 

  

    # Обновить значение в массиве

    arr[i] = new_val; 

  

    # Обновлять значения узлов в сегментном дереве

    updateValueUtil(st, 0, n - 1, i, diff, 0); 

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

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

  

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

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

  

        print("Invalid Input", end = ""); 

        return -1

      

    return getSumUtil(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] = 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, 5, 7, 9, 11]; 

    n = len(arr); 

  

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

    st = constructST(arr, n); 

  

    # Вывести сумму значений в массиве из индекса 1 в 3

    print("Sum of values in given range = ",

                       getSum(st, n, 1, 3)); 

  

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

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

    updateValue(arr, st, n, 1, 10); 

  

    # Найти сумму после обновления значения

    print("Updated sum of values in given range = ",

                     getSum(st, n, 1, 3), end = ""); 

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

C #

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

using System;

  

class SegmentTree 

{

    int []st; // Массив, в котором хранятся узлы дерева сегментов

  

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

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

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

    constructSTUtil () для заполнения выделенной памяти * /

    SegmentTree(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]; // Выделение памяти

  

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

    }

  

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

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

    int getMid(int s, int e) 

    {

        return s + (e - s) / 2;

    }

  

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

    сумма значений в заданном диапазоне

        массива. Следующее

        параметры для этой функции

  

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

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

            сегментное дерево. Первоначально

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

                всегда с индексом 0

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

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

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

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

    int getSumUtil(int ss, int se, int qs, int qe, int si)

    {

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

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

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

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

            return st[si];

  

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

        // вне заданного диапазона

        if (se < qs || ss > qe)

            return 0;

  

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

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

        int mid = getMid(ss, se);

        return getSumUtil(ss, mid, qs, qe, 2 * si + 1) +

                getSumUtil(mid + 1, se, qs, qe, 2 * si + 2);

    }

  

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

    узлы, которые имеют данный

    Индекс в их диапазоне. Следующее

    это параметры st, si, ss и se

    такие же, как getSumUtil () i -> index

    элемента, который будет обновлен. Эта

    индекс находится во входном массиве. diff -> Value

    быть добавленным ко всем узлам с i в диапазоне * /

    void updateValueUtil(int ss, int se, int i,

                                int diff, int si)

    {

        // Базовый случай: если входной индекс

        // лежит вне диапазона этого сегмента

        if (i < ss || i > se)

            return;

  

        // Если входной индекс находится в диапазоне

        // этот узел, затем обновляем значение

        // узла и его потомков

        st[si] = st[si] + diff;

        if (se != ss) 

        {

            int mid = getMid(ss, se);

            updateValueUtil(ss, mid, i, diff, 2 * si + 1);

            updateValueUtil(mid + 1, se, i, diff, 2 * si + 2);

        }

    }

  

    // Функция для обновления значения

    // во входном массиве и сегментном дереве.

    // Он использует updateValueUtil () для

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

    void updateValue(int []arr, int n, int i, int new_val)

    {

        // Проверяем ошибочный индекс ввода

        if (i < 0 || i > n - 1)

        {

            Console.WriteLine("Invalid Input");

            return;

        }

  

        // Получить разницу между

        // новое значение и старое значение

        int diff = new_val - arr[i];

          

        // Обновляем значение в массиве

        arr[i] = new_val;

  

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

        updateValueUtil(0, n - 1, i, diff, 0);

    }

  

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

    // из индекса qs (quey start) в

    // qe (конец запроса). Он в основном использует getSumUtil ()

    int getSum(int n, int qs, int qe)

    {

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

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

        {

            Console.WriteLine("Invalid Input");

            return -1;

        }

        return getSumUtil(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] = constructSTUtil(arr, ss, mid, si * 2 + 1) +

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

        return st[si];

    }

  

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

    public static void Main()

    {

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

        int n = arr.Length;

        SegmentTree tree = new SegmentTree(arr, n);

  

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

  

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

        Console.WriteLine("Sum of values in given range = " +

                                        tree.getSum(n, 1, 3));

  

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

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

        tree.updateValue(arr, n, 1, 10);

  

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

        Console.WriteLine("Updated sum of values in given range = " +

                tree.getSum(n, 1, 3));

    }

}

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


Выход:

 
Sum of values in given range = 15
Updated sum of values in given range = 22

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

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

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


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

Ссылки:
ИИТ Канпур бумага.

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

Сегментное дерево | Набор 1 (сумма заданного диапазона)

0.00 (0%) 0 votes