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

Question

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 1

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]

Answer 2

break all intervals into start and end indexes: s_i,e_i for the i-th interval which starts including s_i and ends excluding e_i

sort all s_i-s as an array S sort all e_i-s as an array E

set increment to zero start a linear scan of the input and add increment to everyone, in each loop if the next s_i is the current index increment increment if the next e_i is index decement increment

inc=0
s=<PriorityQueue of interval startindexes>
e=<PriorityQueue of interval endindexes>
for(i=0;i<n;i++){
  if( inc == 0 ){
    // skip adding zeros
    i=min(s.peek(),e.peek())
  }
  while( s.peek() == i ) {
    s.pop();
    inc++;
  }
  while( e.peek() == i ) {
    e.pop();
    inc--;
  }
  a[i]+=inc;
}

complexity(without skipping nonincremented elements): O(n+m*log(m)) // m is the number of intervals if n>>m then it's O(n)

complexity when skipping elements: O( min( n , \sum length(I_i) ) ), where length(I_i)=e_i-s_i