Dynamic Data structure for All nearest smaller values
If you modify a balanced binary search tree (whose inorder traversal is the sequence order) so that each node stores the minimum value of its descendants (and if you know the path to x) then you can easily find the nearest smaller value: it must either be on the path to x, or in a left subtree descending from the path. In the first case, you have a logarithmic number of nodes to check, and in the second case you can use the extra information to find the closest left subtree with a value smaller than x and then descend through it along the rightmost path that still has a value smaller than x. So the time per query or update is logarithmic.

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.