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>
Producción
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>
Producción
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>
Producción
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>
Producción
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