Рубрики

Двоичное индексированное дерево: обновление диапазона и запросы диапазона

Продвинутые Структуры данных, Технический Scripter

Дан массив arr [0..n-1]. Следующие операции должны быть выполнены.

  1. update (l, r, val) : добавить 'val' ко всем элементам в массиве из [l, r].
  2. getRangeSum (l, r) : Найти сумму всех элементов в массиве из [l, r].

Первоначально все элементы в массиве равны 0. Запросы могут быть в любом порядке, т. Е. Перед суммой диапазона может быть много обновлений.

Пример: 

Input : n = 5   // {0, 0, 0, 0, 0}
Queries: update : l = 0, r = 4, val = 2
         update : l = 3, r = 4, val = 3 
         getRangeSum : l = 2, r = 4

Output: Sum of elements of range [2, 4] is 12

Explanation : Array after first update becomes
              {2, 2, 2, 2, 2}
              Array after second update becomes
              {2, 2, 2, 5, 5}

В предыдущем посте мы обсуждали решения по обновлению диапазона и точечному запросу с использованием BIT.
rangeUpdate (l, r, val): мы добавляем 'val' к элементу с индексом 'l'. Мы вычитаем 'val' из элемента с индексом 'r + 1'.
getElement (index) [или getSum ()]: мы возвращаем сумму элементов от 0 до индекса, который можно быстро получить с помощью BIT.

Мы можем вычислить rangeSum () с помощью запросов getSum ().
rangeSum (l, r) = getSum (r) — getSum (l-1)

Простое решение — использовать решения, обсужденные в предыдущем посте . Запрос на обновление диапазона такой же. Запрос суммы диапазона можно выполнить, выполнив запрос get для всех элементов в диапазоне.

Эффективное решение — убедиться, что оба запроса могут быть выполнены за время O (Log n). Мы получаем сумму диапазона, используя префиксные суммы. Как убедиться, что обновление выполняется таким образом, чтобы сумма префикса могла быть сделана быстро? Рассмотрим ситуацию, когда префикс sum [0, k] (где 0 <= k <n) необходим после обновления диапазона в диапазоне [l, r]. Три случая возникают, так как k может лежать в 3 регионах.

Случай 1 : 0 <k <l
Запрос на обновление не повлияет на запрос суммы.

Случай 2 : l <= k <= r
Рассмотрим пример:

Add 2 to range [2, 4], the resultant array would be:
0 0 2 2 2
If k = 3
Sum from [0, k] = 4

Как получить этот результат?
Просто добавьте val из l- го индекса в k- й индекс. Сумма увеличивается на «val * (k) — val * (l-1)» после запроса на обновление.

Случай 3 : k> r
Для этого случая нам нужно добавить «val» из l- го индекса в r- й индекс. Сумма увеличивается на «val * r — val * (l-1)» из-за запроса на обновление.

Наблюдения:
Случай 1: прост, так как сумма останется такой же, какой была до обновления.

Случай 2: сумма была увеличена на val * k — val * (l-1). Мы можем найти «val», это похоже на поиск i- го элемента в статье обновления диапазона и точечного запроса . Таким образом, мы поддерживаем один бит для обновления диапазона и точечных запросов, этот бит будет полезен при поиске значения по k- му индексу. Теперь вычисляется val * k, как обработать дополнительный термин val * (l-1)?
Чтобы обработать этот дополнительный термин, мы поддерживаем еще один бит (BIT2). Обновите val * (l-1) по l- му индексу, чтобы при выполнении запроса getSum на BIT2 результат получался как val * (l-1).

Случай 3: сумма в случае 3 была увеличена на «val * r — val * (l-1)», значение этого члена можно получить с помощью BIT2. Вместо добавления мы вычитаем «val * (l-1) — val * r», поскольку мы можем получить это значение из BIT2, добавляя val * (l-1), как мы это делали в случае 2, и вычитая val * r в каждом обновлении операция.

Update Query 
Update(BITree1, l, val)
Update(BITree1, r+1, -val)
UpdateBIT2(BITree2, l, val*(l-1))
UpdateBIT2(BITree2, r+1, -val*r)

Range Sum 
getSum(BITTree1, k) *k) - getSum(BITTree2, k)

Реализация вышеуказанной идеи

C ++

// C ++ программа для демонстрации обновления диапазона
// и Range Range с использованием BIT
#include <iostream>

using namespace std;

  
// Возвращает сумму arr [0..index]. Эта функция предполагает
// что массив предварительно обработан и частичные суммы
// элементы массива хранятся в BITree []

int getSum(int BITree[], int index)

{

    int sum = 0; // Инициализировать результат

  

    // индекс в BITree [] на 1 больше, чем индекс в arr []

    index = index + 1;

  

    // Пройдемся по предкам BITree [index]

    while (index>0)

    {

        // Добавить текущий элемент BITree к сумме

        sum += BITree[index];

  

        // Переместить индекс на родительский узел в представлении getSum

        index -= index & (-index);

    }

    return sum;

}

  
// Обновляет узел в дереве двоичных индексов (BITree) в данный момент
// индекс в BITree. Данное значение 'val' добавляется к
// BITree [i] и все его предки в дереве.

void updateBIT(int BITree[], int n, int index, int val)

{

    // индекс в BITree [] на 1 больше, чем индекс в arr []

    index = index + 1;

  

    // Обходим всех предков и добавляем 'val'

    while (index <= n)

    {

        // Добавить 'val' к текущему узлу дерева BI

        BITree[index] += val;

  

        // Обновить индекс до родительского в обновлении View

        index += index & (-index);

    }

}

  
// Возвращает сумму массива из [0, x]

int sum(int x, int BITTree1[], int BITTree2[])

{

    return (getSum(BITTree1, x) * x) - getSum(BITTree2, x);

}

  

  

void updateRange(int BITTree1[], int BITTree2[], int n,

                 int val, int l, int r)

{

    // Обновляем оба дерева двоичных индексов

    // Как обсуждено в статье

  

    // Обновляем BIT1

    updateBIT(BITTree1,n,l,val);

    updateBIT(BITTree1,n,r+1,-val);

  

    // Обновляем BIT2

    updateBIT(BITTree2,n,l,val*(l-1));

    updateBIT(BITTree2,n,r+1,-val*r);

}

  

int rangeSum(int l, int r, int BITTree1[], int BITTree2[])

{

    // Находим сумму из [0, r], затем вычитаем сумму

    // из [0, l-1], чтобы найти сумму из

    // [l, r]

    return sum(r, BITTree1, BITTree2) -

           sum(l-1, BITTree1, BITTree2);

}

  

  

int *constructBITree(int n)

{

    // Создать и инициализировать BITree [] как 0

    int *BITree = new int[n+1];

    for (int i=1; i<=n; i++)

        BITree[i] = 0;

  

    return BITree;

}

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

int main()

{

    int n = 5;

  

    // Построить два БИТ

    int *BITTree1, *BITTree2;

  

    // BIT1 для получения элемента по любому индексу

    // в массиве

    BITTree1 = constructBITree(n);

  

    // BIT 2 поддерживает дополнительный срок

    // который нужно вычесть

    BITTree2 = constructBITree(n);

  

    // Добавить 5 ко всем элементам из [0,4]

    int l = 0 , r = 4 , val = 5;

    updateRange(BITTree1,BITTree2,n,val,l,r);

  

    // Добавить 2 ко всем элементам из [2,4]

    l = 2 , r = 4 , val = 10;

    updateRange(BITTree1,BITTree2,n,val,l,r);

  

    // Находим сумму всех элементов из

    // [1,4]

    l = 1 , r = 4;

    cout << "Sum of elements from [" << l

         << "," << r << "] is ";

    cout << rangeSum(l,r,BITTree1,BITTree2) << "\n";

  

    return 0;

}

Джава

// Java-программа для демонстрации обновления диапазона
// и Range Range с использованием BIT

import java.util.*;

  

class GFG

{

  
// Возвращает сумму arr [0..index]. Эта функция предполагает
// что массив предварительно обработан и частичные суммы
// элементы массива хранятся в BITree []

static int getSum(int BITree[], int index)

{

    int sum = 0; // Инициализировать результат

  

    // индекс в BITree [] на 1 больше, чем индекс в arr []

    index = index + 1;

  

    // Пройдемся по предкам BITree [index]

    while (index > 0)

    {

        // Добавить текущий элемент BITree к сумме

        sum += BITree[index];

  

        // Переместить индекс на родительский узел в представлении getSum

        index -= index & (-index);

    }

    return sum;

}

  
// Обновляет узел в дереве двоичных индексов (BITree) в данный момент
// индекс в BITree. Данное значение 'val' добавляется к
// BITree [i] и все его предки в дереве.

static void updateBIT(int BITree[], int n, int index, int val)

{

    // индекс в BITree [] на 1 больше, чем индекс в arr []

    index = index + 1;

  

    // Обходим всех предков и добавляем 'val'

    while (index <= n)

    {

        // Добавить 'val' к текущему узлу дерева BI

        BITree[index] += val;

  

        // Обновить индекс до родительского в обновлении View

        index += index & (-index);

    }

}

  
// Возвращает сумму массива из [0, x]

static int sum(int x, int BITTree1[], int BITTree2[])

{

    return (getSum(BITTree1, x) * x) - getSum(BITTree2, x);

}

  

  

static void updateRange(int BITTree1[], int BITTree2[], int n,

                int val, int l, int r)

{

    // Обновляем оба дерева двоичных индексов

    // Как обсуждено в статье

  

    // Обновляем BIT1

    updateBIT(BITTree1, n, l, val);

    updateBIT(BITTree1, n, r + 1, -val);

  

    // Обновляем BIT2

    updateBIT(BITTree2, n, l, val * (l - 1));

    updateBIT(BITTree2, n, r + 1, -val * r);

}

  

static int rangeSum(int l, int r, int BITTree1[], int BITTree2[])

{

    // Находим сумму из [0, r], затем вычитаем сумму

    // из [0, l-1], чтобы найти сумму из

    // [l, r]

    return sum(r, BITTree1, BITTree2) -

        sum(l - 1, BITTree1, BITTree2);

}

  

  

static int[] constructBITree(int n)

{

    // Создать и инициализировать BITree [] как 0

    int []BITree = new int[n + 1];

    for (int i = 1; i <= n; i++)

        BITree[i] = 0;

  

    return BITree;

}

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

public static void main(String[] args)

{

    int n = 5;

  

    // Contwo BIT

    int []BITTree1;

    int []BITTree2;

  

    // BIT1 для получения элемента по любому индексу

    // в массиве

    BITTree1 = constructBITree(n);

  

    // BIT 2 поддерживает дополнительный срок

    // который нужно вычесть

    BITTree2 = constructBITree(n);

  

    // Добавить 5 ко всем элементам из [0,4]

    int l = 0 , r = 4 , val = 5;

    updateRange(BITTree1, BITTree2, n, val, l, r);

  

    // Добавить 2 ко всем элементам из [2,4]

    l = 2 ; r = 4 ; val = 10;

    updateRange(BITTree1, BITTree2, n, val, l, r);

  

    // Находим сумму всех элементов из

    // [1,4]

    l = 1 ; r = 4;

    System.out.print("Sum of elements from [" + l

        + "," + r+ "] is ");

    System.out.print(rangeSum(l, r, BITTree1, BITTree2)+ "\n");

}
}

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

C #

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

using System;

  

class GFG

{

  
// Возвращает сумму arr [0..index]. Эта функция предполагает
// что массив предварительно обработан и частичные суммы
// элементы массива хранятся в BITree []

static int getSum(int []BITree, int index)

{

    int sum = 0; // Инициализировать результат

  

    // индекс в BITree [] на 1 больше

    // индекс в [] обр

    index = index + 1;

  

    // Пройдемся по предкам BITree [index]

    while (index > 0)

    {

        // Добавить текущий элемент BITree к сумме

        sum += BITree[index];

  

        // Переместить индекс на родительский узел в представлении getSum

        index -= index & (-index);

    }

    return sum;

}

  
// Обновляет узел в дереве двоичных индексов (BITree) в данный момент
// индекс в BITree. Данное значение 'val' добавляется к
// BITree [i] и все его предки в дереве.

static void updateBIT(int []BITree, int n, 

                      int index, int val)

{

    // индекс в BITree [] на 1 больше

    // индекс в [] обр

    index = index + 1;

  

    // Обходим всех предков и добавляем 'val'

    while (index <= n)

    {

        // Добавить 'val' к текущему узлу дерева BI

        BITree[index] += val;

  

        // Обновить индекс до

        // родитель в обновлении View

        index += index & (-index);

    }

}

  
// Возвращает сумму массива из [0, x]

static int sum(int x, int []BITTree1,

                      int []BITTree2)

{

    return (getSum(BITTree1, x) * x) - 

            getSum(BITTree2, x);

}

  

  

static void updateRange(int []BITTree1, 

                        int []BITTree2, int n,

                        int val, int l, int r)

{

    // Обновляем оба дерева двоичных индексов

    // Как обсуждено в статье

  

    // Обновляем BIT1

    updateBIT(BITTree1, n, l, val);

    updateBIT(BITTree1, n, r + 1, -val);

  

    // Обновляем BIT2

    updateBIT(BITTree2, n, l, val * (l - 1));

    updateBIT(BITTree2, n, r + 1, -val * r);

}

  

static int rangeSum(int l, int r, 

                    int []BITTree1, 

                    int []BITTree2)

{

    // Находим сумму из [0, r], затем вычитаем сумму

    // из [0, l-1], чтобы найти сумму из

    // [l, r]

    return sum(r, BITTree1, BITTree2) -

           sum(l - 1, BITTree1, BITTree2);

}

  

static int[] constructBITree(int n)

{

    // Создать и инициализировать BITree [] как 0

    int []BITree = new int[n + 1];

    for (int i = 1; i <= n; i++)

        BITree[i] = 0;

  

    return BITree;

}

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

public static void Main(String[] args)

{

    int n = 5;

  

    // Contwo BIT

    int []BITTree1;

    int []BITTree2;

  

    // BIT1 для получения элемента по любому индексу

    // в массиве

    BITTree1 = constructBITree(n);

  

    // BIT 2 поддерживает дополнительный срок

    // который нужно вычесть

    BITTree2 = constructBITree(n);

  

    // Добавить 5 ко всем элементам из [0,4]

    int l = 0 , r = 4 , val = 5;

    updateRange(BITTree1, BITTree2, n, val, l, r);

  

    // Добавить 2 ко всем элементам из [2,4]

    l = 2 ; r = 4 ; val = 10;

    updateRange(BITTree1, BITTree2, n, val, l, r);

  

    // Находим сумму всех элементов из

    // [1,4]

    l = 1 ; r = 4;

    Console.Write("Sum of elements from [" + l + 

                             "," + r + "] is ");

    Console.Write(rangeSum(l, r, BITTree1,

                                 BITTree2) + "\n");

}
}

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

Выход:

Sum of elements from [1,4] is 50

Сложность времени : O (q * log (n)), где q — количество запросов.

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

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

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

Двоичное индексированное дерево: обновление диапазона и запросы диапазона

0.00 (0%) 0 votes