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

Answer 3

There are three main approaches that I can think of:

Approach 1

This is the simplest one, where you just keep the array as is, and do the naive thing for increment.

• Pros: Querying is constant time
• Cons: Increment can be linear time (and hence pretty slow if L is big)

Approach 2

This one is a little more complicated, but is better if you plan on incrementing a lot.

Store the elements in a binary tree so that an in-order traversal accesses the elements in order. Each node (aside from the normal left and right subchildren) also stores an extra int addOn, which will be "add me when you query any node in this tree".

For querying elements, do the normal binary search on index to find the element, adding up all of the values of the addOn variables as you go. Add those to the A[i] at the node you want, and that's your value.

For increments, traverse down into the tree, updating all of these new addOns as necessary. Note that if you add the incremented value to an addOn for one node, you do not update it for the two children. The runtime for each increment is then O(log L), since the only times you ever have to "branch off" into the children is when the first or last element in the interval is in your range. Hence, you branch off at most 2 log L times, and access a constant factor more in elements.

• Pros: Increment is now O(log L), so now things are much faster than before if you increment a ton.
• Cons: Queries take longer (also O(log L)), and the implementation is much trickier.

Approach 3

Use an interval tree.

• Pros: Just like approach 2, this one can be much faster than the naive approach
• Cons: Not doable if you don't know what the intervals are going to be beforehand.
  Also tricky to implement

Answer 4

Solve the problem for a single interval. Then iterate over all intervals and apply the single-interval solution for each. The best data structure depends on the language. Here's a Java example:

public class Interval {
    int i;
    int j;
}

public void increment(int[] array, Interval interval) {
    for (int i = interval.i; i < interval.j; ++i) {
        ++array[i];
    }
}

public void increment(int[] array, Interval[] intervals) {
    for (Interval interval : intervals) {
        increment(array, interval);
    }
}

Obviously you could nest one loop inside the other if you wanted to reduce the amount of code. However, a single-interval method might be useful in its own right.

EDIT

If the intervals are known beforehand, then you can improve things a bit. You can modify the Interval structure to maintain an increment amount (which defaults to 1). Then preprocess the set of intervals S as follows:

1. Initialize a second set of intervals T to the empty set
2. For each interval I in S: if I does not overlap any interval in T, add I to T; otherwise:
3. For each interval J in T that overlaps I, remove J from T, form new intervals K₁...K_n from I and J such that there are no overlaps (n can be from 1 to 3), and add K₁...K_n to T

When this finishes, use the intervals in T with the earlier code (modified as described). Since there are no overlaps, no element of the array will be incremented more than once. For a fixed set of intervals, this is a constant time algorithm, regardless of the array length.

For N intervals, the splitting process can probably be designed to run in something close to O(N log N) by keeping T ordered by interval start index. But if the cost is amortized among many array increment operations, this isn't all that important to the overall complexity.

Answer 5

A Possible implementation of O(M+N) algorithm suggested by Adrian Budau

import java.util.Scanner;

class Interval{
    int i;
    int j;
}

public class IncrementArray {
    public static void main(String[] args) {
        int k= 5;                                   // increase array elements by this value
        Scanner sc = new Scanner(System.in);
        int intervalNo = sc.nextInt();                // specify no of intervals
        Interval[] interval = new Interval[intervalNo];           // array containing ranges/intervals
        System.out.println(">"+sc.nextLine()+"<");
        for(int i=0;i<intervalNo;i++)
        {
            interval[i]= new Interval();
            String s = sc.nextLine();                             // specify i and j separated by comma in one line for an interval.
            String[] s1 = s.split(" ");
            interval[i].i= Integer.parseInt(s1[0]);
            interval[i].j= Integer.parseInt(s1[1]);
        }
        int[] arr = new int[10];           // array whose values need to be incremented.
        for(int i=0;i<arr.length;++i)
            arr[i]=i+1;                    // initialising array.
        int[] temp = new int[10];
        Interval run=interval[0]; int i;
        for(i=0;i<intervalNo;i++,run=interval[i<intervalNo?i:0] )  // i<intervalNo?i:0 is used just to avoid arrayBound Exceptions at last iteration.
        {
            temp[run.i]+=k;
            if(run.j+1<10)                                          // incrementing temp within array bounds.
            temp[run.j +1]-=k;
        }
        for (i = 1; i < 10; ++i) 
            temp[i] += temp[i - 1];

        for(i=0, run=interval[i];i<10;i++)
            {
                arr[i]+= temp[i];
                System.out.print(" "+arr[i]);                     // printing results.
            }


    }
}