I have a question about a seemingly-simple problem I came up with which I just can't quite solve. In short, given an array $A$ of integers, I want to support **queries** and **updates**:↵
↵
- **Queries** give you an index $i$, and ask for the **largest value $A[j]$ where $j \geq i$ but $A[j] \leq A[i]$**.↵
- **Updates** simply append a value to the array.↵
↵
My goal is to support both queries and updates in $O(\log{n})$ time (where $n$ is the size of $A$ immediately before the operation) after an at-most $O(n\log{n})$ preprocessing.↵
↵
Now, my initial idea was to maintain a **BST**forcontaining the values in every suffix of $A$, and specifically use **persistent BSTs** to save storage (turning $O(n^2)$ storage into $O(n\log{n})$ storage needed). Then, given an index $i$, I would simply query the BST corresponding to the suffix starting at $A[i]$ to get the answer. However, my idea does **not** support updates. This is because appending a value to the array **changes ALL the suffixes** of the array, which in turn would require me to update all the BSTs I had kept for each suffix of the *previous* array, which would require $O(n\log{n})$ time.↵
↵
However, I haven't been able to think of how to solve this issueI had another idea, which was to keep one big BST for the entire array. This BST would be **keyed by index**, so that for suffix queries, I could just take $O(\log{n})$ nodes in the BST that correspond to any suffix. Furthermore, updates are easy: simply insert $(|A|, \text{new value})$ for every new value received. However, the problem here is that by having the BST not be keyed by the array values themselves, I think we lose the ability to efficiently find the maximum value at most a certain value, making queries devolve to linear time.↵
↵
I've spent quite some time thinking about how to turn these ideas into a full solution, but I haven't been able to find a way. Can someone provide hints or a solution to this problem?
↵
- **Queries** give you an index $i$, and ask for the **largest value $A[j]$ where $j \geq i$ but $A[j] \leq A[i]$**.↵
- **Updates** simply append a value to the array.↵
↵
My goal is to support both queries and updates in $O(\log{n})$ time (where $n$ is the size of $A$ immediately before the operation) after an at-most $O(n\log{n})$ preprocessing.↵
↵
Now, my initial idea was to maintain a **BST**
↵
↵
I've spent quite some time thinking about how to turn these ideas into a full solution, but I haven't been able to find a way. Can someone provide hints or a solution to this problem?
