原文：
给定一个包含n整数和值d的数组。 给出m个查询。 每个查询具有两个值start和end。 对于每个查询，问题是将给定数组中从start到end索引的值增加给定值d。 需要线性省时的pg电子试玩链接的解决方案来处理此类多个查询。
示例：
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.
朴素的方法：对于每个查询，遍历start到end范围内的数组，并将该范围内的值增加给定值d。
有效方法：创建大小为n的数组sum[]并将其所有索引初始化为 0。现在，对于每个start, end索引对在sum[]数组上应用给定的运算。 仅当存在索引end 1时，操作才是sum[start] = d和sum[end 1] -= d。 现在，从索引i = 1到n-1，将sum[]数组中的值累加为：sum[i] = sum[i-1]。 最后，对于索引i = 0到n-1，执行以下操作：arr[i] = sum[i]。
c
// c implementation to increment values in the
// given range by a value d for multiple queries
#include
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
输出：
original array:
3 5 4 8 6 1
modified array:
7 11 10 14 12 5
时间复杂度：o(m n)。
辅助空间：o(n)。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
