Étant donné un tableau arr[0..N-1]. Les opérations suivantes doivent être effectuées.
- mise à jour (l r val) : Ajoutez 'val' à tous les éléments du tableau à partir de [l r].
- getRangeSum(lr) : Trouvez la somme de tous les éléments du tableau à partir de [l r].
Initialement, tous les éléments du tableau valent 0. Les requêtes peuvent être dans n'importe quel ordre, c'est-à-dire qu'il peut y avoir de nombreuses mises à jour avant la somme de la plage.
Exemple:
Saisir: N = 5 // {0 0 0 0 0}
Requêtes : mise à jour : l = 0 r = 4 val = 2
mise à jour : l = 3 r = 4 val = 3
getRangeSum : l = 2 r = 4Sortir: La somme des éléments de la plage [2 4] est 12
Explication: Le tableau après la première mise à jour devient {2 2 2 2 2}
Le tableau après la deuxième mise à jour devient {2 2 2 5 5}
Approche naïve : Pour résoudre le problème, suivez l'idée ci-dessous :
Dans le message précédent nous avons discuté des solutions de mise à jour de gamme et de requête de points à l'aide de BIT.
rangeUpdate(l r val) : Nous ajoutons 'val' à l'élément à l'index 'l'. Nous soustrayons 'val' de l'élément à l'index 'r+1'.
getElement(index) [ou getSum()] : Nous renvoyons la somme des éléments de 0 à l'index qui peut être rapidement obtenue en utilisant BIT.
Nous pouvons calculer rangeSum() à l’aide de requêtes getSum().
rangeSum(l r) = getSum(r) - getSum(l-1)différence symétriqueUne solution simple est d'utiliser les solutions discutées dans le message précédent . La requête de mise à jour de plage est la même. La requête de somme de plage peut être réalisée en effectuant une requête get pour tous les éléments de la plage.
Approche efficace : Pour résoudre le problème, suivez l'idée ci-dessous :
Nous obtenons la somme de plage en utilisant les sommes de préfixes. Comment s'assurer que la mise à jour est effectuée de manière à ce que la somme des préfixes puisse être effectuée rapidement ? Considérons une situation où la somme des préfixes [0 k] (où 0<= k < n) is needed after range update on the range [l r]. Three cases arise as k can possibly lie in 3 regions.
- Cas 1 : 0< k < l
- La requête de mise à jour n’affectera pas la requête de somme.
- Cas 2 : je<= k <= r
- Prenons un exemple : Ajoutez 2 à la plage [2 4], le tableau résultant serait : 0 0 2 2 2
Si k = 3 La somme de [0 k] = 4Comment obtenir ce résultat ?
Ajoutez simplement le val de lèmeindice à kèmeindice. La somme est incrémentée de 'val*(k) - val*(l-1)' après la requête de mise à jour.
- Cas 3 : k > r
- Dans ce cas, nous devons ajouter 'val' de lèmeindex à rèmeindice. La somme est incrémentée de « val*r – val*(l-1) » en raison d'une requête de mise à jour.
Observations :
Cas 1 : C'est simple car la somme resterait la même qu'avant la mise à jour.
Cas 2 : La somme a été incrémentée de val*k - val*(l-1). Nous pouvons trouver 'val', c'est similaire à trouver le ièmeélément dans article sur la mise à jour de la plage et la requête de points . Nous maintenons donc un BIT pour la mise à jour de plage et les requêtes de points. Ce BIT sera utile pour trouver la valeur à k.èmeindice. Maintenant, val * k est calculé, comment gérer le terme supplémentaire val*(l-1) ?
Afin de gérer ce terme supplémentaire, nous maintenons un autre BIT (BIT2). Mettre à jour val * (l-1) à lèmeindex donc lorsque la requête getSum est effectuée sur BIT2, elle donnera le résultat val*(l-1).
Cas 3 : La somme dans le cas 3 a été incrémentée de 'val*r - val *(l-1)', la valeur de ce terme peut être obtenue en utilisant BIT2. Au lieu d'ajouter, nous soustrayons 'val*(l-1) - val*r' car nous pouvons obtenir cette valeur de BIT2 en ajoutant val*(l-1) comme nous l'avons fait dans le cas 2 et en soustrayant val*r à chaque opération de mise à jour.
Mettre à jour la requête
Mise à jour (BITree1 l val)
Mise à jour (BITree1 r+1 -val)
Mise à jourBIT2(BITree2 l val*(l-1))
Mise à jourBIT2(BITree2 r+1 -val*r)Somme de plage
getSum(BITTree1 k) *k) - getSum(BITTree2 k)
Suivez les étapes ci-dessous pour résoudre le problème :
- Créez les deux arbres d'index binaires en utilisant la fonction donnée constructBITree()
- Pour trouver la somme dans une plage donnée, appelez la fonction rangeSum() avec des paramètres comme la plage donnée et des arbres indexés binaires
- Appelez une fonction sum qui renverra une somme dans la plage [0 X]
- Renvoie somme(R) - somme(L-1)
- A l'intérieur de cette fonction, appelez la fonction getSum() qui renverra la somme du tableau de [0 X]
- Retourner getSum(Tree1 x) * x - getSum(tree2 x)
- Dans la fonction getSum(), créez une somme entière égale à zéro et augmentez l'index de 1
- Tant que l'indice est supérieur à zéro, augmentez la somme de Tree[index]
- Diminuez l'index de (index & (-index)) pour déplacer l'index vers le nœud parent dans l'arborescence
- Somme de retour
- Imprimer la somme dans la plage donnée
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
exécuter le shell de scriptC++
// 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>
Sortir
Sum of elements from [14] is 50
Complexité temporelle : O(q * log(N)) où q est le nombre de requêtes.
Espace auxiliaire : SUR)