# Dynamic Data structure for All nearest smaller values

I need a data structure that stores a sequence of numbers and supports the following operations. The input to each operation includes the position of an item in the current sequence (not the value or the memory address of that item).

• $\mathtt{NearestSmaller}(i)$: Return the value of the last item in the sequence that occurs before position $i$ and whose value is less than the value at position $i$.

• $\mathtt{InsertBefore}(x, i)$: Insert a new item with value $x$ into the sequence just before the item with position $i$.

• $\mathtt{Delete}(i)$: Delete item at position $i$ from the sequence.

In short, my question is whether there is a dynamic version of the all nearest smaller neighbors algorithm.

For example, if the current sequence is $X = [9,7,3,1,8,12,10,20,15,5]$, then

• $\mathtt{NearestSmaller}(6)$ should return $8 = X$, and

• $\mathtt{NearestSmaller}(10)$ should return $1 = X$.

• Edited for clarity. Please verify that I haven't changed the question. In particular, I wasn't sure what you actually intended as the input to the insertion and deletion functions. (Direct pointer? Rank? Value? Something else?) Mar 3 '13 at 16:58
• Thank you,my dear friend,I will re-edit to make it more clear.
– Vk1
Mar 4 '13 at 17:40
• Re-edited for precision and consistency. Again, it's unclear whether the intended input is the position or the address of the item in the sequence. It's also unclear whether the ambiguous term "nearest" is supposed to mean "furthest to the right" or "closest in value". Mar 5 '13 at 6:55
• Now it is pretty clear. If it is still not clear,I request you to refer to this link en.wikipedia.org/wiki/All_nearest_smaller_values and try to find a datastructure to implement its dynamic version.
– Vk1
Mar 5 '13 at 15:09
• Edited for concision. "Position smaller than and closest to $i$" is the same as "last before position $i$". Mar 5 '13 at 18:53

Edited to add: Now that you have clarified that you want to identify items in the sequence by their position, you should also augment the search tree so that each node stores its number of descendants. With this information, it is straightforward to find the path to the item at position $i$, in logarithmic time, matching the time described above for the NearestSmaller query.