İkili Dizinli Ağaç: Aralık Güncellemeleri ve Nokta Sorguları
Bir dizi verildiğinde arr[0..n-1] Aşağıdaki işlemlerin yapılması gerekmektedir.
Başlangıçta dizideki tüm öğeler 0'dır. Sorgular herhangi bir sırada olabilir, yani nokta sorgusundan önce birçok güncelleme olabilir.
Örnek:
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} Yöntem 1 [güncelleme: O(n) getElement() : O(1)]
En kötü durumda zaman karmaşıklığı O(q*n)'dir; burada q, sorgu sayısı ve n, öğe sayısıdır.
Yöntem 2 [güncelleme: O(1) getElement(): O(n)]
Tüm öğeleri güncellemekten kaçınabiliriz ve dizinin yalnızca 2 dizinini güncelleyebiliriz!
arr[l] = arr[l] + val arr[r+1] = arr[r+1] - val
Güncelleme sorgusunu analiz edelim. Neden l'ye val eklenmeli? o indeks? l'ye val ekleme o indeks, her öğe için önek toplamını hesaplayacağımız için l'den sonraki tüm öğelerin val ile artırıldığı anlamına gelir. Neden val'i (r+1)'den çıkarmalı? o indeks? [lr]'den bir aralık güncellemesi gerekiyordu, ancak güncellediğimiz şey [l n-1], bu yüzden ri'den sonra val'i tüm öğelerden kaldırmamız gerekiyor, yani val'i (r+1)'den çıkarmalıyız. o indeks. Böylece val, [lr] aralığına eklenir. Aşağıda yukarıdaki yaklaşımın uygulanması yer almaktadır.
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
Çıkış:
Element at index 4 is 2 Element at index 3 is 6
Zaman karmaşıklığı : O(q*n) burada q sorgu sayısıdır.
Yardımcı Alan: Açık)
Yöntem 3 (İkili Dizine Alınmış Ağacı Kullanma)
Yöntem 2'de sorunun güncelleme ve önek toplamı sorgularına indirgenebileceğini gördük. Bunu gördük BIT, O(Logn) zamanında toplam sorguları güncellemek ve önek yapmak için kullanılabilir. Aşağıda uygulaması yer almaktadır.
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 ) } ` );
Çıkış:
Element at index 4 is 2 Element at index 3 is 6
Zaman Karmaşıklığı: O(q * log n) + O(n * log n) burada q, sorgu sayısıdır.
Yardımcı Alan: Açık)
Yöntem 1, sorguların çoğu getElement() olduğunda etkilidir. Yöntem 2, sorguların çoğu update() olduğunda etkilidir ve her iki sorgunun karışımı olduğunda yöntem 3 tercih edilir.
Hoşunuza Gidebilir
En Makaleler
