Dada una array de tamaño n y un conjunto dado de comandos de tamaño m. Los comandos se enumeran del 1 al m. Estos comandos pueden ser de los siguientes dos tipos de comandos:
- Tipo 1 [lr (1 <= l <= r <= n)] : Aumenta todos los elementos de la array en uno, cuyos índices pertenecen al rango [l, r]. En estas consultas el índice es inclusivo en el rango.
- Escriba 2 [lr (1 <= l <= r <= m)] : Ejecute todos los comandos cuyos índices estén en el rango [l, r]. En estas consultas el índice es inclusivo en el rango. Se garantiza que r es estrictamente menor que la enumeración/número del comando actual.
Nota: la indexación de la array es desde 1 según la declaración del problema.
Ejemplo 1
Input : 5 5 1 1 2 1 4 5 2 1 2 2 1 3 2 3 4 Output : 7 7 0 7 7
Explicación del Ejemplo 1:
Nuestra array inicialmente es de tamaño 5 y cada elemento se ha inicializado en 0.
Entonces, ahora la pregunta indica que tenemos 5 consultas para el ejemplo anterior.
- La consulta 1 es del tipo 1: como se indicó anteriormente, simplemente incrementaremos los índices de la array en 1, los índices dados son 1 y 2, por lo que después de la ejecución de la primera, nuestra array se convierte en 1 1 0 0 0.
- La consulta 2 es del tipo 1: como se indicó anteriormente, simplemente incrementaremos los índices de la array en 1,
los índices dados son 4 y 5, por lo que después de la ejecución de la primera, nuestra array se convierte en 1 1 0 1 1. - La consulta 3 es del tipo 2: como se indica en la definición de este tipo de consulta, ejecutaremos las consultas establecidas en el rango, es decir, operaremos las consultas en lugar de la array. El rango dado es 1 y 2, por lo que ejecutaremos las consultas 1 y 2 nuevamente, es decir, usaremos un enfoque repetitivo para las consultas de tipo 2, por lo que ejecutaremos la consulta 1 nuevamente y nuestra array será 2 2 0 1 1. Ahora, cuando ejecutemos el consulta ejecutaremos la consulta 2 y nuestra array resultante será 2 2 0 2 2 .
- La consulta 4 es del tipo 2: como se indica en la definición de este tipo de consulta, ejecutaremos las consultas establecidas en el rango, es decir, operaremos las consultas en lugar de la array. El rango dado es 1 y 3, por lo que ejecutaremos las consultas 1, 2 y 3 nuevamente, es decir, utilizando un enfoque repetitivo, se ejecutarán las consultas 1, 2 y 3. Después de la ejecución de la consulta 1 nuevamente, la array será 3 3 0 2 2 . Después de la ejecución de la consulta 2 nuevamente, la array será 3 3 0 3 3 . Ahora, debido a la consulta 3 incluida en el rango, ejecutaremos la consulta 3, la array resultante será 4 4 0 4 4 . Como se explicó anteriormente.
- La consulta 5 es del tipo 2: la última consulta ejecutará la tercera y cuarta consulta que se explicó anteriormente. Después de la ejecución de la tercera consulta, nuestra array será 5 5 0 5 5 . Y después de la ejecución de la cuarta consulta, es decir, la ejecución de la consulta 1, 2 y 3, nuestra array será 7 7 0 7 7 Lo anterior es el resultado deseado
Ejemplo 2
Input : 1 2 1 1 1 1 1 1 Output : 2
Explicación del ejemplo 2:
Nuestra array inicialmente es de tamaño 1 y cada elemento se ha inicializado en 0.
Entonces, ahora la pregunta indica que tenemos 2 consultas para el ejemplo anterior.
- La consulta 1 es del tipo 1: como se indicó anteriormente, simplemente incrementaremos los índices de la array en 1, los índices dados son 1 y 1, por lo que después de la ejecución de la primera, nuestra array se convierte en 1.
- La consulta 2 es del tipo 1: como se indicó anteriormente, simplemente incrementaremos los índices de la array en 1, los índices dados son 1 y 1, por lo que después de la ejecución de la primera, nuestra array se convierte en 2. Esto nos da el resultado deseado.
Método 1: este método es el método de fuerza bruta en el que se aplica una recursividad simple en las consultas de tipo 2 y para las consultas de tipo 1 se realiza un incremento simple en el índice de la array.
Implementación:
C++
// CPP program to perform range queries over range // queries. #include <bits/stdc++.h> using namespace std; // Function to execute type 1 query void type1(int arr[], int start, int limit) { // incrementing the array by 1 for type // 1 queries for (int i = start; i <= limit; i++) arr[i]++; } // Function to execute type 2 query void type2(int arr[], int query[][3], int start, int limit) { for (int i = start; i <= limit; i++) { // If the query is of type 1 function // call to type 1 query if (query[i][0] == 1) type1(arr, query[i][1], query[i][2]); // If the query is of type 2 recursive call // to type 2 query else if (query[i][0] == 2) type2(arr, query, query[i][1], query[i][2]); } } // Driver code int main() { // Input size of array and number of queries int n = 5, m = 5; int arr[n + 1]; for (int i = 1; i <= n; i++) arr[i] = 0; // Build query matrix int temp[15] = { 1, 1, 2, 1, 4, 5, 2, 1, 2, 2, 1, 3, 2, 3, 4 }; int query[5][3]; int j = 0; for (int i = 1; i <= m; i++) { query[i][0] = temp[j++]; query[i][1] = temp[j++]; query[i][2] = temp[j++]; } // Perform queries for (int i = 1; i <= m; i++) if (query[i][0] == 1) type1(arr, query[i][1], query[i][2]); else if (query[i][0] == 2) type2(arr, query, query[i][1], query[i][2]); // printing the result for (int i = 1; i <= n; i++) cout << arr[i] << " "; return 0; }
Java
// Java program to perform range queries // over range queries. import java.util.*; class GFG { // Function to execute type 1 query static void type1(int[] arr, int start, int limit) { // incrementing the array by 1 for type // 1 queries for (int i = start; i <= limit; i++) arr[i]++; } // Function to execute type 2 query static void type2(int[] arr, int[][] query, int start, int limit) { for (int i = start; i <= limit; i++) { // If the query is of type 1 function // call to type 1 query if (query[i][0] == 1) type1(arr, query[i][1], query[i][2]); // If the query is of type 2 recursive call // to type 2 query else if (query[i][0] == 2) type2(arr, query, query[i][1], query[i][2]); } } // Driver Code public static void main(String[] args) { // Input size of array and number of queries int n = 5, m = 5; int[] arr = new int[n + 1]; // Build query matrix int[] temp = { 1, 1, 2, 1, 4, 5, 2, 1, 2, 2, 1, 3, 2, 3, 4 }; int[][] query = new int[6][4]; int j = 0; for (int i = 1; i <= m; i++) { query[i][0] = temp[j++]; query[i][1] = temp[j++]; query[i][2] = temp[j++]; } // Perform queries for (int i = 1; i <= m; i++) if (query[i][0] == 1) type1(arr, query[i][1], query[i][2]); else if (query[i][0] == 2) type2(arr, query, query[i][1], query[i][2]); // printing the result for (int i = 1; i <= n; i++) System.out.print(arr[i] + " "); System.out.println(); } } // This code is contributed by // sanjeev2552
Python3
# Python3 program to perform range # queries over range queries. # Function to execute type 1 query def type1(arr, start, limit): # incrementing the array by 1 # for type 1 queries for i in range(start, limit + 1): arr[i] += 1 # Function to execute type 2 query def type2(arr, query, start, limit): for i in range(start, limit + 1): # If the query is of type 1 # function call to type 1 query if (query[i][0] == 1): type1(arr, query[i][1], query[i][2]) # If the query is of type 2 # recursive call to type 2 query else if (query[i][0] == 2): type2(arr, query, query[i][1], query[i][2]) # Driver code # Input size of array and # number of queries n = 5 m = 5 arr = [0 for i in range(n + 1)] # Build query matrix temp = [1, 1, 2, 1, 4, 5, 2, 1, 2, 2, 1, 3, 2, 3, 4 ] query = [[0 for i in range(3)] for j in range(6)] j = 0 for i in range(1, m + 1): query[i][0] = temp[j] j += 1 query[i][1] = temp[j] j += 1 query[i][2] = temp[j] j += 1 # Perform queries for i in range(1, m + 1): if (query[i][0] == 1): type1(arr, query[i][1], query[i][2]) else if (query[i][0] == 2): type2(arr, query, query[i][1], query[i][2]) # printing the result for i in range(1, n + 1): print(arr[i], end = " ") # This code is contributed # by mohit kumar
C#
// C# program to perform range queries // over range queries. using System; class GFG { // Function to execute type 1 query static void type1(int[] arr, int start, int limit) { // incrementing the array by 1 for type // 1 queries for (int i = start; i <= limit; i++) arr[i]++; } // Function to execute type 2 query static void type2(int[] arr, int[,] query, int start, int limit) { for (int i = start; i <= limit; i++) { // If the query is of type 1 function // call to type 1 query if (query[i, 0] == 1) type1(arr, query[i,1], query[i,2]); // If the query is of type 2 recursive call // to type 2 query else if (query[i, 0] == 2) type2(arr, query, query[i, 1], query[i, 2]); } } // Driver Code public static void Main() { // Input size of array and number of queries int n = 5, m = 5; int[] arr = new int[n + 1]; // Build query matrix int[] temp = { 1, 1, 2, 1, 4, 5, 2, 1, 2, 2, 1, 3, 2, 3, 4 }; int[,] query = new int[6,4]; int j = 0; for (int i = 1; i <= m; i++) { query[i, 0] = temp[j++]; query[i, 1] = temp[j++]; query[i, 2] = temp[j++]; } // Perform queries for (int i = 1; i <= m; i++) if (query[i, 0] == 1) type1(arr, query[i, 1], query[i, 2]); else if (query[i, 0] == 2) type2(arr, query, query[i, 1], query[i, 2]); // printing the result for (int i = 1; i <= n; i++) Console.Write(arr[i] + " "); Console.WriteLine(); } } // This code is contributed by AbhiThakur
Javascript
<script> // Javascript program to perform range queries // over range queries. // Function to execute type 1 query function type1(arr,start,limit) { // incrementing the array by 1 for type // 1 queries for (let i = start; i <= limit; i++) arr[i]++; } // Function to execute type 2 query function type2(arr,query,start,limit) { for (let i = start; i <= limit; i++) { // If the query is of type 1 function // call to type 1 query if (query[i][0] == 1) type1(arr, query[i][1], query[i][2]); // If the query is of type 2 recursive call // to type 2 query else if (query[i][0] == 2) type2(arr, query, query[i][1], query[i][2]); } } // Driver Code // Input size of array and number of queries let n = 5, m = 5; let arr = new Array(n + 1); for(let i=0;i<arr.length;i++) { arr[i]=0; } // Build query matrix let temp = [ 1, 1, 2, 1, 4, 5, 2, 1, 2, 2, 1, 3, 2, 3, 4 ]; let query = new Array(6); for(let i=0;i<6;i++) { query[i]=new Array(4); for(let j=0;j<4;j++) { query[i][j]=0; } } let j = 0; for (let i = 1; i <= m; i++) { query[i][0] = temp[j++]; query[i][1] = temp[j++]; query[i][2] = temp[j++]; } // Perform queries for (let i = 1; i <= m; i++) if (query[i][0] == 1) type1(arr, query[i][1], query[i][2]); else if (query[i][0] == 2) type2(arr, query, query[i][1], query[i][2]); // printing the result for (let i = 1; i <= n; i++) document.write(arr[i] + " "); document.write("<br>"); // This code is contributed by patel2127 </script>
7 7 0 7 7
La complejidad del tiempo del código anterior es O(2 ^ m)
Método 2: en este método, usamos una array adicional para crear la array de registros para encontrar la cantidad de veces que se ejecuta una consulta en particular y, después de crear la array de registros, simplemente ejecutamos las consultas de tipo 1 y el contenido de la array de registros es simplemente agregó a la array principal y esto nos daría la array resultante.
Implementación:
C++
// CPP program to perform range queries over range // queries. #include <bits/stdc++.h> using namespace std; // Function to create the record array void record_sum(int record[], int l, int r, int n, int adder) { for (int i = l; i <= r; i++) record[i] += adder; } // Driver Code int main() { int n = 5, m = 5; int arr[n]; // Build query matrix memset(arr, 0, sizeof arr); int query[5][3] = { { 1, 1, 2 }, { 1, 4, 5 }, { 2, 1, 2 }, { 2, 1, 3 }, { 2, 3, 4 } }; int record[m]; memset(record, 0, sizeof record); for (int i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_sum if (query[i][0] == 2) record_sum(record, query[i][1] - 1, query[i][2] - 1, m, record[i] + 1); // If query is of type 1 then simply add // 1 to the record array else record_sum(record, i, i, m, 1); } // for type 1 queries adding the contains of // record array to the main array record array for (int i = 0; i < m; i++) { if (query[i][0] == 1) record_sum(arr, query[i][1] - 1, query[i][2] - 1, n, record[i]); } // printing the array for (int i = 0; i < n; i++) cout << arr[i] << ' '; return 0; }
Java
// Java program to perform range queries // over range queries. import java.util.Arrays; class GFG { // Function to create the record array static void record_sum(int record[], int l, int r, int n, int adder) { for (int i = l; i <= r; i++) { record[i] += adder; } } // Driver Code public static void main(String[] args) { int n = 5, m = 5; int arr[] = new int[n]; // Build query matrix Arrays.fill(arr, 0); int query[][] = {{1, 1, 2}, {1, 4, 5}, {2, 1, 2}, {2, 1, 3}, {2, 3, 4}}; int record[] = new int[m]; Arrays.fill(record, 0); for (int i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_sum if (query[i][0] == 2) { record_sum(record, query[i][1] - 1, query[i][2] - 1, m, record[i] + 1); } // If query is of type 1 then // simply add 1 to the record array else { record_sum(record, i, i, m, 1); } } // for type 1 queries adding the contains of // record array to the main array record array for (int i = 0; i < m; i++) { if (query[i][0] == 1) { record_sum(arr, query[i][1] - 1, query[i][2] - 1, n, record[i]); } } // printing the array for (int i = 0; i < n; i++) { System.out.print(arr[i] + " "); } } } // This code is contributed // by Princi Singh
Python3
# Python3 program to perform range queries over range # queries. # Function to create the record array def record_sum(record, l, r, n, adder): for i in range(l, r + 1): record[i] += adder # Driver Code n = 5 m = 5 arr = [0]*n # Build query matrix query = [[1, 1, 2 ],[ 1, 4, 5 ],[2, 1, 2 ], [ 2, 1, 3 ],[ 2, 3, 4]] record = [0]*m for i in range(m - 1, -1, -1): # If query is of type 2 then function # call to record_sum if (query[i][0] == 2): record_sum(record, query[i][1] - 1, query[i][2] - 1, m, record[i] + 1) # If query is of type 1 then simply add # 1 to the record array else: record_sum(record, i, i, m, 1) # for type 1 queries adding the contains of # record array to the main array record array for i in range(m): if (query[i][0] == 1): record_sum(arr, query[i][1] - 1, query[i][2] - 1, n, record[i]) # printing the array for i in range(n): print(arr[i], end=' ') # This code is contributed by shubhamsingh10
C#
// C# program to perform range queries // over range queries. using System; class GFG { // Function to create the record array static void record_sum(int []record, int l, int r, int n, int adder) { for (int i = l; i <= r; i++) { record[i] += adder; } } // Driver Code public static void Main(String[] args) { int n = 5, m = 5; int []arr = new int[n]; // Build query matrix int [,]query = {{1, 1, 2}, {1, 4, 5}, {2, 1, 2}, {2, 1, 3}, {2, 3, 4}}; int []record = new int[m]; for (int i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_sum if (query[i,0] == 2) { record_sum(record, query[i,1] - 1, query[i,2] - 1, m, record[i] + 1); } // If query is of type 1 then // simply add 1 to the record array else { record_sum(record, i, i, m, 1); } } // for type 1 queries adding the contains of // record array to the main array record array for (int i = 0; i < m; i++) { if (query[i, 0] == 1) { record_sum(arr, query[i, 1] - 1, query[i, 2] - 1, n, record[i]); } } // printing the array for (int i = 0; i < n; i++) { Console.Write(arr[i] + " "); } } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript program to perform range queries // over range queries. // Function to create the record array function record_sum(record,l,r,n,adder) { for (let i = l; i <= r; i++) { record[i] += adder; } } // Driver Code let n = 5, m = 5; let arr = new Array(n); // Build query matrix for(let i=0;i<arr.length;i++) { arr[i]=0; } let query = [[1, 1, 2], [1, 4, 5], [2, 1, 2], [2, 1, 3], [2, 3, 4]]; let record = new Array(m); for(let i=0;i<record.length;i++) { record[i]=0; } for (let i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_sum if (query[i][0] == 2) { record_sum(record, query[i][1] - 1, query[i][2] - 1, m, record[i] + 1); } // If query is of type 1 then // simply add 1 to the record array else { record_sum(record, i, i, m, 1); } } // for type 1 queries adding the contains of // record array to the main array record array for (let i = 0; i < m; i++) { if (query[i][0] == 1) { record_sum(arr, query[i][1] - 1, query[i][2] - 1, n, record[i]); } } // printing the array for (let i = 0; i < n; i++) { document.write(arr[i] + " "); } // This code is contributed by unknown2108 </script>
7 7 0 7 7
La complejidad de tiempo del código anterior es O (n ^ 2)
Método 3: este método se ha vuelto más eficiente al aplicar la descomposición de raíces cuadradas a la array de registros.
Implementación:
C++
// CPP program to perform range queries over range // queries. #include <bits/stdc++.h> #define max 10000 using namespace std; // For prefix sum array void update(int arr[], int l) { arr[l] += arr[l - 1]; } // This function is used to apply square root // decomposition in the record array void record_func(int block_size, int block[], int record[], int l, int r, int value) { // traversing first block in range while (l < r && l % block_size != 0 && l != 0) { record[l] += value; l++; } // traversing completely overlapped blocks in range while (l + block_size <= r + 1) { block[l / block_size] += value; l += block_size; } // traversing last block in range while (l <= r) { record[l] += value; l++; } } // Function to print the resultant array void print(int arr[], int n) { for (int i = 0; i < n; i++) cout << arr[i] << " "; } // Driver code int main() { int n = 5, m = 5; int arr[n], record[m]; int block_size = sqrt(m); int block[max]; int command[5][3] = { { 1, 1, 2 }, { 1, 4, 5 }, { 2, 1, 2 }, { 2, 1, 3 }, { 2, 3, 4 } }; memset(arr, 0, sizeof arr); memset(record, 0, sizeof record); memset(block, 0, sizeof block); for (int i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_func if (command[i][0] == 2) { int x = i / (block_size); record_func(block_size, block, record, command[i][1] - 1, command[i][2] - 1, (block[x] + record[i] + 1)); } // If query is of type 1 then simply add // 1 to the record array else record[i]++; } // Merging the value of the block in the record array for (int i = 0; i < m; i++) { int check = (i / block_size); record[i] += block[check]; } for (int i = 0; i < m; i++) { // If query is of type 1 then the array // elements are over-written by the record // array if (command[i][0] == 1) { arr[command[i][1] - 1] += record[i]; if ((command[i][2] - 1) < n - 1) arr[(command[i][2])] -= record[i]; } } // The prefix sum of the array for (int i = 1; i < n; i++) update(arr, i); // Printing the resultant array print(arr, n); return 0; }
Java
// Java program to perform range queries over range // queries. public class GFG { static final int max = 10000; // For prefix sum array static void update(int arr[], int l) { arr[l] += arr[l - 1]; } // This function is used to apply square root // decomposition in the record array static void record_func(int block_size, int block[], int record[], int l, int r, int value) { // traversing first block in range while (l < r && l % block_size != 0 && l != 0) { record[l] += value; l++; } // traversing completely overlapped blocks in range while (l + block_size <= r + 1) { block[l / block_size] += value; l += block_size; } // traversing last block in range while (l <= r) { record[l] += value; l++; } } // Function to print the resultant array static void print(int arr[], int n) { for (int i = 0; i < n; i++) { System.out.print(arr[i] + " "); } } // Driver code public static void main(String[] args) { int n = 5, m = 5; int arr[] = new int[n], record[] = new int[m]; int block_size = (int) Math.sqrt(m); int block[] = new int[max]; int command[][] = {{1, 1, 2}, {1, 4, 5}, {2, 1, 2}, {2, 1, 3}, {2, 3, 4}}; for (int i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_func if (command[i][0] == 2) { int x = i / (block_size); record_func(block_size, block, record, command[i][1] - 1, command[i][2] - 1, (block[x] + record[i] + 1)); } // If query is of type 1 then simply add // 1 to the record array else { record[i]++; } } // Merging the value of the block in the record array for (int i = 0; i < m; i++) { int check = (i / block_size); record[i] += block[check]; } for (int i = 0; i < m; i++) { // If query is of type 1 then the array // elements are over-written by the record // array if (command[i][0] == 1) { arr[command[i][1] - 1] += record[i]; if ((command[i][2] - 1) < n - 1) { arr[(command[i][2])] -= record[i]; } } } // The prefix sum of the array for (int i = 1; i < n; i++) { update(arr, i); } // Printing the resultant array print(arr, n); } } // This code is contributed by 29AjayKumar
Python3
# Python3 program to perform range # queries over range queries. import math max = 10000 # For prefix sum array def update(arr, l): arr[l] += arr[l - 1] # This function is used to apply square root # decomposition in the record array def record_func(block_size, block, record, l, r, value): # Traversing first block in range while (l < r and l % block_size != 0 and l != 0): record[l] += value l += 1 # Traversing completely overlapped # blocks in range while (l + block_size <= r + 1): block[l // block_size] += value l += block_size # Traversing last block in range while (l <= r): record[l] += value l += 1 # Function to print the resultant array def print_array(arr, n): for i in range(n): print(arr[i], end = " ") # Driver code if __name__ == "__main__": n = 5 m = 5 arr = [0] * n record = [0] * m block_size = (int)(math.sqrt(m)) block = [0] * max command = [ [ 1, 1, 2 ], [ 1, 4, 5 ], [ 2, 1, 2 ], [ 2, 1, 3 ], [ 2, 3, 4 ] ] for i in range(m - 1, -1, -1): # If query is of type 2 then function # call to record_func if (command[i][0] == 2): x = i // (block_size) record_func(block_size, block, record, command[i][1] - 1, command[i][2] - 1, (block[x] + record[i] + 1)) # If query is of type 1 then simply add # 1 to the record array else: record[i] += 1 # Merging the value of the block # in the record array for i in range(m): check = (i // block_size) record[i] += block[check] for i in range(m): # If query is of type 1 then the array # elements are over-written by the record # array if (command[i][0] == 1): arr[command[i][1] - 1] += record[i] if ((command[i][2] - 1) < n - 1): arr[(command[i][2])] -= record[i] # The prefix sum of the array for i in range(1, n): update(arr, i) # Printing the resultant array print_array(arr, n) # This code is contributed by chitranayal
C#
// C# program to perform range queries over range // queries. using System; public class GFG { static readonly int max = 10000; // For prefix sum array static void update(int []arr, int l) { arr[l] += arr[l - 1]; } // This function is used to apply square root // decomposition in the record array static void record_func(int block_size, int []block, int []record, int l, int r, int value) { // traversing first block in range while (l < r && l % block_size != 0 && l != 0) { record[l] += value; l++; } // traversing completely overlapped blocks in range while (l + block_size <= r + 1) { block[l / block_size] += value; l += block_size; } // traversing last block in range while (l <= r) { record[l] += value; l++; } } // Function to print the resultant array static void print(int []arr, int n) { for (int i = 0; i < n; i++) { Console.Write(arr[i] + " "); } } // Driver code public static void Main() { int n = 5, m = 5; int []arr = new int[n]; int []record = new int[m]; int block_size = (int) Math.Sqrt(m); int []block = new int[max]; int [,]command= {{1, 1, 2}, {1, 4, 5}, {2, 1, 2}, {2, 1, 3}, {2, 3, 4}}; for (int i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_func if (command[i,0] == 2) { int x = i / (block_size); record_func(block_size, block, record, command[i,1] - 1, command[i,2] - 1, (block[x] + record[i] + 1)); } // If query is of type 1 then simply add // 1 to the record array else { record[i]++; } } // Merging the value of the block in the record array for (int i = 0; i < m; i++) { int check = (i / block_size); record[i] += block[check]; } for (int i = 0; i < m; i++) { // If query is of type 1 then the array // elements are over-written by the record // array if (command[i,0] == 1) { arr[command[i,1] - 1] += record[i]; if ((command[i,2] - 1) < n - 1) { arr[(command[i,2])] -= record[i]; } } } // The prefix sum of the array for (int i = 1; i < n; i++) { update(arr, i); } // Printing the resultant array print(arr, n); } } // This code is contributed by 29AjayKumar
Javascript
<script> // Javascript program to perform range queries over range // queries. let max = 10000; // For prefix sum array function update(arr,l) { arr[l] += arr[l - 1]; } // This function is used to apply square root // decomposition in the record array function record_func(block_size,block,record,l,r,value) { // traversing first block in range while (l < r && l % block_size != 0 && l != 0) { record[l] += value; l++; } // traversing completely overlapped blocks in range while (l + block_size <= r + 1) { let x = Math.floor(l / block_size); block[x] += value; l += block_size; } // traversing last block in range while (l <= r) { record[l] += value; l++; } } // Function to print the resultant array function print(arr,n) { for (let i = 0; i < n; i++) { document.write(arr[i] + " "); } } // Driver code let n = 5, m = 5; let arr = new Array(n); for(let i = 0; i < n; i++) arr[i] = 0; let record = new Array(m); for(let i = 0; i < m; i++) record[i] = 0; let block_size = Math.floor( Math.sqrt(m)); let block = new Array(max); for(let i = 0; i < max; i++) block[i] = 0; let command = [[1, 1, 2], [1, 4, 5], [2, 1, 2], [2, 1, 3], [2, 3, 4]]; for (let i = m - 1; i >= 0; i--) { // If query is of type 2 then function // call to record_func if (command[i][0] == 2) { let x = Math.floor(i / (block_size)); record_func(block_size, block, record, command[i][1] - 1, command[i][2] - 1, (block[x] + record[i] + 1)); } // If query is of type 1 then simply add // 1 to the record array else { record[i]++; } } // Merging the value of the block in the record array for (let i = 0; i < m; i++) { let check = Math.floor(i / block_size); record[i] += block[check]; } for (let i = 0; i < m; i++) { // If query is of type 1 then the array // elements are over-written by the record // array if (command[i][0] == 1) { arr[command[i][1] - 1] += record[i]; if ((command[i][2] - 1) < n - 1) { arr[(command[i][2])] -= record[i]; } } } // The prefix sum of the array for (let i = 1; i < n; i++) { update(arr, i); } // Printing the resultant array print(arr, n); // This code is contributed by ab2127 </script>
7 7 0 7 7
Método 4: este método se ha vuelto más eficiente al aplicar el árbol indexado binario o el árbol Fenwick mediante la creación de dos árboles indexados binarios para la consulta 1 y la consulta 2, respectivamente.
Implementación:
C++
// C++ program to perform range queries over range // queries. #include <bits/stdc++.h> 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 + BITree[index]); // Update index to that of parent in update View index = (index + (index & (-index))); } return; } // Constructs and returns a Binary Indexed Tree for given // array of size n. 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; } // 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; // index in BITree[] is 1 more than the index in arr[] index = index + 1; // Traverse ancestors of BITree[index] while (index > 0) { // Add element of BITree to sum sum = (sum + BITree[index]); // Move index to parent node in getSum View index -= index & (-index); } return sum; } // Function to update the BITree void update(int BITree[], int l, int r, int n, int val) { updateBIT(BITree, n, l, val); updateBIT(BITree, n, r + 1, -val); return; } // Driver code int main() { int n = 5, m = 5; int temp[15] = { 1, 1, 2, 1, 4, 5, 2, 1, 2, 2, 1, 3, 2, 3, 4 }; int q[5][3]; int j = 0; for (int i = 1; i <= m; i++) { q[i][0] = temp[j++]; q[i][1] = temp[j++]; q[i][2] = temp[j++]; } // BITree for query of type 2 int* BITree = constructBITree(m); // BITree for query of type 1 int* BITree2 = constructBITree(n); // Input the queries in a 2D matrix for (int i = 1; i <= m; i++) cin >> q[i][0] >> q[i][1] >> q[i][2]; // If query is of type 2 then function call // to update with BITree for (int i = m; i >= 1; i--) if (q[i][0] == 2) update(BITree, q[i][1] - 1, q[i][2] - 1, m, 1); for (int i = m; i >= 1; i--) { if (q[i][0] == 2) { long int val = getSum(BITree, i - 1); update(BITree, q[i][1] - 1, q[i][2] - 1, m, val); } } // If query is of type 1 then function call // to update with BITree2 for (int i = m; i >= 1; i--) { if (q[i][0] == 1) { long int val = getSum(BITree, i - 1); update(BITree2, q[i][1] - 1, q[i][2] - 1, n, (val + 1)); } } for (int i = 1; i <= n; i++) cout << (getSum(BITree2, i - 1)) << " "; return 0; }
Java
// Java program to perform range queries over range // queries. import java.io.*; import java.util.*; class GFG { // 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 + BITree[index]); // Update index to that of parent in update View index = (index + (index & (-index))); } return; } // Constructs and returns a Binary Indexed Tree for given // array of size n. 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; } // 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; // index in BITree[] is 1 more than the index in arr[] index = index + 1; // Traverse ancestors of BITree[index] while (index > 0) { // Add element of BITree to sum sum = (sum + BITree[index]); // Move index to parent node in getSum View index -= index & (-index); } return sum; } // Function to update the BITree static void update(int BITree[], int l, int r, int n, int val) { updateBIT(BITree, n, l, val); updateBIT(BITree, n, r + 1, -val); return; } // Driver code public static void main (String[] args) { int n = 5, m = 5; int temp[] = { 1, 1, 2, 1, 4, 5, 2, 1, 2, 2, 1, 3, 2, 3, 4 }; int[][] q = new int[6][3]; int j = 0; for (int i = 1; i <= m; i++) { q[i][0] = temp[j++]; q[i][1] = temp[j++]; q[i][2] = temp[j++]; } // BITree for query of type 2 int[] BITree = constructBITree(m); // BITree for query of type 1 int[] BITree2 = constructBITree(n); // Input the queries in a 2D matrix /*Scanner sc=new Scanner(System.in); for (int i = 1; i <= m; i++) { q[i][0]=sc.nextInt(); q[i][1]=sc.nextInt(); q[i][2]=sc.nextInt(); }*/ // If query is of type 2 then function call // to update with BITree for (int i = m; i >= 1; i--) if (q[i][0] == 2) update(BITree, q[i][1] - 1, q[i][2] - 1, m, 1); for (int i = m; i >= 1; i--) { if (q[i][0] == 2) { int val = getSum(BITree, i - 1); update(BITree, q[i][1] - 1, q[i][2] - 1, m, val); } } // If query is of type 1 then function call // to update with BITree2 for (int i = m; i >= 1; i--) { if (q[i][0] == 1) { int val = getSum(BITree, i - 1); update(BITree2, q[i][1] - 1, q[i][2] - 1, n, (val + 1)); } } for (int i = 1; i <= n; i++) System.out.print(getSum(BITree2, i - 1)+" "); } } // This code is contributed by avanitrachhadiya2155
C#
// C# program to perform range queries over range // queries. using System; class GFG{ // 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 + BITree[index]); // Update index to that of parent in update View index = (index + (index & (-index))); } return; } // Constructs and returns a Binary Indexed // Tree for given array of size n. 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; } // 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; // index in BITree[] is 1 more than // the index in arr[] index = index + 1; // Traverse ancestors of BITree[index] while (index > 0) { // Add element of BITree to sum sum = (sum + BITree[index]); // Move index to parent node in getSum View index -= index & (-index); } return sum; } // Function to update the BITree static void update(int[] BITree, int l, int r, int n, int val) { updateBIT(BITree, n, l, val); updateBIT(BITree, n, r + 1, -val); return; } // Driver code static public void Main() { int n = 5, m = 5; int[] temp = { 1, 1, 2, 1, 4, 5, 2, 1, 2, 2, 1, 3, 2, 3, 4 }; int[,] q = new int[6, 3]; int j = 0; for(int i = 1; i <= m; i++) { q[i, 0] = temp[j++]; q[i, 1] = temp[j++]; q[i, 2] = temp[j++]; } // BITree for query of type 2 int[] BITree = constructBITree(m); // BITree for query of type 1 int[] BITree2 = constructBITree(n); // If query is of type 2 then function call // to update with BITree for(int i = m; i >= 1; i--) if (q[i, 0] == 2) update(BITree, q[i, 1] - 1, q[i, 2] - 1, m, 1); for(int i = m; i >= 1; i--) { if (q[i,0] == 2) { int val = getSum(BITree, i - 1); update(BITree, q[i, 1] - 1, q[i, 2] - 1, m, val); } } // If query is of type 1 then function call // to update with BITree2 for(int i = m; i >= 1; i--) { if (q[i,0] == 1) { int val = getSum(BITree, i - 1); update(BITree2, q[i, 1] - 1, q[i, 2] - 1, n, (val + 1)); } } for(int i = 1; i <= n; i++) Console.Write(getSum(BITree2, i - 1) + " "); } } // This code is contributed by rag2127
Javascript
<script> // Javascript program to perform range queries over range // queries. // 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 + BITree[index]); // Update index to that of parent in update View index = (index + (index & (-index))); } return; } // Constructs and returns a Binary Indexed Tree for given // array of size n. 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; } // 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; // index in BITree[] is 1 more than the index in arr[] index = index + 1; // Traverse ancestors of BITree[index] while (index > 0) { // Add element of BITree to sum sum = (sum + BITree[index]); // Move index to parent node in getSum View index -= index & (-index); } return sum; } // Function to update the BITree function update(BITree, l, r, n, val) { updateBIT(BITree, n, l, val); updateBIT(BITree, n, r + 1, -val); return; } // Driver code let n = 5, m = 5; let temp = [ 1, 1, 2, 1, 4, 5, 2, 1, 2, 2, 1, 3, 2, 3, 4 ]; let q = new Array(6).fill(0).map(() => new Array(3)) let j = 0; for (let i = 1; i <= m; i++) { q[i][0] = temp[j++]; q[i][1] = temp[j++]; q[i][2] = temp[j++]; } // BITree for query of type 2 let BITree = constructBITree(m); // BITree for query of type 1 let BITree2 = constructBITree(n); // Input the queries in a 2D matrix /*Scanner sc=new Scanner(System.in); for (int i = 1; i <= m; i++) { q[i][0]=sc.nextInt(); q[i][1]=sc.nextInt(); q[i][2]=sc.nextInt(); }*/ // If query is of type 2 then function call // to update with BITree for (let i = m; i >= 1; i--) if (q[i][0] == 2) update(BITree, q[i][1] - 1, q[i][2] - 1, m, 1); for (let i = m; i >= 1; i--) { if (q[i][0] == 2) { let val = getSum(BITree, i - 1); update(BITree, q[i][1] - 1, q[i][2] - 1, m, val); } } // If query is of type 1 then function call // to update with BITree2 for (let i = m; i >= 1; i--) { if (q[i][0] == 1) { let val = getSum(BITree, i - 1); update(BITree2, q[i][1] - 1, q[i][2] - 1, n, (val + 1)); } } for (let i = 1; i <= n; i++) document.write(getSum(BITree2, i - 1)+" "); // This code is contributed by gfgking. </script>
0 0 0 7 7
La complejidad de tiempo del Método 3 y el Método 4 es O(log n) .
Este artículo es una contribución de Mohak Agrawal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA