Дат низ арр[0..Н-1]. Потребно је извршити следеће операције.
- ажурирање (л р вал) : Додајте 'вал' свим елементима у низу из [л р].
- гетРангеСум(л р) : Пронађите збир свих елемената у низу из [л р].
У почетку су сви елементи у низу 0. Упити могу бити у било ком редоследу, тј. може бити много ажурирања пре збира опсега.
Пример:
Улаз: Н = 5 // {0 0 0 0 0}
Упити: ажурирање: л = 0 р = 4 вал = 2
ажурирање: л = 3 р = 4 вал = 3
гетРангеСум : л = 2 р = 4Излаз: Збир елемената опсега [2 4] је 12
Објашњење: Низ након првог ажурирања постаје {2 2 2 2 2}
Низ након другог ажурирања постаје {2 2 2 5 5}
Наивни приступ: Да бисте решили проблем, следите следећу идеју:
У претходни пост расправљали смо о ажурирању опсега и решењима за упите тачака користећи БИТ.
рангеУпдате(л р вал) : Додајемо 'вал' елементу на индексу 'л'. Од елемента са индексом 'р+1' одузимамо 'вал'.
гетЕлемент(индек) [или гетСум()]: Враћамо збир елемената од 0 до индекса који се може брзо добити коришћењем БИТ-а.
Можемо да израчунамо рангеСум() користећи гетСум() упите.
рангеСум(л р) = гетСум(р) - гетСум(л-1)државе у САДЈедноставно решење је коришћење решења о којима се говори у претходни пост . Упит за ажурирање опсега је исти. Упит за суму опсега се може постићи извођењем упита гет за све елементе у опсегу.
Ефикасан приступ: Да бисте решили проблем, следите следећу идеју:
Добијамо збир опсега користећи префиксне суме. Како се уверити да је ажурирање обављено на начин да се збир префикса може обавити брзо? Размотрите ситуацију у којој је збир префикса [0 к] (где је 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
Ако је к = 3 Збир из [0 к] = 4Како доћи до овог резултата?
Једноставно додајте вал из лтхиндекс на ктхиндекс. Збир се повећава за 'вал*(к) - вал*(л-1)' након упита за ажурирање.
- Случај 3 : к > р
- За овај случај морамо додати 'вал' из лтхиндекс на ртхиндекс. Збир се повећава за 'вал*р – вал*(л-1)' због упита за ажурирање.
запажања:
Случај 1: је једноставно јер би збир остао исти као и пре ажурирања.
преузми иоутубе видео влц
Случај 2: Збир је повећан за вал*к - вал*(л-1). Можемо пронаћи 'вал' то је слично проналажењу итхелемент у ажурирање опсега и чланак о упиту о тачкама . Тако да одржавамо један БИТ за ажурирање опсега и упите о тачкама, овај БИТ ће бити од помоћи у проналажењу вредности на ктхиндекс. Сада се израчунава вал * к како се поступа са додатним термином вал*(л-1)?
Да бисмо обрадили овај додатни термин одржавамо још један БИТ (БИТ2). Ажурирајте вал * (л-1) на лтхиндекс, тако да када се гетСум упит изврши на БИТ2 ће дати резултат као вал*(л-1).
Случај 3: Збир у случају 3 је увећан за 'вал*р - вал *(л-1)' вредност овог појма се може добити коришћењем БИТ2. Уместо сабирања одузимамо 'вал*(л-1) - вал*р' јер ову вредност можемо добити из БИТ2 додавањем вал*(л-1) као што смо урадили у случају 2 и одузимањем вал*р у свакој операцији ажурирања.
Ажурирај упит
Ажурирање (БИТрее1 л вал)
Ажурирај (БИТрее1 р+1 -вал)
УпдатеБИТ2(БИТрее2 л вал*(л-1))
УпдатеБИТ2(БИТрее2 р+1 -вал*р)Ранг Сум
гетСум(БИТТрее1 к) *к) - гетСум(БИТТрее2 к)
Пратите доле наведене кораке да бисте решили проблем:
- Креирајте два бинарна стабла индекса користећи дату функцију цонструцтБИТрее()
- Да бисте пронашли збир у датом опсегу, позовите функцију рангеСум() са параметрима као датим опсегом и бинарно индексираним стаблима
- Позовите функцију суме која ће вратити збир у опсегу [0 Кс]
- Повратни збир(Р) - збир(Л-1)
- Унутар ове функције позовите функцију гетСум() која ће вратити збир низа из [0 Кс]
- Врати гетСум(дрво1 к) * к - гетСум(трее2 к)
- Унутар функције гетСум() креирајте целобројну суму једнаку нули и повећајте индекс за 1
- Док је индекс већи од нуле, повећајте збир за Трее[индекс]
- Смањите индекс за (индекс & (-индек)) да бисте преместили индекс на родитељски чвор у стаблу
- Повратни збир
- Одштампајте збир у датом опсегу
Испод је имплементација горњег приступа:
C++// C++ program to demonstrate Range Update // and Range Queries using BIT #include
// 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 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
<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
Временска сложеност : О(к * лог(Н)) где је к број упита.
Помоћни простор: О(Н)