Binarne drzewo indeksowane: aktualizacje zakresów i zapytania o punkty
Biorąc pod uwagę tablicę arr[0..n-1]. Należy wykonać następujące operacje.
Początkowo wszystkie elementy tablicy mają wartość 0. Kolejność zapytań może być dowolna, tzn. przed zapytaniem punktowym może nastąpić wiele aktualizacji.
Przykład:
Input: arr = {0 0 0 0 0} Queries: update : l = 0 r = 4 val = 2 getElement : i = 3 update : l = 3 r = 4 val = 3 getElement : i = 3 Output: Element at 3 is 2 Element at 3 is 5 Explanation: Array after first update becomes {2 2 2 2 2} Array after second update becomes {2 2 2 5 5} Metoda 1 [aktualizacja: O(n) getElement(): O(1)]
Złożoność czasowa w najgorszym przypadku wynosi O(q*n), gdzie q to liczba zapytań, a n to liczba elementów.
Metoda 2 [aktualizacja: O(1) getElement(): O(n)]
Możemy uniknąć aktualizacji wszystkich elementów i możemy zaktualizować tylko 2 indeksy tablicy!
arr[l] = arr[l] + val arr[r+1] = arr[r+1] - val
Przeanalizujmy zapytanie o aktualizację. Po co dodawać val do l t indeks? Dodanie val do l t indeks oznacza, że wszystkie elementy po l są zwiększane o val, ponieważ będziemy obliczać sumę przedrostków dla każdego elementu. Dlaczego odejmować val od (r+1) t indeks? Wymagana była aktualizacja zakresu z [lr], ale zaktualizowaliśmy [l n-1], więc musimy usunąć val ze wszystkich elementów po r, tj. odjąć val od (r+1) t indeks. W ten sposób wartość val jest dodawana do zakresu [lr]. Poniżej implementacja powyższego podejścia.
C++ // C++ program to demonstrate Range Update // and Point Queries Without using BIT #include using namespace std ; // Updates such that getElement() gets an increased // value when queried from l to r. void update ( int arr [] int l int r int val ) { arr [ l ] += val ; arr [ r + 1 ] -= val ; } // Get the element indexed at i int getElement ( int arr [] int i ) { // To get ith element sum of all the elements // from 0 to i need to be computed int res = 0 ; for ( int j = 0 ; j <= i ; j ++ ) res += arr [ j ]; return res ; } // Driver program to test above function int main () { int arr [] = { 0 0 0 0 0 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); int l = 2 r = 4 val = 2 ; update ( arr l r val ); //Find the element at Index 4 int index = 4 ; cout < < 'Element at index ' < < index < < ' is ' < < getElement ( arr index ) < < endl ; l = 0 r = 3 val = 4 ; update ( arr l r val ); //Find the element at Index 3 index = 3 ; cout < < 'Element at index ' < < index < < ' is ' < < getElement ( arr index ) < < endl ; return 0 ; }
Java // Java program to demonstrate Range Update // and Point Queries Without using BIT class GfG { // Updates such that getElement() gets an increased // value when queried from l to r. static void update ( int arr [] int l int r int val ) { arr [ l ] += val ; if ( r + 1 < arr . length ) arr [ r + 1 ] -= val ; } // Get the element indexed at i static int getElement ( int arr [] int i ) { // To get ith element sum of all the elements // from 0 to i need to be computed int res = 0 ; for ( int j = 0 ; j <= i ; j ++ ) res += arr [ j ] ; return res ; } // Driver program to test above function public static void main ( String [] args ) { int arr [] = { 0 0 0 0 0 }; int n = arr . length ; int l = 2 r = 4 val = 2 ; update ( arr l r val ); //Find the element at Index 4 int index = 4 ; System . out . println ( 'Element at index ' + index + ' is ' + getElement ( arr index )); l = 0 ; r = 3 ; val = 4 ; update ( arr l r val ); //Find the element at Index 3 index = 3 ; System . out . println ( 'Element at index ' + index + ' is ' + getElement ( arr index )); } }
Python3 # Python3 program to demonstrate Range # Update and PoQueries Without using BIT # Updates such that getElement() gets an # increased value when queried from l to r. def update ( arr l r val ): arr [ l ] += val if r + 1 < len ( arr ): arr [ r + 1 ] -= val # Get the element indexed at i def getElement ( arr i ): # To get ith element sum of all the elements # from 0 to i need to be computed res = 0 for j in range ( i + 1 ): res += arr [ j ] return res # Driver Code if __name__ == '__main__' : arr = [ 0 0 0 0 0 ] n = len ( arr ) l = 2 r = 4 val = 2 update ( arr l r val ) # Find the element at Index 4 index = 4 print ( 'Element at index' index 'is' getElement ( arr index )) l = 0 r = 3 val = 4 update ( arr l r val ) # Find the element at Index 3 index = 3 print ( 'Element at index' index 'is' getElement ( arr index )) # This code is contributed by PranchalK
C# // C# program to demonstrate Range Update // and Point Queries Without using BIT using System ; class GfG { // Updates such that getElement() // gets an increased value when // queried from l to r. static void update ( int [] arr int l int r int val ) { arr [ l ] += val ; if ( r + 1 < arr . Length ) arr [ r + 1 ] -= val ; } // Get the element indexed at i static int getElement ( int [] arr int i ) { // To get ith element sum of all the elements // from 0 to i need to be computed int res = 0 ; for ( int j = 0 ; j <= i ; j ++ ) res += arr [ j ]; return res ; } // Driver code public static void Main ( String [] args ) { int [] arr = { 0 0 0 0 0 }; int n = arr . Length ; int l = 2 r = 4 val = 2 ; update ( arr l r val ); //Find the element at Index 4 int index = 4 ; Console . WriteLine ( 'Element at index ' + index + ' is ' + getElement ( arr index )); l = 0 ; r = 3 ; val = 4 ; update ( arr l r val ); //Find the element at Index 3 index = 3 ; Console . WriteLine ( 'Element at index ' + index + ' is ' + getElement ( arr index )); } } // This code is contributed by PrinciRaj1992
PHP // PHP program to demonstrate Range Update // and Point Queries Without using BIT // Updates such that getElement() gets an // increased value when queried from l to r. function update ( & $arr $l $r $val ) { $arr [ $l ] += $val ; if ( $r + 1 < sizeof ( $arr )) $arr [ $r + 1 ] -= $val ; } // Get the element indexed at i function getElement ( & $arr $i ) { // To get ith element sum of all the elements // from 0 to i need to be computed $res = 0 ; for ( $j = 0 ; $j <= $i ; $j ++ ) $res += $arr [ $j ]; return $res ; } // Driver Code $arr = array ( 0 0 0 0 0 ); $n = sizeof ( $arr ); $l = 2 ; $r = 4 ; $val = 2 ; update ( $arr $l $r $val ); // Find the element at Index 4 $index = 4 ; echo ( 'Element at index ' . $index . ' is ' . getElement ( $arr $index ) . ' n ' ); $l = 0 ; $r = 3 ; $val = 4 ; update ( $arr $l $r $val ); // Find the element at Index 3 $index = 3 ; echo ( 'Element at index ' . $index . ' is ' . getElement ( $arr $index )); // This code is contributed by Code_Mech ?>
JavaScript //JavaScript program to demonstrate Range Update // and Point Queries Without using BIT // Updates such that getElement() gets an increased // value when queried from l to r. function update ( arr l r val ) { arr [ l ] += val ; arr [ r + 1 ] -= val ; } // Get the element indexed at i function getElement ( rr i ) { // To get ith element sum of all the elements // from 0 to i need to be computed let res = 0 ; for ( let j = 0 ; j <= i ; j ++ ) res += arr [ j ]; return res ; } // Driver program to test above function let arr = [ 0 0 0 0 0 ]; let n = arr . length ; let l = 2 r = 4 val = 2 ; update ( arr l r val ); // Find the element at Index 4 let index = 4 ; console . log ( 'Element at index ' index ' is ' getElement ( arr index )); l = 0 r = 3 val = 4 ; update ( arr l r val ); // Find the element at Index 3 index = 3 ; console . log ( 'Element at index ' index ' is ' getElement ( arr index )); // This code is contributed by vikkycirus
Wyjście:
Element at index 4 is 2 Element at index 3 is 6
Złożoność czasowa : O(q*n) gdzie q to liczba zapytań.
Przestrzeń pomocnicza: NA)
Metoda 3 (przy użyciu drzewa indeksowanego binarnie)
W metodzie 2 widzieliśmy, że problem można ograniczyć do zapytań o aktualizację i sumę prefiksów. Widzieliśmy to BIT może być używany do wykonywania zapytań o aktualizację i sumę prefiksów w czasie O (Logn). Poniżej realizacja.
C++ // C++ code to demonstrate Range Update and // Point Queries on a Binary Index Tree #include using namespace std ; // 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 ); } } // Constructs and returns a Binary Indexed Tree for given // array of size n. int * constructBITree ( int arr [] int n ) { // Create and initialize BITree[] as 0 int * BITree = new int [ n + 1 ]; for ( int i = 1 ; i <= n ; i ++ ) BITree [ i ] = 0 ; // Store the actual values in BITree[] using update() for ( int i = 0 ; i < n ; i ++ ) updateBIT ( BITree n i arr [ i ]); // Uncomment below lines to see contents of BITree[] //for (int i=1; i <=n; i++) // cout < < BITree[i] < < ' '; return BITree ; } // SERVES THE PURPOSE OF getElement() // 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 such that getElement() gets an increased // value when queried from l to r. void update ( int BITree [] int l int r int n int val ) { // Increase value at 'l' by 'val' updateBIT ( BITree n l val ); // Decrease value at 'r+1' by 'val' updateBIT ( BITree n r + 1 - val ); } // Driver program to test above function int main () { int arr [] = { 0 0 0 0 0 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); int * BITree = constructBITree ( arr n ); // Add 2 to all the element from [24] int l = 2 r = 4 val = 2 ; update ( BITree l r n val ); // Find the element at Index 4 int index = 4 ; cout < < 'Element at index ' < < index < < ' is ' < < getSum ( BITree index ) < < ' n ' ; // Add 2 to all the element from [03] l = 0 r = 3 val = 4 ; update ( BITree l r n val ); // Find the element at Index 3 index = 3 ; cout < < 'Element at index ' < < index < < ' is ' < < getSum ( BITree index ) < < ' n ' ; return 0 ; }
Java /* Java code to demonstrate Range Update and * Point Queries on a Binary Index Tree. * This method only works when all array * values are initially 0.*/ class GFG { // Max tree size final static int MAX = 1000 ; static int BITree [] = new int [ MAX ] ; // 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. public static void updateBIT ( 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 BITree BITree [ index ] += val ; // Update index to that // of parent in update View index += index & ( - index ); } } // Constructs Binary Indexed Tree // for given array of size n. public static void constructBITree ( int arr [] int n ) { // Initialize BITree[] as 0 for ( int i = 1 ; i <= n ; i ++ ) BITree [ i ] = 0 ; // Store the actual values // in BITree[] using update() for ( int i = 0 ; i < n ; i ++ ) updateBIT ( n i arr [ i ] ); // Uncomment below lines to // see contents of BITree[] // for (int i=1; i <=n; i++) // cout < < BITree[i] < < ' '; } // SERVES THE PURPOSE OF getElement() // Returns sum of arr[0..index]. This // function assumes that the array is // preprocessed and partial sums of // array elements are stored in BITree[] public static int getSum ( 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 the sum return sum ; } // Updates such that getElement() // gets an increased value when // queried from l to r. public static void update ( int l int r int n int val ) { // Increase value at // 'l' by 'val' updateBIT ( n l val ); // Decrease value at // 'r+1' by 'val' updateBIT ( n r + 1 - val ); } // Driver Code public static void main ( String args [] ) { int arr [] = { 0 0 0 0 0 }; int n = arr . length ; constructBITree ( arr n ); // Add 2 to all the // element from [24] int l = 2 r = 4 val = 2 ; update ( l r n val ); int index = 4 ; System . out . println ( 'Element at index ' + index + ' is ' + getSum ( index )); // Add 2 to all the // element from [03] l = 0 ; r = 3 ; val = 4 ; update ( l r n val ); // Find the element // at Index 3 index = 3 ; System . out . println ( 'Element at index ' + index + ' is ' + getSum ( index )); } } // This code is contributed // by Puneet Kumar.
Python3 # Python3 code to demonstrate Range Update and # PoQueries on a Binary Index Tree # 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 ( 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 ) # Constructs and returns a Binary Indexed Tree for given # array of size n. def constructBITree ( arr n ): # Create and initialize BITree[] as 0 BITree = [ 0 ] * ( n + 1 ) # Store the actual values in BITree[] using update() for i in range ( n ): updateBIT ( BITree n i arr [ i ]) return BITree # SERVES THE PURPOSE OF getElement() # 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 index ): 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 such that getElement() gets an increased # value when queried from l to r. def update ( BITree l r n val ): # Increase value at 'l' by 'val' updateBIT ( BITree n l val ) # Decrease value at 'r+1' by 'val' updateBIT ( BITree n r + 1 - val ) # Driver code arr = [ 0 0 0 0 0 ] n = len ( arr ) BITree = constructBITree ( arr n ) # Add 2 to all the element from [24] l = 2 r = 4 val = 2 update ( BITree l r n val ) # Find the element at Index 4 index = 4 print ( 'Element at index' index 'is' getSum ( BITree index )) # Add 2 to all the element from [03] l = 0 r = 3 val = 4 update ( BITree l r n val ) # Find the element at Index 3 index = 3 print ( 'Element at index' index 'is' getSum ( BITree index )) # This code is contributed by mohit kumar 29
C# using System ; /* C# code to demonstrate Range Update and * Point Queries on a Binary Index Tree. * This method only works when all array * values are initially 0.*/ public class GFG { // Max tree size public const int MAX = 1000 ; public static int [] BITree = new int [ MAX ]; // 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. public static void updateBIT ( 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 BITree BITree [ index ] += val ; // Update index to that // of parent in update View index += index & ( - index ); } } // Constructs Binary Indexed Tree // for given array of size n. public static void constructBITree ( int [] arr int n ) { // Initialize BITree[] as 0 for ( int i = 1 ; i <= n ; i ++ ) { BITree [ i ] = 0 ; } // Store the actual values // in BITree[] using update() for ( int i = 0 ; i < n ; i ++ ) { updateBIT ( n i arr [ i ]); } // Uncomment below lines to // see contents of BITree[] // for (int i=1; i <=n; i++) // cout < < BITree[i] < < ' '; } // SERVES THE PURPOSE OF getElement() // Returns sum of arr[0..index]. This // function assumes that the array is // preprocessed and partial sums of // array elements are stored in BITree[] public static int getSum ( 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 the sum return sum ; } // Updates such that getElement() // gets an increased value when // queried from l to r. public static void update ( int l int r int n int val ) { // Increase value at // 'l' by 'val' updateBIT ( n l val ); // Decrease value at // 'r+1' by 'val' updateBIT ( n r + 1 - val ); } // Driver Code public static void Main ( string [] args ) { int [] arr = new int [] { 0 0 0 0 0 }; int n = arr . Length ; constructBITree ( arr n ); // Add 2 to all the // element from [24] int l = 2 r = 4 val = 2 ; update ( l r n val ); int index = 4 ; Console . WriteLine ( 'Element at index ' + index + ' is ' + getSum ( index )); // Add 2 to all the // element from [03] l = 0 ; r = 3 ; val = 4 ; update ( l r n val ); // Find the element // at Index 3 index = 3 ; Console . WriteLine ( 'Element at index ' + index + ' is ' + getSum ( index )); } } // This code is contributed by Shrikant13
JavaScript // 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 ); } } // Constructs and returns a Binary Indexed Tree for given // array of size n. function constructBITree ( arr n ) { // Create and initialize BITree[] as 0 let BITree = new Array ( n + 1 ). fill ( 0 ); // Store the actual values in BITree[] using update() for ( let i = 0 ; i < n ; i ++ ) { updateBIT ( BITree n i arr [ i ]); } return BITree ; } // SERVES THE PURPOSE OF getElement() // 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 such that getElement() gets an increased // value when queried from l to r. function update ( BITree l r n val ) { // Increase value at 'l' by 'val' updateBIT ( BITree n l val ); // Decrease value at 'r+1' by 'val' updateBIT ( BITree n r + 1 - val ); } // Test the functions let arr = [ 0 0 0 0 0 ]; let n = arr . length ; let BITree = constructBITree ( arr n ); // Add 2 to all the element from [24] let l = 2 r = 4 val = 2 ; update ( BITree l r n val ); // Find the element at Index 4 let index = 4 ; console . log ( `Element at index ${ index } is ${ getSum ( BITree index ) } ` ); // Add 2 to all the element from [03] l = 0 r = 3 val = 4 ; update ( BITree l r n val ); // Find the element at Index 3 index = 3 ; console . log ( `Element at index ${ index } is ${ getSum ( BITree index ) } ` );
Wyjście:
Element at index 4 is 2 Element at index 3 is 6
Złożoność czasowa: O(q * log n) + O(n * log n) gdzie q to liczba zapytań.
Przestrzeń pomocnicza: NA)
Metoda 1 jest skuteczna, gdy większość zapytań to getElement(), metoda 2 jest skuteczna, gdy większość zapytań to aktualizacje(), a metoda 3 jest preferowana, gdy oba zapytania są mieszane.
Może Ci Się Spodobać
Najpopularniejsze Artykuły
