Binärer indizierter Baum: Bereichsaktualisierung und Bereichsabfragen
Gegeben sei ein Array arr[0..N-1]. Die folgenden Vorgänge müssen ausgeführt werden.
- update(l r val) : Füge „val“ zu allen Elementen im Array von [l r] hinzu.
- getRangeSum(l r) : Ermitteln Sie die Summe aller Elemente im Array aus [l r].
Anfänglich sind alle Elemente im Array 0. Abfragen können in beliebiger Reihenfolge erfolgen, d. h. es können viele Aktualisierungen vor der Bereichssumme erfolgen.
Beispiel:
Eingang: N = 5 // {0 0 0 0 0}
Anfragen: Aktualisierung: l = 0 r = 4 val = 2
Aktualisierung: l = 3 r = 4 val = 3
getRangeSum: l = 2 r = 4Ausgabe: Die Summe der Elemente im Bereich [2 4] beträgt 12
Erläuterung: Das Array wird nach der ersten Aktualisierung zu {2 2 2 2 2}.
Array nach der zweiten Aktualisierung wird zu {2 2 2 5 5}
Naiver Ansatz: Um das Problem zu lösen, befolgen Sie die folgende Idee:
Im vorheriger Beitrag Wir haben Bereichsaktualisierungs- und Punktabfragelösungen mithilfe von BIT besprochen.
rangeUpdate(l r val) : Wir fügen „val“ zum Element am Index „l“ hinzu. Wir subtrahieren „val“ vom Element am Index „r+1“.
getElement(index) [oder getSum()]: Wir geben die Summe der Elemente von 0 bis zum Index zurück, die mit BIT schnell ermittelt werden kann.
Wir können rangeSum() mithilfe von getSum()-Abfragen berechnen.
rangeSum(l r) = getSum(r) - getSum(l-1)Eine einfache Lösung besteht darin, die in der besprochenen Lösungen zu verwenden vorheriger Beitrag . Die Bereichsaktualisierungsabfrage ist dieselbe. Eine Bereichssummenabfrage kann durch eine Get-Abfrage für alle Elemente im Bereich erreicht werden.
Effizienter Ansatz: Um das Problem zu lösen, befolgen Sie die folgende Idee:
Wir erhalten die Bereichssumme mithilfe von Präfixsummen. Wie kann sichergestellt werden, dass die Aktualisierung so erfolgt, dass die Präfixsumme schnell durchgeführt werden kann? Stellen Sie sich eine Situation vor, in der die Präfixsumme [0 k] (wobei 0 <= k < n) is needed after range update on the range [l r]. Three cases arise as k can possibly lie in 3 regions.
- Fall 1 : 0 < k < l
- Die Aktualisierungsabfrage hat keinen Einfluss auf die Summenabfrage.
- Fall 2 :l <= k <= r
- Betrachten Sie ein Beispiel: Fügen Sie 2 zum Bereich [2 4] hinzu. Das resultierende Array wäre: 0 0 2 2 2
Wenn k = 3. Die Summe aus [0 k] = 4Wie kommt man zu diesem Ergebnis?
Fügen Sie einfach den Wert von l hinzu Th Index zu k Th Index. Die Summe wird nach der Aktualisierungsabfrage um „Wert*(k) – Wert*(l-1)“ erhöht.
- Fall 3 : k > r
- In diesem Fall müssen wir „val“ von l hinzufügen Th Index nach r Th Index. Die Summe wird aufgrund einer Aktualisierungsabfrage um „val*r – val*(l-1)“ erhöht.
Beobachtungen:
Fall 1: ist einfach, da die Summe die gleiche bleiben würde wie vor dem Update.
Fall 2: Die Summe wurde um val*k - val*(l-1) erhöht. Wir können „val“ finden, es ähnelt dem Finden des i Th Element in Artikel zur Bereichsaktualisierung und Punktabfrage . Daher verwalten wir ein BIT für Bereichsaktualisierungen und Punktabfragen. Dieses BIT wird bei der Ermittlung des Werts bei k hilfreich sein Th Index. Jetzt wird val * k berechnet. Wie wird mit dem zusätzlichen Term val*(l-1) umgegangen?
Um diesen zusätzlichen Begriff zu verwalten, unterhalten wir ein weiteres BIT (BIT2). Aktualisieren Sie val * (l-1) bei l Th Wenn also die getSum-Abfrage für BIT2 ausgeführt wird, wird das Ergebnis als val*(l-1) ausgegeben.
Fall 3: Die Summe im Fall 3 wurde um „val*r – val *(l-1)“ erhöht. Der Wert dieses Termes kann mit BIT2 ermittelt werden. Anstatt zu addieren, subtrahieren wir „val*(l-1) – val*r“, da wir diesen Wert aus BIT2 erhalten können, indem wir val*(l-1) addieren, wie wir es in Fall 2 getan haben, und val*r bei jedem Aktualisierungsvorgang subtrahieren.
Abfrage aktualisieren
Update(BITree1 l val)
Update(BITree1 r+1 -val)
UpdateBIT2(BITree2 l val*(l-1))
UpdateBIT2(BITree2 r+1 -val*r)Bereichssumme
getSum(BITTree1 k) *k) - getSum(BITTree2 k)
Befolgen Sie die folgenden Schritte, um das Problem zu lösen:
- Erstellen Sie die beiden binären Indexbäume mit der angegebenen Funktion constructionBITree()
- Um die Summe in einem bestimmten Bereich zu finden, rufen Sie die Funktion rangeSum() mit Parametern wie dem angegebenen Bereich und binär indizierten Bäumen auf
- Rufen Sie eine Funktion sum auf, die eine Summe im Bereich [0 X] zurückgibt.
- Rückgabesumme(R) - Summe(L-1)
- Rufen Sie innerhalb dieser Funktion die Funktion getSum() auf, die die Summe des Arrays von [0 X] zurückgibt.
- Rückgabe getSum(Tree1 x) * x - getSum(tree2 x)
- Erstellen Sie innerhalb der Funktion getSum() eine ganzzahlige Summe gleich Null und erhöhen Sie den Index um 1
- Während der Index größer als Null ist, erhöhen Sie die Summe um Tree[index]
- Verringern Sie den Index um (index & (-index)), um den Index zum übergeordneten Knoten im Baum zu verschieben
- Rückgabesumme
- Geben Sie die Summe im angegebenen Bereich aus
Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:
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# // 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 ( BITree index ) { 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 ( BITree n index 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] function sum ( x BITTree1 BITTree2 ) { return ( getSum ( BITTree1 x ) * x ) - getSum ( BITTree2 x ); } function updateRange ( BITTree1 BITTree2 n val l 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 ); } function rangeSum ( l r BITTree1 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 ); } 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>
Ausgabe
Sum of elements from [14] is 50
Zeitkomplexität : O(q * log(N)) wobei q die Anzahl der Abfragen ist.
Hilfsraum: AN)
