What updates are available to a wavelet tree?
Difference between en1 and en2, changed 135 character(s)
Usually the wavelet tree is made not to support updates. I wonder what types of updates it can recieve that will still keep all its operations in $O(\log{}A)$, where $A$ is the range of values it gets. For instance the only one I found is that you can support appending or removing the element from the back of the array (on which the wavelet is built).

A short tutorial for this data structure can be found [here](http://codeforces.me/blog/entry/52854), for those who are interested.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Noam527 2017-12-11 18:17:38 135
en1 English Noam527 2017-12-11 18:12:31 398 Initial revision (published)