Dada una array que contiene n enteros y un valor d . Se dan m consultas. Cada consulta tiene dos valores start y end . Para cada consulta, el problema es incrementar los valores desde el índice de inicio hasta el final en la array dada por el valor dado d . Se requiere una solución lineal eficiente en el tiempo para manejar tantas consultas múltiples.
Ejemplos:
Input : arr[] = {3, 5, 4, 8, 6, 1}
Query list: {0, 3}, {4, 5}, {1, 4},
{0, 1}, {2, 5}
d = 2
Output : 7 11 10 14 12 5
Executing 1st query {0, 3}
arr = {5, 7, 6, 10, 6, 1}
Executing 2nd query {4, 5}
arr = {5, 7, 6, 10, 8, 3}
Executing 3rd query {1, 4}
arr = {5, 9, 8, 12, 10, 3}
Executing 4th query {0, 1}
arr = {7, 11, 8, 12, 10, 3}
Executing 5th query {2, 5}
arr = {7, 11, 10, 14, 12, 5}
Note: Each query is executed on the
previously modified array.
Enfoque ingenuo: para cada consulta, recorra la array en el rango de principio a fin e incremente los valores en ese rango por el valor dado d .
Enfoque eficiente: cree una array sum[] de tamaño n e inicialice todos sus índices con el valor 0. Ahora, para cada par de índices (inicio, final) , aplique la operación dada en la array sum[] . Las operaciones son: sum[start] += d y sum[end+1] -= d solo si el índice (end+1) existe. Ahora, del índice i = 1 a n-1, acumule los valores en la array sum[] como: sum[i] += sum[i-1] . Finalmente, para el índice i = 0 a n-1, realice la operación: arr[i] += sum[i] .
Implementación:
C++
// C++ implementation to increment values in the
// given range by a value d for multiple queries
#include <bits/stdc++.h>
using namespace std;
// structure to store the (start, end) index pair for
// each query
struct query {
int start, end;
};
// function to increment values in the given range
// by a value d for multiple queries
void incrementByD(int arr[], struct query q_arr[],
int n, int m, int d)
{
int sum[n];
memset(sum, 0, sizeof(sum));
// for each (start, end) index pair perform the
// following operations on 'sum[]'
for (int i = 0; i < m; i++) {
// increment the value at index 'start' by
// the given value 'd' in 'sum[]'
sum[q_arr[i].start] += d;
// if the index '(end+1)' exists then decrement
// the value at index '(end+1)' by the given
// value 'd' in 'sum[]'
if ((q_arr[i].end + 1) < n)
sum[q_arr[i].end + 1] -= d;
}
// Now, perform the following operations:
// accumulate values in the 'sum[]' array and
// then add them to the corresponding indexes
// in 'arr[]'
arr[0] += sum[0];
for (int i = 1; i < n; i++) {
sum[i] += sum[i - 1];
arr[i] += sum[i];
}
}
// function to print the elements of the given array
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver program to test above
int main()
{
int arr[] = { 3, 5, 4, 8, 6, 1 };
struct query q_arr[] = { { 0, 3 }, { 4, 5 }, { 1, 4 },
{ 0, 1 }, { 2, 5 } };
int n = sizeof(arr) / sizeof(arr[0]);
int m = sizeof(q_arr) / sizeof(q_arr[0]);
int d = 2;
cout << "Original Array:\n";
printArray(arr, n);
// modifying the array for multiple queries
incrementByD(arr, q_arr, n, m, d);
cout << "\nModified Array:\n";
printArray(arr, n);
return 0;
}
Java
// Java implementation to increment values in the
// given range by a value d for multiple queries
class GFG
{
// structure to store the (start, end)
// index pair for each query
static class query
{
int start, end;
query(int start, int end)
{
this.start = start;
this.end = end;
}
}
// function to increment values in the given range
// by a value d for multiple queries
public static void incrementByD(int[] arr, query[] q_arr,
int n, int m, int d)
{
int[] sum = new int[n];
// for each (start, end) index pair, perform
// the following operations on 'sum[]'
for (int i = 0; i < m; i++)
{
// increment the value at index 'start'
// by the given value 'd' in 'sum[]'
sum[q_arr[i].start] += d;
// if the index '(end+1)' exists then
// decrement the value at index '(end+1)'
// by the given value 'd' in 'sum[]'
if ((q_arr[i].end + 1) < n)
sum[q_arr[i].end + 1] -= d;
}
// Now, perform the following operations:
// accumulate values in the 'sum[]' array and
// then add them to the corresponding indexes
// in 'arr[]'
arr[0] += sum[0];
for (int i = 1; i < n; i++)
{
sum[i] += sum[i - 1];
arr[i] += sum[i];
}
}
// function to print the elements of the given array
public static void printArray(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[] arr = { 3, 5, 4, 8, 6, 1 };
query[] q_arr = new query[5];
q_arr[0] = new query(0, 3);
q_arr[1] = new query(4, 5);
q_arr[2] = new query(1, 4);
q_arr[3] = new query(0, 1);
q_arr[4] = new query(2, 5);
int n = arr.length;
int m = q_arr.length;
int d = 2;
System.out.println("Original Array:");
printArray(arr, n);
// modifying the array for multiple queries
incrementByD(arr, q_arr, n, m, d);
System.out.println("\nModified Array:");
printArray(arr, n);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation to increment
# values in the given range by a value d
# for multiple queries
# structure to store the (start, end)
# index pair for each query
# function to increment values in the given range
# by a value d for multiple queries
def incrementByD(arr, q_arr, n, m, d):
sum = [0 for i in range(n)]
# for each (start, end) index pair perform
# the following operations on 'sum[]'
for i in range(m):
# increment the value at index 'start'
# by the given value 'd' in 'sum[]'
sum[q_arr[i][0]] += d
# if the index '(end+1)' exists then decrement
# the value at index '(end+1)' by the given
# value 'd' in 'sum[]'
if ((q_arr[i][1] + 1) < n):
sum[q_arr[i][1] + 1] -= d
# Now, perform the following operations:
# accumulate values in the 'sum[]' array and
# then add them to the corresponding indexes
# in 'arr[]'
arr[0] += sum[0]
for i in range(1, n):
sum[i] += sum[i - 1]
arr[i] += sum[i]
# function to print the elements
# of the given array
def printArray(arr, n):
for i in arr:
print(i, end = " ")
# Driver Code
arr = [ 3, 5, 4, 8, 6, 1]
q_arr = [[0, 3], [4, 5], [1, 4],
[0, 1], [2, 5]]
n = len(arr)
m = len(q_arr)
d = 2
print("Original Array:")
printArray(arr, n)
# modifying the array for multiple queries
incrementByD(arr, q_arr, n, m, d)
print("\nModified Array:")
printArray(arr, n)
# This code is contributed
# by Mohit Kumar
C#
// C# implementation to increment values in the
// given range by a value d for multiple queries
using System;
class GFG
{
// structure to store the (start, end)
// index pair for each query
public class query
{
public int start, end;
public query(int start, int end)
{
this.start = start;
this.end = end;
}
}
// function to increment values in the given range
// by a value d for multiple queries
public static void incrementByD(int[] arr, query[] q_arr,
int n, int m, int d)
{
int[] sum = new int[n];
// for each (start, end) index pair, perform
// the following operations on 'sum[]'
for (int i = 0; i < m; i++)
{
// increment the value at index 'start'
// by the given value 'd' in 'sum[]'
sum[q_arr[i].start] += d;
// if the index '(end+1)' exists then
// decrement the value at index '(end+1)'
// by the given value 'd' in 'sum[]'
if ((q_arr[i].end + 1) < n)
sum[q_arr[i].end + 1] -= d;
}
// Now, perform the following operations:
// accumulate values in the 'sum[]' array and
// then add them to the corresponding indexes
// in 'arr[]'
arr[0] += sum[0];
for (int i = 1; i < n; i++)
{
sum[i] += sum[i - 1];
arr[i] += sum[i];
}
}
// function to print the elements of the given array
public static void printArray(int[] arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 3, 5, 4, 8, 6, 1 };
query[] q_arr = new query[5];
q_arr[0] = new query(0, 3);
q_arr[1] = new query(4, 5);
q_arr[2] = new query(1, 4);
q_arr[3] = new query(0, 1);
q_arr[4] = new query(2, 5);
int n = arr.Length;
int m = q_arr.Length;
int d = 2;
Console.WriteLine("Original Array:");
printArray(arr, n);
// modifying the array for multiple queries
incrementByD(arr, q_arr, n, m, d);
Console.WriteLine("\nModified Array:");
printArray(arr, n);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript implementation to increment values in the
// given range by a value d for multiple queries
// structure to store the (start, end)
// index pair for each query
class query
{
constructor(start,end)
{
this.start = start;
this.end = end;
}
}
// function to increment values in the given range
// by a value d for multiple queries
function incrementByD(arr,q_arr,n,m,d)
{
let sum = new Array(n);
for(let i=0;i<sum.length;i++)
{
sum[i]=0;
}
// for each (start, end) index pair, perform
// the following operations on 'sum[]'
for (let i = 0; i < m; i++)
{
// increment the value at index 'start'
// by the given value 'd' in 'sum[]'
sum[q_arr[i].start] += d;
// if the index '(end+1)' exists then
// decrement the value at index '(end+1)'
// by the given value 'd' in 'sum[]'
if ((q_arr[i].end + 1) < n)
sum[q_arr[i].end + 1] -= d;
}
// Now, perform the following operations:
// accumulate values in the 'sum[]' array and
// then add them to the corresponding indexes
// in 'arr[]'
arr[0] += sum[0];
for (let i = 1; i < n; i++)
{
sum[i] += sum[i - 1];
arr[i] += sum[i];
}
}
// function to print the elements of the given array
function printArray(arr,n)
{
for (let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Driver code
let arr = [3, 5, 4, 8, 6, 1 ];
let q_arr = new Array(5);
q_arr[0] = new query(0, 3);
q_arr[1] = new query(4, 5);
q_arr[2] = new query(1, 4);
q_arr[3] = new query(0, 1);
q_arr[4] = new query(2, 5);
let n = arr.length;
let m = q_arr.length;
let d = 2;
document.write("Original Array:<br>");
printArray(arr, n);
// modifying the array for multiple queries
incrementByD(arr, q_arr, n, m, d);
document.write("<br>Modified Array:<br>");
printArray(arr, n);
// This code is contributed by patel2127
</script>
Producción
Original Array: 3 5 4 8 6 1 Modified Array: 7 11 10 14 12 5
Complejidad temporal: O(m+n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Ayush Jauhari . 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