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

// 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 для отображения операций с сегментным деревом, например
# конструкция, запрос и обновление

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 # Программа для отображения дерева сегментов
// операции типа строительства,
// запрос и обновление

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 * /