Сегментное дерево | Набор 3 (XOR заданного диапазона)

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

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

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

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

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

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

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

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

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

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

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

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

{

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

    // xor отрезка

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

        return st[si];

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

    if (se < qs || ss > qe)

        return 0;

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

    int mid = getMid(ss, se);

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

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

}

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

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

    st, si, ss и se совпадают с getXorUtil ()

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

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

   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);

}

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

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

{

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

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

    {

        printf("Invalid Input");

        return -1;

    }

    return getXorUtil(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];

    }

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

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

    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 =  (int *)malloc(sizeof(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);

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

    printf("Xor of values in given range = %d\n", 

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

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

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

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

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

    printf("Updated xor of values in given range = %d\n",

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

    return 0;

}