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

algorithm, data-structures, range-query

Solution

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`

Problem

Original source