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.

Boar

Depends. What other operations are you planning to support? – Nudism

I need the final values of array A. – Boar

So, you're saying that you want to be able to store an array of elements and be able to 1) increment all of the elements in a range by that value and 2) query the value of any element in the array? – Nudism

loop through the intervals; for each interval use a for loop in increment each Array entry within the interval. If array access is too 'expensive', then make a new array of counts from all the intervals and access the A array just once. – Pyramid

Can the intervals overlap? If so, do you want to increment multiple times in the overlaps? – Preconize

@user2094963 Alright. I'll post with two different approaches; you can pick whichever that suits your use case. – Nudism

@TedHopp yes the intervals can overlap and i want to increment multiple times in the overlap area – Boar

Answer 1

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

Anaclinal

What if you don't know what the intervals are going to be beforehand? – Nudism

if i interpret the question correctly, the intervals are given as input or blocks of inputs – Mortenson

I guess I was thinking about the case where he's only going to get the intervals on an increment operation, and suppose he has to answer the queries as they come (i.e. no doing it all at once) – Nudism

that's a different case...maybe the question should be clarified – Mortenson

Isn't there an O(NlnN) for EACH of the beginning sorts? – Pyramid

@ZoltánNagy, could u explain "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 decrement increment" – Boar

i've used priorityqueue because this way it's easier to understand...in implementation i would use sorted index arrays – Mortenson

This is very inefficient if the intervals collectively affect many fewer elements than the array length. In fact, for a fixed set of intervals, there should be a constant-time algorithm regardless of the length of the array, while this approach always grows with the array length. – Preconize

@TedHopp now it's skipping 0 adding ;) – Mortenson

You're still iterating over the entire array, which is O(N) even if you do nothing at each index. For a fixed set of intervals, there should be a fixed-time solution regardless of the array length. – Preconize

@TedHopp no, i=min(s.peek(),e.peek()) jumped ahead – Mortenson

The complexity estimate is now wrong. It should be independent of n. – Preconize

@TedHopp: this skipping complicates the complexity estimate...i updated with something which is near to the correct – Mortenson

For non-overlapping sequences, \sum length(I_i) cannot possibly exceed n (unless there are out-of-bounds indexes in the intervals). The dependence on n should disappear. – Preconize

@TedHopp by using that min it would be more or less correct for overlappig cases too, i removed the constraint – Mortenson

Answer 2

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]

Harvestman

Awesome Solution! just one suggestion, At the time of creating B array, if j+1 <ArrayBounds then B[j+1] -=k else do_nothing – Concrete

Awesome....bdw what's the intuition behind this solution, Also do we have a formal name for this approach. – Rough

For future readers looking for the name of this method, it is called Difference Array. – Trismus

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

Nudism

can this problem be done using a normal segment tree? If yes, how? – Boar

Probably. I just think of these first. – Nudism

I get the feeling that solving this with a segment tree wouldn't be that much different from approach 2; think of each addOn as corresponding to a segment/interval over the elements in that subtree. – Nudism

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.

Preconize

i want the complexity to be much less than O(LN) where L is the length of the array and N is the number of intervals – Boar

@user2094963 - The complexity is O(MN) where M is the (average) length of an interval and N is the number of intervals. The length of the underlying array does not affect the number of operations in any way. The only way to perhaps do better is to preprocess the intervals, splitting when there are overlaps, and keep track of the increment amount for each interval. Even so, the complexity will still be O(MN), just with a reduced M and an increased N. (How this would affect the product MN depends on how much overlap you are dealing with.) Plus preprocessing will have its own complexity. – Preconize

Why not make an array of increments? Wouldn't that be O(L+N)? – Pyramid

@Jim - An array of increments is exactly what I suggested. However, the complexity is not O(L+N). Consider: if an interval is M long (M = j - i), then M increment operations are required; there is no getting around that (barring some hardware support for parallel processing, but I assume we are using an SISD machine). For N intervals, the complexity would thus be O(MN). I don't see how L (the length of the array) enters into the equation at all. – Preconize

@Ted If you combined the intervals in groups of two, and then combined the combinations, I think you could avoid some increments and maybe get to O(NlnM). – Pyramid

@Jim - How do you combine non-adjacent intervals into groups and gain any efficiency? – Preconize

@Ted Let's say you had N intervals with M length each (for simplicity) so total number of increments would be N*M. To combine a pair would be 2M. Combining together in groups of two, there are ln N pairings, so total is O(MlnN) (not as I said earlier). I'm assuming val += count is same cost as val++. – Pyramid

@Jim - Think about it: when you combine two intervals, there are still N-2 intervals with M elements and now 1 interval new with 2M elements. So you've replace MN with M(N-2) + 2M. Have you really changed anything? – Preconize

@Ted I was thinking you still have M elements, just that some might have a value greater than 1. [There is a shift from an interval to an array, which might be practically, if not theoretically, more time-consuming.] – Pyramid

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.
            }


    }
}

Concrete