Efficient algorithm for joining sieves

Question

I'm trying to find an efficient algorithm for the following algorithm.

I have a sequence consisting of lists of indices denoting indices to be removed. The semantics are such that each sequence must be performed in order. I want to take these sequences and flatten them into one sequence of absolute indices to be removed.

This can be achieved by performing a series of sieves (somewhat akin to the Sieve of Eratosthenes). The caveat is that this technique is slow (quadratic).

Thus this group of relative indices:

R0: 0 3 10 15
R1: 2 7 20
R2: 1 11 12 14 17
R3: 0 1 2

Would correspond to this group of absolute indices:

A0: 0 3 10 15
A1: 4 9 22
A2: 2 17 18 20 24
A3: 1 5 6

And when merged into one sequence of absolute indices, I would have the following:

A': 0 1 2 3 4 5 6 9 10 15 17 18 20 22 24

There may be any number of relative sequences, each of which may contain any number of elements and may have large gaps between indices. The input relative sequences are sorted in increasing order any may not contain duplicates.

Obtaining the intermediate A# lists is unnecessary. I only care about the list A' from the inputs R#.

---

Clarification on the algorithm

Let's take the list of non-negative integers

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ...

And remove the indices given by R0

Then we have

1 2 4 5 6 7 8 9 10 11 12 13 14 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ...

The removed values yield A0 (0 3 10 15)

Now remove the indices given by R1

1 2 5 6 7 8 10 11 12 13 14 16 17 18 19 20 21 23 24 25 26 27 28 29 30 ...

The removed values yield A1 (4 9 22)

Now remove the indices given by R2

1 5 6 7 8 10 11 12 13 14 16 19 21 23 25 26 27 28 29 30 ...

The removed values yield A2 (2 17 18 20 24)

Now remove the indices given by R3

7 8 10 11 12 13 14 16 19 21 23 25 26 27 28 29 30 ...

The removed values yield A3 (1 5 6)

Answer 1

Your complexity analysis is wrong. Generating each intermediate list is linear. Merging the lists if the final list has n elements and you have k intermediate lists is O(k n) with a naive algorithm, and O(n log(k)) if you use a standard priority queue (which under the hood is probably a heap).

The only quadratic operation is removing the elements from the long list. Odds are that you are calling a method to remove an element, which is going to have to recopy the whole list. That is linear per element removed, which will scale quadratically when you remove a lot of elements.

Instead what you need to do is run through the list, keeping track of where you are copying from and where you are copying to. When you run across elements to skip, just move the "copying from" location and don't copy. When you finish running through the whole list, then change the length of the data to the last location you copied from.