Noam527's blog

By Noam527, history, 9 months ago, In English,

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.

 
 
 
 
  • Vote: I like it  
  • +10
  • Vote: I do not like it  

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Noam527 (previous revision, new revision, compare).

»
9 months ago, # |
  Vote: I like it +23 Vote: I do not like it

There are some possible updates in the 3rd section of this paper.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Great, thanks! More are welcome of course.