Dada una array A[ ] que consta de enteros no negativos y una array Q[ ][ ] que consta de consultas de los siguientes dos tipos:
- (1, l, val): actualice A[l] a A[l] + val .
- (2, K): encuentre el límite inferior de K en la array de suma de prefijos de A[ ] . Si el límite_inferior no existe, imprima -1.
La tarea para cada consulta del segundo tipo es imprimir el índice del límite inferior del valor K.
Ejemplos:
Entrada: A[ ] = {1, 2, 3, 5, 8}, Q[ ][ ] = {{1, 0, 2}, {2, 5}, {1, 3, 5}}
Salida: 1
Explicación:
Consulta 1: actualice A[0] a A[0] + 2. Ahora A[ ] = {3, 2, 3, 5, 8}
Consulta 2: límite inferior de K = 5 en la array de suma de prefijos {3, 5, 8, 13, 21} es 5 e índice = 1.
Consulta 3: actualice A[3] a A[3] + 5. Ahora A[ ] = {3, 2, 3, 10, 8}Entrada: A[ ] = {4, 1, 12, 8, 20}, Q[ ] = {{2, 50}, {1, 3, 12}, {2, 50}}
Salida: -1
Enfoque ingenuo:
el enfoque más simple es construir primero una array de suma de prefijos de una array dada A[ ], y para consultas de Tipo 1 , actualizar valores y volver a calcular la suma de prefijos. Para consultas de tipo 2 , realice una búsqueda binaria en la array de suma de prefijos para encontrar el límite inferior .
Complejidad de tiempo: O(Q*(N*logn))
Espacio auxiliar: O(N)
Enfoque eficiente:
El enfoque anterior se puede optimizar Fenwick Tree . Con esta estructura de datos , las consultas de actualización en la array de suma de prefijos se pueden realizar en tiempo logarítmico.
Siga los pasos a continuación para resolver el problema:
- Construya la array de suma de prefijos utilizando Fenwick Tree.
- Para consultas de Tipo 1 , mientras que l > 0 , agregue val a A[l] transversal al Node principal agregando el bit menos significativo en l .
- Para consultas de tipo 2 , realice la búsqueda binaria en el árbol de Fenwick para obtener el límite inferior.
- Siempre que aparezca una suma de prefijos mayor que K , almacene ese índice y recorra la parte izquierda del árbol de Fenwick. De lo contrario, atraviese la parte derecha del Fenwick Tree ahora, realice una búsqueda binaria .
- Finalmente, imprima el índice requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate and return // the sum of arr[0..index] int getSum(int BITree[], int index) { int ans = 0; index += 1; // Traverse ancestors // of BITree[index] while (index > 0) { // Update the sum of current // element of BIT to ans ans += BITree[index]; // Update index to that // of the parent node in // getSum() view by // subtracting LSB(Least // Significant Bit) index -= index & (-index); } return ans; } // Function to update the Binary Index // Tree by replacing all ancestors of // index by their respective sum with val static void updateBIT(int BITree[], int n, int index, int val) { index = index + 1; // Traverse all ancestors // and sum with 'val'. while (index <= n) { // Add 'val' to current // node of BIT BITree[index] += val; // Update index to that // of the parent node in // updateBit() view by // adding LSB(Least // Significant Bit) index += index & (-index); } } // Function to construct the Binary // Indexed Tree for the given array int* constructBITree(int arr[], int n) { // Initialize the // Binary Indexed Tree int* BITree = new int[n + 1]; for(int i = 0; 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]); return BITree; } // Function to obtain and return // the index of lower_bound of k int getLowerBound(int BITree[], int arr[], int n, int k) { int lb = -1; int l = 0, r = n - 1; while (l <= r) { int mid = l + (r - l) / 2; if (getSum(BITree, mid) >= k) { r = mid - 1; lb = mid; } else l = mid + 1; } return lb; } void performQueries(int A[], int n, int q[][3]) { // Store the Binary Indexed Tree int* BITree = constructBITree(A, n); // Solve each query in Q for(int i = 0; i < sizeof(q[0]) / sizeof(int); i++) { int id = q[i][0]; if (id == 1) { int idx = q[i][1]; int val = q[i][2]; A[idx] += val; // Update the values of all // ancestors of idx updateBIT(BITree, n, idx, val); } else { int k = q[i][1]; int lb = getLowerBound(BITree, A, n, k); cout << lb << endl; } } } // Driver Code int main() { int A[] = { 1, 2, 3, 5, 8 }; int n = sizeof(A) / sizeof(int); int q[][3] = { { 1, 0, 2 }, { 2, 5, 0 }, { 1, 3, 5 } }; performQueries(A, n, q); } // This code is contributed by jrishabh99
Java
// Java program to implement // the above approach import java.util.*; import java.io.*; class GFG { // Function to calculate and return // the sum of arr[0..index] static int getSum(int BITree[], int index) { int ans = 0; index += 1; // Traverse ancestors // of BITree[index] while (index > 0) { // Update the sum of current // element of BIT to ans ans += BITree[index]; // Update index to that // of the parent node in // getSum() view by // subtracting LSB(Least // Significant Bit) index -= index & (-index); } return ans; } // Function to update the Binary Index // Tree by replacing all ancestors of // index by their respective sum with val static void updateBIT(int BITree[], int n, int index, int val) { index = index + 1; // Traverse all ancestors // and sum with 'val'. while (index <= n) { // Add 'val' to current // node of BIT BITree[index] += val; // Update index to that // of the parent node in // updateBit() view by // adding LSB(Least // Significant Bit) index += index & (-index); } } // Function to construct the Binary // Indexed Tree for the given array static int[] constructBITree( int arr[], int n) { // Initialize the // Binary Indexed Tree int[] BITree = new int[n + 1]; for (int i = 0; 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]); return BITree; } // Function to obtain and return // the index of lower_bound of k static int getLowerBound(int BITree[], int[] arr, int n, int k) { int lb = -1; int l = 0, r = n - 1; while (l <= r) { int mid = l + (r - l) / 2; if (getSum(BITree, mid) >= k) { r = mid - 1; lb = mid; } else l = mid + 1; } return lb; } static void performQueries(int A[], int n, int q[][]) { // Store the Binary Indexed Tree int[] BITree = constructBITree(A, n); // Solve each query in Q for (int i = 0; i < q.length; i++) { int id = q[i][0]; if (id == 1) { int idx = q[i][1]; int val = q[i][2]; A[idx] += val; // Update the values of all // ancestors of idx updateBIT(BITree, n, idx, val); } else { int k = q[i][1]; int lb = getLowerBound( BITree, A, n, k); System.out.println(lb); } } } // Driver Code public static void main(String[] args) { int A[] = { 1, 2, 3, 5, 8 }; int n = A.length; int[][] q = { { 1, 0, 2 }, { 2, 5 }, { 1, 3, 5 } }; performQueries(A, n, q); } }
Python3
# Python3 program to implement # the above approach # Function to calculate and return # the sum of arr[0..index] def getSum(BITree, index): ans = 0 index += 1 # Traverse ancestors # of BITree[index] while (index > 0): # Update the sum of current # element of BIT to ans ans += BITree[index] # Update index to that # of the parent node in # getSum() view by # subtracting LSB(Least # Significant Bit) index -= index & (-index) return ans # Function to update the # Binary Index Tree by # replacing all ancestors # of index by their respective # sum with val def updateBIT(BITree, n, index, val): index = index + 1 # Traverse all ancestors # and sum with 'val'. while (index <= n): # Add 'val' to current # node of BIT BITree[index] += val # Update index to that # of the parent node in # updateBit() view by # adding LSB(Least # Significant Bit) index += index & (-index) # Function to construct the Binary # Indexed Tree for the given array def constructBITree(arr, n): # Initialize the # Binary Indexed Tree BITree = [0] * (n + 1) for i in range(n + 1): BITree[i] = 0 # Store the actual values in # BITree[] using update() for i in range(n): updateBIT(BITree, n, i, arr[i]) return BITree # Function to obtain and return # the index of lower_bound of k def getLowerBound(BITree, arr, n, k): lb = -1 l = 0 r = n - 1 while (l <= r): mid = l + (r - l) // 2 if (getSum(BITree, mid) >= k): r = mid - 1 lb = mid else: l = mid + 1 return lb def performQueries(A, n, q): # Store the Binary Indexed Tree BITree = constructBITree(A, n) # Solve each query in Q for i in range(len(q)): id = q[i][0] if (id == 1): idx = q[i][1] val = q[i][2] A[idx] += val # Update the values of all # ancestors of idx updateBIT(BITree, n, idx, val) else: k = q[i][1] lb = getLowerBound(BITree, A, n, k) print(lb) # Driver Code if __name__ == "__main__": A = [1, 2, 3, 5, 8] n = len(A) q = [[1, 0, 2], [2, 5, 0], [1, 3, 5]] performQueries(A, n, q) # This code is contributed by Chitranayal
C#
// C# program to implement // the above approach using System; class GFG{ // Function to calculate and return // the sum of arr[0..index] static int getSum(int []BITree, int index) { int ans = 0; index += 1; // Traverse ancestors // of BITree[index] while (index > 0) { // Update the sum of current // element of BIT to ans ans += BITree[index]; // Update index to that // of the parent node in // getSum() view by // subtracting LSB(Least // Significant Bit) index -= index & (-index); } return ans; } // Function to update the Binary Index // Tree by replacing all ancestors of // index by their respective sum with val static void updateBIT(int []BITree, int n, int index, int val) { index = index + 1; // Traverse all ancestors // and sum with 'val'. while (index <= n) { // Add 'val' to current // node of BIT BITree[index] += val; // Update index to that // of the parent node in // updateBit() view by // adding LSB(Least // Significant Bit) index += index & (-index); } } // Function to construct the Binary // Indexed Tree for the given array static int[] constructBITree(int []arr, int n) { // Initialize the // Binary Indexed Tree int[] BITree = new int[n + 1]; for(int i = 0; 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]); return BITree; } // Function to obtain and return // the index of lower_bound of k static int getLowerBound(int []BITree, int[] arr, int n, int k) { int lb = -1; int l = 0, r = n - 1; while (l <= r) { int mid = l + (r - l) / 2; if (getSum(BITree, mid) >= k) { r = mid - 1; lb = mid; } else l = mid + 1; } return lb; } static void performQueries(int []A, int n, int [,]q) { // Store the Binary Indexed Tree int[] BITree = constructBITree(A, n); // Solve each query in Q for(int i = 0; i < q.GetLength(0); i++) { int id = q[i, 0]; if (id == 1) { int idx = q[i, 1]; int val = q[i, 2]; A[idx] += val; // Update the values of all // ancestors of idx updateBIT(BITree, n, idx, val); } else { int k = q[i, 1]; int lb = getLowerBound(BITree, A, n, k); Console.WriteLine(lb); } } } // Driver Code public static void Main(String[] args) { int []A = { 1, 2, 3, 5, 8 }; int n = A.Length; int [,]q = { { 1, 0, 2 }, { 2, 5, 0 }, { 1, 3, 5 } }; performQueries(A, n, q); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript program to implement // the above approach // Function to calculate and return // the sum of arr[0..index] function getSum(BITree, index) { let ans = 0; index += 1; // Traverse ancestors // of BITree[index] while (index > 0) { // Update the sum of current // element of BIT to ans ans += BITree[index]; // Update index to that // of the parent node in // getSum() view by // subtracting LSB(Least // Significant Bit) index -= index & (-index); } return ans; } // Function to update the Binary Index // Tree by replacing all ancestors of // index by their respective sum with val function updateBIT(BITree, n, index, val) { index = index + 1; // Traverse all ancestors // and sum with 'val'. while (index <= n) { // Add 'val' to current // node of BIT BITree[index] += val; // Update index to that // of the parent node in // updateBit() view by // adding LSB(Least // Significant Bit) index += index & (-index); } } // Function to construct the Binary // Indexed Tree for the given array function constructBITree(arr, n) { // Initialize the // Binary Indexed Tree let BITree = new Array(n + 1); for (let i = 0; i <= n; i++) BITree[i] = 0; // Store the actual values in // BITree[] using update() for (let i = 0; i < n; i++) updateBIT(BITree, n, i, arr[i]); return BITree; } // Function to obtain and return // the index of lower_bound of k function getLowerBound(BITree, arr, n, k) { let lb = -1; let l = 0, r = n - 1; while (l <= r) { let mid = Math.floor(l + (r - l) / 2); if (getSum(BITree, mid) >= k) { r = mid - 1; lb = mid; } else l = mid + 1; } return lb; } function performQueries(A, n, q) { // Store the Binary Indexed Tree let BITree = constructBITree(A, n); // Solve each query in Q for (let i = 0; i < q.length; i++) { let id = q[i][0]; if (id == 1) { let idx = q[i][1]; let val = q[i][2]; A[idx] += val; // Update the values of all // ancestors of idx updateBIT(BITree, n, idx, val); } else { let k = q[i][1]; let lb = getLowerBound(BITree, A, n, k); document.write(lb + "<br>"); } } } // Driver Code let A = [1, 2, 3, 5, 8]; let n = A.length; let q = [[1, 0, 2], [2, 5, 0], [1, 3, 5]]; performQueries(A, n, q); // This code is contributed by gfgking </script>
1
Complejidad de tiempo: O(Q*(logN) 2 )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Ganeshchowdharysadanala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA