Querying suffixes while supporting appends

Revision en1, by Anthony_Smith, 2025-03-15 22:26:06

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 for 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 issue. Can someone provide hints or a solution to this problem?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Anthony_Smith 2025-03-15 22:37:06 13 Tiny change: 'tain value, making ' -> 'tain value in a subtree, making '
en2 English Anthony_Smith 2025-03-15 22:33:16 648 add second idea
en1 English Anthony_Smith 2025-03-15 22:26:06 1304 Initial revision (published)