# Finding $k$-th element in prefix of size $i$

Let's say we are given array $$A$$ of size $$n$$. We need to answer some numbers of queries. For each query we are given index $$i$$ and integer value $$k$$, $$k \le i$$. If we take the first $$i$$ elements of the array $$A$$ and we sort them we should return the one on index $$k$$ (we assume everything is 1 indexed).

I know that this can be solved in $$O(Q\log N)$$ if $$Q$$ is the number of our queries in offline way (we sort all queries by their index) and if we use persistent segment trees we can even make it work in online way (we can answer queries immediately), however I was wondering if there is simpler solution?

• I think that your answer is wrong - if we have just one query, we need O(n) time to answer it. – Bulat Jun 17 at 14:05

I misunderstood the original premise that A does not need to change. If you want a solution for that, a good one is to just apply the worst-case linear time selection algorithm on the original array for 0-i. This is O(i).

Assume A = [1, 0, 3, 5, 4, 7, 2, 1, 3] (inserted in that order)

There is a trivial solution to the problem at hand, and that is to store the data as so:

1
0 1
0 1 3
0 1 3 5
0 1 3 4 5
0 1 3 4 5 7
0 1 2 3 4 5 7
0 1 1 2 3 4 5 7
0 1 1 2 3 3 4 5 7


This is O(n^2) space and preprocessing, but is O(1) retrieval. It is very fast and simple, and honestly the best solution.

In order to achieve "subquadratic preprocessing", you can store this matrix type array in a sparse manner:

1,2
0,0
3,2
0 1 3
5,4
4,3
7,5
0 1 3 4 5 7
2,3
1,2
3,5
0 1 1 2 3 3 4 5 7


This is O(nlog(n)) preprocessing and O(nlog(n)) space, but O(log(n)) time. You choose the gaps by computing floor(log(n)) (or ceil it does not matter) and then fill in the gaps with the elements deleted and the index that they were deleted from in the bigger array (not the smaller one). When searching given an i and k, compute ceil(i/floor(log(n))) to determine which array to start from, and then delete items from that array (do not copy it, as that will make this algorithm O(n)). When you delete an item to the right of your k, you do nothing. Delete an item to the left, and just increment your k to the next undeleted spot. By keeping track of where the last deleted item was you'll never have to traverse the array. Finally, when you reach your i, the k will be pointing to the answer. At this point, just unwind and reinsert the deleted values back in to the array.

Example with i = 7, k = 6:

1. Start with 0 1 1 2 3 3 4 5 7, with k pointing at 6
2. Delete at index 5, increment k: 0 1 1 2 3 _ 4 5 7 k=7, i=8
3. Delete at index 2, increment k: 0 1 _ 2 3 _ 4 5 7 k=8, i=7
4. i=i that we started at, so we return A[8] which is 7, and now unwind:
5. 0 1 1 2 3 _ 4 5 7
6. 0 1 1 2 3 3 4 5 7

This next solution was the one I was working on when I came up with the above solution (which I think is the best given the constraints). I will leave it in case if someone finds a use for it.

This solution is overly complicated for minimal gains, but matches the "subquadratic preprocessing" constraint. It is also O(n^2) space but is O(nlog(n)) preprocessing. It is O(log(n)) time.

Lets look at this problem in the simple i = n case: we need a data structure that is responsive to updates and can solve the selection problem fast. Here is such a data structure (sorted array for reference):

     1,1
/       \
0,0       3,3
/   \
2,2   5,3
/    /   \
1,1  4,2   7,1
/
3,1

[0, 1, 1, 2, 3, 3, 4, 5, 7]


Let's say you want to find what was at index 2: start at 1,1 at the top; 1 < 2 so now you subtract 1 from the index you were searching for, and go to the right child. 3 > 1, so you go to the left child, and don't change your current index value. Same goes for 2,2, until you reach 1,1, which is at index 1 + 1 which is 2.

This structure is a binary tree that stores each value and its position relative to the nearest parent that it the right child of. This allows you to insert an item and have the changes be reflected across nodes you haven't touched during the insert. For example, if you insert -1 right now, which becomes 0s left child, you need to touch 1 and 0, and update their positions to 2 and 1 respectively. This automatically shifts everything to the right of 1 rightwards one as well. You can even balance this tree; just make sure to update the new parent by subtracting its left parent's value from it's value.

Now to solve the general case: instead of storing just one index, we store:

1. A number representing its position in the original A
2. A list of "previous indices" that the item was at in the sorted arrays

You build this tree just as you build a normal binary tree, except that every time you touch a node, you update it's relative position at that "time" i. Here is an example tree with a small array

A = [1, 0, 3, 5]

    1,0[0,1,1,1]
/       \
0,1[0]     3,2[1,1]
\
5,3[1]


You find the kth index at "time" i by traversing the tree just as above, except you subtract the index you're looking for from the stored index at that node, then index into the list. Instead of going out of bounds, the list also stores the most recent entry. When you add a new entry, you fill in the most recent value for all i up to where you just inserted. If the i you're looking for exceeds the i stored at that node, just use the value at the array index 0 of the node and compare it to the index you're looking for (this only happens if you balance the tree). If this sounds familiar, it's because this is a type of union-set data structure.

For the above tree, finding i = 2, k = 2, you start at the top, subtract your i from 1s i, getting 2 - 0 = 2 and checking it's array at 2, which gives you 1. This is too small, so we subtract the k that we found from our k giving us 1, and move right. Next we encounter 3, we subtract our i = 2 - 2 = 0 and check the array at index 0 giving us 1 which matches our k, which is the answer.

Overly complex solution, but does manage to satisfy the requirements. Additionally, it can actually handle A changing! Balancing the tree is costly, however.

• I think we're looking for an algorithm running in polylogarithmic time (after subquadratic preprocessing). – Yuval Filmus Jun 17 at 19:49
• But this is $O(nk)$ in time. Finally if you just do the same on the original array, you achieve $O(ik)$. What is the interest of this structure ? – Vince Jun 17 at 20:32
• I misunderstood the original question, I will update my answer – hLk Jun 17 at 20:34
• Okay I just did not understand the "and traverse the stored list $n$ times" which is misleading. Now I understand how it works. – Vince Jun 18 at 7:40
• We are looking for solution that is better than linear, $O(\log N)$ for each query is doable with persistent segment trees, however it is a bit hard to implement. Also, we don't need deletes and inserts, the initial array is going to be the same through the process. – someone12321 Jun 18 at 11:31