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 , 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, for those who are interested.
Auto comment: topic has been updated by Noam527 (previous revision, new revision, compare).
There are some possible updates in the 3rd section of this paper.
Great, thanks! More are welcome of course.