How to increment all values in an array interval by a given amount

algorithm data-structures range-query
SHB picture SHB · Aug 23, 2013 · Viewed 14.5k times · Source

Suppose i have an array A of length L. I will be given n intervals(i,j) and i have to increment all values between A[i] and A[j].Which data structure would be most suitable for the given operations?
The intervals are known beforehand.

Answer

adrian.budau picture adrian.budau · Aug 23, 2013

You can get O(N + M). Keep an extra increment array B the same size of A initially empty (filled with 0). If you need to increment the range (i, j) with value k then do B[i] += k and B[j + 1] -= k

Now do a partial sum transformation in B, considering you're indexing from 0:

for (int i = 1; i < N; ++i) B[i] += B[i - 1];

And now the final values of A are A[i] + B[i]

Related questions

How to implement a queue using two stacks?

Suppose we have two stacks and no other temporary variable. Is to possible to "construct" a queue data structure using only the two stacks?

Read More
How to create the most compact mapping n → isprime(n) up to a limit N?

Naturally, for bool isprime(number) there would be a data structure I could query. I define the best algorithm, to be the algorithm that produces a data structure with lowest memory consumption for the range (1, N], where N is a …

Read More
What is the difference between tree depth and height?

This is a simple question from algorithms theory. The difference between them is that in one case you count number of nodes and in other number of edges on the shortest path between root and concrete node. Which is which?

Read More