Multiple array range increments in linear time O(N)

algorithm
array
(Team) #1

Given an array A containing N integers, we perform M queries. Each query has three values START, END and a value D. For each query, the problem is to increment the values from the start to end index(both inclusive) in the given array by the given value d. A naive solution of leaping from start to end for each query is not feasible which takes O(NM) time whereas the efficient algorithm takes O(N+M) time complexity.

Read this article to understand Multiple array range increments in linear time O(N) in depth

Have a doubt or thought? Join the discussion now


This is a companion discussion topic for the original entry at http://iq.opengenus.org/multiple-array-range-increments-linear-time/