Бинарно индексирано стабло: ажурирања опсега и упити за тачке
Дат низ арр[0..н-1]. Потребно је извршити следеће операције.
У почетку су сви елементи у низу 0. Упити могу бити у било ком редоследу, тј. може бити много ажурирања пре упита тачке.
Пример:
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} Метод 1 [ажурирање: О(н) гетЕлемент(): О(1)]
Временска сложеност у најгорем случају је О(к*н) где је к број упита, а н број елемената.
Метод 2 [ажурирање: О(1) гетЕлемент(): О(н)]
Можемо избећи ажурирање свих елемената и можемо ажурирати само 2 индекса низа!
arr[l] = arr[l] + val arr[r+1] = arr[r+1] - val
Хајде да анализирамо упит за ажурирање. Зашто додати вал на л тх индекс? Додавање вал у л тх индекс значи да су сви елементи после л увећани за вал пошто ћемо израчунати збир префикса за сваки елемент. Зашто одузимати вал од (р+1) тх индекс? Ажурирање опсега је било потребно од [лр], али оно што смо ажурирали је [л н-1], тако да морамо уклонити вал из свих елемената након р, тј. одузети вал од (р+1) тх индекс. Тако се вал додаје опсегу [лр]. Испод је примена горе наведеног приступа.
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
Излаз:
Element at index 4 is 2 Element at index 3 is 6
Временска сложеност : О(к*н) где је к број упита.
Помоћни простор: О(н)
Метод 3 (користећи бинарно индексирано стабло)
У методу 2 видели смо да се проблем може свести на упите за ажурирање и збир префикса. То смо видели БИТ се може користити за ажурирање и упите за збир префикса у О(Логн) времену. Испод је имплементација.
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 ) } ` );
Излаз:
Element at index 4 is 2 Element at index 3 is 6
Временска сложеност: О(к * лог н) + О(н * лог н) где је к број упита.
Помоћни простор: О(н)
Метод 1 је ефикасан када је већина упита гетЕлемент() метода 2 је ефикасна када је већина упита упдатес(), а метод 3 је пожељнији када постоји мешавина оба упита.
Можда Ће Вам Се Свидети
Топ Чланци
