Рубрики

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

У нас есть массив arr [0. , , н-1]. Есть два типа запросов

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

Всего будет q запросов.

Ограничение ввода

 n <= 10^5, q <= 10^5

Решение 1
Простое решение состоит в том, чтобы запустить цикл от l до r и вычислить xor элементов в заданном диапазоне. Чтобы обновить значение, просто сделайте arr [i] = x. Первая операция занимает O (n) время, а вторая операция занимает O (1) время. В худшем случае сложность времени O (n * q) для q запросов
что займет огромное время для n ~ 10 ^ 5 и q ~ 10 ^ 5. Следовательно, это решение будет превышать срок.

Решение 2
Другое решение состоит в том, чтобы хранить xor во всех возможных диапазонах, но существует O (n ^ 2) возможных диапазонов, следовательно, при n ~ 10 ^ 5 он превысит сложность пространства, следовательно, без учета временной сложности мы можем утверждать, что это решение не будет работать.

Решение 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;

}

Выход:

Xor of values in given range = 1
Updated xor of values in given range = 8

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

Временная сложность запроса составляет O (log n).
Временная сложность обновления также O (log n).

Общая сложность времени: O (n) для построения + O (log n) для каждого запроса = O (n) + O (n * log n) = O (n * log n)

Time Complexity O(n * log n)
Auxiliary Space  O(n)

Эта статья предоставлена Пратиком Чхаджером . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

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

0.00 (0%) 0 votes