Given a sorted array
1 2 3 4 5 6 7 8
and an operation that takes the N-th element out the array and puts it in front (or rotates the first N elements to the right by one), leaving the following for N = 3
4 1 2 3 5 6 7 8
I need to be able to figure out the state of the array, after performing an arbitrary number of these operations.
I've implemented a simple algorithm using
std::rotate that simulates this behavior, but the problem is that my input data set is too large, and rotating the physical array gets really slow.
I've also tried doing this in a
std::list (linked list), while keeping a separate array of pointers to every K-th element, so that I could access anywhere in the list in near constant time, while benefiting from the fast removal. This approach requires moving the pointers (or iterators in my implementation) every time I rotate, but since I have less pointers than the actual elements in the array (say 1 pointer per 1000 list elements), this isn't so expensive. All in all, this solution turns out to be about 2 times faster than the vector in some cases, in others it's less fast, but it's still too slow.
I don't need to store the actual array, I only need to be able to compute the value of any element in it. I can see how to do this easily if I only had to do one rotation, where the 0th index would be the rotated element, everything before the rotated element would be shifted one to the right by one and everything on the right side of the element would be kept in place, but I don't see how to keep this up when I do multiple rotations.
One of the possible solutions I found was using interval trees, though this seems rather complex and I'm not sure if it would be more efficient given the high number of rotations needed.
TL;DR: Given a sequence of the first N natural numbers, perform K rotations and figure out the final state of the sequence. For the sake of example, set N = 10^6 and K = 10^5.