БІНАРНЕ ІНДЕКСОВАНЕ ДЕРЕВО: ОНОВЛЕННЯ ДІАПАЗОНУ ТА ЗАПИТИ ДІАПАЗОНУ

Дано масив arr[0..N-1]. Необхідно виконати наступні операції.

оновлення (l r val) : додати «val» до всіх елементів у масиві з [l r].
getRangeSum(l r) : знайти суму всіх елементів у масиві з [l r].

Спочатку всі елементи в масиві дорівнюють 0. Запити можуть бути в будь-якому порядку, тобто може бути багато оновлень перед сумою діапазону.

приклад:

введення: N = 5 // {0 0 0 0 0}
запити: оновлення: l = 0 r = 4 значення = 2
оновлення: l = 3 r = 4 значення = 3
getRangeSum : l = 2 r = 4

Вихід: Сума елементів діапазону [2 4] дорівнює 12
Пояснення: Масив після першого оновлення стає {2 2 2 2 2}
Масив після другого оновлення стає {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)
java лямбда

Просте рішення полягає у використанні рішень, розглянутих у попередній пост . Запит на оновлення діапазону той самий. Запит на суму діапазону можна отримати, виконавши запит на отримання для всіх елементів у діапазоні.

Ефективний підхід: Щоб вирішити проблему, дотримуйтеся наведеної нижче ідеї:

Ми отримуємо суму діапазону за допомогою префіксних сум. Як переконатися, що оновлення виконується таким чином, щоб можна було швидко виконати суму префікса? Розглянемо ситуацію, коли префікс sum [0 k] (де 0<= k < n) is needed after range update on the range [l r]. Three cases arise as k can possibly lie in 3 regions.

Випадок 1 : 0< k < l
Запит на оновлення не вплине на запит суми.
Випадок 2 : л<= k <= r
Розглянемо приклад: додайте 2 до діапазону [2 4], результуючий масив буде таким: 0 0 2 2 2
Якщо k = 3 Сума з [0 k] = 4
Як отримати такий результат?
Просто додайте значення з 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^тиселемент в оновлення діапазону та стаття про запит точки . Тому ми підтримуємо один BIT для оновлення діапазону та запитів точок, цей BIT допоможе знайти значення на k^тисіндекс. Тепер обчислюється val * k, як обробляти додатковий член val*(l-1)?
Для обробки цього додаткового терміну ми підтримуємо інший BIT (BIT2). Оновити значення * (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 під час кожної операції оновлення.

Оновити запит

Оновлення (BITree1 l val)
Оновлення (BITree1 r+1 -val)
ОновленняBIT2(BITree2 l val*(l-1))
ОновленняBIT2(BITree2 r+1 -val*r)

Сума діапазону

getSum(BITTree1 k) *k) - getSum(BITTree2 k)
змінна глобальний javascript

Щоб вирішити проблему, виконайте наведені нижче дії.

Створіть два бінарних індексних дерева за допомогою заданої функції constructBITree()
Щоб знайти суму в заданому діапазоні, викличте функцію rangeSum() із параметрами заданого діапазону та бінарних індексованих дерев
- Виклик функції sum, яка поверне суму в діапазоні [0 X]
- Сума повернення (R) - сума (L-1)
  - Усередині цієї функції викликається функція getSum(), яка повертає суму масиву з [0 X]
  - Повернути getSum(Tree1 x) * x - getSum(tree2 x)
  - Усередині функції getSum() створіть цілу суму, що дорівнює нулю, і збільште індекс на 1
  - Якщо індекс більший за нуль, збільште суму на Tree[index]
  - Зменшіть індекс на (index & (-index)), щоб перемістити індекс до батьківського вузла в дереві
  - Сума повернення
Виведіть суму в заданому діапазоні

Нижче наведено реалізацію вищезазначеного підходу:

C++

// C++ program to demonstrate Range Update // and Range Queries using BIT #include    using namespace std; // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[] int getSum(int BITree[] int index) {  int sum = 0; // Initialize result  // index in BITree[] is 1 more than the index in arr[]  index = index + 1;  // Traverse ancestors of BITree[index]  while (index > 0) {  // Add current element of BITree to sum  sum += BITree[index];  // Move index to parent node in getSum View  index -= index & (-index);  }  return sum; } // Updates a node in Binary Index Tree (BITree) at given // index in BITree. The given value 'val' is added to // BITree[i] and all of its ancestors in tree. void updateBIT(int BITree[] int n int index int val) {  // index in BITree[] is 1 more than the index in arr[]  index = index + 1;  // Traverse all ancestors and add 'val'  while (index <= n) {  // Add 'val' to current node of BI Tree  BITree[index] += val;  // Update index to that of parent in update View  index += index & (-index);  } } // Returns the sum of array from [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) {  // Update Both the Binary Index Trees  // As discussed in the article  // Update BIT1  updateBIT(BITTree1 n l val);  updateBIT(BITTree1 n r + 1 -val);  // Update 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[]) {  // Find sum from [0r] then subtract sum  // from [0l-1] in order to find sum from  // [lr]  return sum(r BITTree1 BITTree2)  - sum(l - 1 BITTree1 BITTree2); } int* constructBITree(int n) {  // Create and initialize BITree[] as 0  int* BITree = new int[n + 1];  for (int i = 1; i <= n; i++)  BITree[i] = 0;  return BITree; } // Driver code int main() {  int n = 5;  // Construct two BIT  int *BITTree1 *BITTree2;  // BIT1 to get element at any index  // in the array  BITTree1 = constructBITree(n);  // BIT 2 maintains the extra term  // which needs to be subtracted  BITTree2 = constructBITree(n);  // Add 5 to all the elements from [04]  int l = 0 r = 4 val = 5;  updateRange(BITTree1 BITTree2 n val l r);  // Add 10 to all the elements from [24]  l = 2 r = 4 val = 10;  updateRange(BITTree1 BITTree2 n val l r);  // Find sum of all the elements from  // [14]  l = 1 r = 4;  cout << 'Sum of elements from [' << l << '' << r  << '] is ';  cout << rangeSum(l r BITTree1 BITTree2) << 'n';  return 0; }

Java

// Java program to demonstrate Range Update // and Range Queries using BIT import java.util.*; class GFG {  // Returns sum of arr[0..index]. This function assumes  // that the array is preprocessed and partial sums of  // array elements are stored in BITree[]  static int getSum(int BITree[] int index)  {  int sum = 0; // Initialize result  // index in BITree[] is 1 more than the index in  // arr[]  index = index + 1;  // Traverse ancestors of BITree[index]  while (index > 0) {  // Add current element of BITree to sum  sum += BITree[index];  // Move index to parent node in getSum View  index -= index & (-index);  }  return sum;  }  // Updates a node in Binary Index Tree (BITree) at given  // index in BITree. The given value 'val' is added to  // BITree[i] and all of its ancestors in tree.  static void updateBIT(int BITree[] int n int index  int val)  {  // index in BITree[] is 1 more than the index in  // arr[]  index = index + 1;  // Traverse all ancestors and add 'val'  while (index <= n) {  // Add 'val' to current node of BI Tree  BITree[index] += val;  // Update index to that of parent in update View  index += index & (-index);  }  }  // Returns the sum of array from [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)  {  // Update Both the Binary Index Trees  // As discussed in the article  // Update BIT1  updateBIT(BITTree1 n l val);  updateBIT(BITTree1 n r + 1 -val);  // Update 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[])  {  // Find sum from [0r] then subtract sum  // from [0l-1] in order to find sum from  // [lr]  return sum(r BITTree1 BITTree2)  - sum(l - 1 BITTree1 BITTree2);  }  static int[] constructBITree(int n)  {  // Create and initialize BITree[] as 0  int[] BITree = new int[n + 1];  for (int i = 1; i <= n; i++)  BITree[i] = 0;  return BITree;  }  // Driver Program to test above function  public static void main(String[] args)  {  int n = 5;  // Contwo BIT  int[] BITTree1;  int[] BITTree2;  // BIT1 to get element at any index  // in the array  BITTree1 = constructBITree(n);  // BIT 2 maintains the extra term  // which needs to be subtracted  BITTree2 = constructBITree(n);  // Add 5 to all the elements from [04]  int l = 0 r = 4 val = 5;  updateRange(BITTree1 BITTree2 n val l r);  // Add 10 to all the elements from [24]  l = 2;  r = 4;  val = 10;  updateRange(BITTree1 BITTree2 n val l r);  // Find sum of all the elements from  // [14]  l = 1;  r = 4;  System.out.print('Sum of elements from [' + l + ''  + r + '] is ');  System.out.print(rangeSum(l r BITTree1 BITTree2)  + 'n');  } } // This code is contributed by 29AjayKumar

Python3

# Python3 program to demonstrate Range Update # and Range Queries using BIT # Returns sum of arr[0..index]. This function assumes # that the array is preprocessed and partial sums of # array elements are stored in BITree[] def getSum(BITree: list index: int) -> int: summ = 0 # Initialize result # index in BITree[] is 1 more than the index in arr[] index = index + 1 # Traverse ancestors of BITree[index] while index > 0: # Add current element of BITree to sum summ += BITree[index] # Move index to parent node in getSum View index -= index & (-index) return summ # Updates a node in Binary Index Tree (BITree) at given # index in BITree. The given value 'val' is added to # BITree[i] and all of its ancestors in tree. def updateBit(BITTree: list n: int index: int val: int) -> None: # index in BITree[] is 1 more than the index in arr[] index = index + 1 # Traverse all ancestors and add 'val' while index <= n: # Add 'val' to current node of BI Tree BITTree[index] += val # Update index to that of parent in update View index += index & (-index) # Returns the sum of array from [0 x] def summation(x: int BITTree1: list BITTree2: list) -> int: return (getSum(BITTree1 x) * x) - getSum(BITTree2 x) def updateRange(BITTree1: list BITTree2: list n: int val: int l: int r: int) -> None: # Update Both the Binary Index Trees # As discussed in the article # Update BIT1 updateBit(BITTree1 n l val) updateBit(BITTree1 n r + 1 -val) # Update BIT2 updateBit(BITTree2 n l val * (l - 1)) updateBit(BITTree2 n r + 1 -val * r) def rangeSum(l: int r: int BITTree1: list BITTree2: list) -> int: # Find sum from [0r] then subtract sum # from [0l-1] in order to find sum from # [lr] return summation(r BITTree1 BITTree2) - summation( l - 1 BITTree1 BITTree2) # Driver Code if __name__ == '__main__': n = 5 # BIT1 to get element at any index # in the array BITTree1 = [0] * (n + 1) # BIT 2 maintains the extra term # which needs to be subtracted BITTree2 = [0] * (n + 1) # Add 5 to all the elements from [04] l = 0 r = 4 val = 5 updateRange(BITTree1 BITTree2 n val l r) # Add 10 to all the elements from [24] l = 2 r = 4 val = 10 updateRange(BITTree1 BITTree2 n val l r) # Find sum of all the elements from # [14] l = 1 r = 4 print('Sum of elements from [%d%d] is %d' % (l r rangeSum(l r BITTree1 BITTree2))) # This code is contributed by # sanjeev2552

// C# program to demonstrate Range Update // and Range Queries using BIT using System; class GFG {  // Returns sum of arr[0..index]. This function assumes  // that the array is preprocessed and partial sums of  // array elements are stored in BITree[]  static int getSum(int[] BITree int index)  {  int sum = 0; // Initialize result  // index in BITree[] is 1 more than  // the index in []arr  index = index + 1;  // Traverse ancestors of BITree[index]  while (index > 0) {  // Add current element of BITree to sum  sum += BITree[index];  // Move index to parent node in getSum View  index -= index & (-index);  }  return sum;  }  // Updates a node in Binary Index Tree (BITree) at given  // index in BITree. The given value 'val' is added to  // BITree[i] and all of its ancestors in tree.  static void updateBIT(int[] BITree int n int index  int val)  {  // index in BITree[] is 1 more than  // the index in []arr  index = index + 1;  // Traverse all ancestors and add 'val'  while (index <= n) {  // Add 'val' to current node of BI Tree  BITree[index] += val;  // Update index to that of  // parent in update View  index += index & (-index);  }  }  // Returns the sum of array from [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)  {  // Update Both the Binary Index Trees  // As discussed in the article  // Update BIT1  updateBIT(BITTree1 n l val);  updateBIT(BITTree1 n r + 1 -val);  // Update 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)  {  // Find sum from [0r] then subtract sum  // from [0l-1] in order to find sum from  // [lr]  return sum(r BITTree1 BITTree2)  - sum(l - 1 BITTree1 BITTree2);  }  static int[] constructBITree(int n)  {  // Create and initialize BITree[] as 0  int[] BITree = new int[n + 1];  for (int i = 1; i <= n; i++)  BITree[i] = 0;  return BITree;  }  // Driver Code  public static void Main(String[] args)  {  int n = 5;  // Contwo BIT  int[] BITTree1;  int[] BITTree2;  // BIT1 to get element at any index  // in the array  BITTree1 = constructBITree(n);  // BIT 2 maintains the extra term  // which needs to be subtracted  BITTree2 = constructBITree(n);  // Add 5 to all the elements from [04]  int l = 0 r = 4 val = 5;  updateRange(BITTree1 BITTree2 n val l r);  // Add 10 to all the elements from [24]  l = 2;  r = 4;  val = 10;  updateRange(BITTree1 BITTree2 n val l r);  // Find sum of all the elements from  // [14]  l = 1;  r = 4;  Console.Write('Sum of elements from [' + l + '' + r  + '] is ');  Console.Write(rangeSum(l r BITTree1 BITTree2)  + 'n');  } } // This code is contributed by 29AjayKumar

JavaScript

<script> // JavaScript program to demonstrate Range Update // and Range Queries using BIT // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[] function getSum(BITreeindex) {  let sum = 0; // Initialize result    // index in BITree[] is 1 more than the index in arr[]  index = index + 1;    // Traverse ancestors of BITree[index]  while (index > 0)  {  // Add current element of BITree to sum  sum += BITree[index];    // Move index to parent node in getSum View  index -= index & (-index);  }  return sum; } // Updates a node in Binary Index Tree (BITree) at given // index in BITree. The given value 'val' is added to // BITree[i] and all of its ancestors in tree. function updateBIT(BITreenindexval) {  // index in BITree[] is 1 more than the index in arr[]  index = index + 1;    // Traverse all ancestors and add 'val'  while (index <= n)  {  // Add 'val' to current node of BI Tree  BITree[index] += val;    // Update index to that of parent in update View  index += index & (-index);  } } // Returns the sum of array from [0 x] function sum(xBITTree1BITTree2) {  return (getSum(BITTree1 x) * x) - getSum(BITTree2 x); } function updateRange(BITTree1BITTree2nvallr) {  // Update Both the Binary Index Trees  // As discussed in the article    // Update BIT1  updateBIT(BITTree1 n l val);  updateBIT(BITTree1 n r + 1 -val);    // Update BIT2  updateBIT(BITTree2 n l val * (l - 1));  updateBIT(BITTree2 n r + 1 -val * r); } function rangeSum(lrBITTree1BITTree2) {  // Find sum from [0r] then subtract sum  // from [0l-1] in order to find sum from  // [lr]  return sum(r BITTree1 BITTree2) -  sum(l - 1 BITTree1 BITTree2); } function constructBITree(n) {  // Create and initialize BITree[] as 0  let BITree = new Array(n + 1);  for (let i = 1; i <= n; i++)  BITree[i] = 0;    return BITree; } // Driver Program to test above function let n = 5;   // Contwo BIT let BITTree1; let BITTree2; // BIT1 to get element at any index // in the array BITTree1 = constructBITree(n); // BIT 2 maintains the extra term // which needs to be subtracted BITTree2 = constructBITree(n); // Add 5 to all the elements from [04] let l = 0  r = 4  val = 5; updateRange(BITTree1 BITTree2 n val l r); // Add 10 to all the elements from [24] l = 2 ; r = 4 ; val = 10; updateRange(BITTree1 BITTree2 n val l r); // Find sum of all the elements from // [14] l = 1 ; r = 4; document.write('Sum of elements from [' + l  + '' + r+ '] is '); document.write(rangeSum(l r BITTree1 BITTree2)+ '  
'); // This code is contributed by rag2127 </script>

Вихід

Sum of elements from [14] is 50

Часова складність : O(q * log(N)), де q – кількість запитів.
Допоміжний простір: O(N)

TechCodeview

Бінарне індексоване дерево: Оновлення діапазону та запити діапазону

Спостереження: