Then we move on to dynamic tries, where we achieve a worst-case bound of O(m+lg^2(s)/lglg(s)) per query or update, which should again be compared to the previously known O(m+lg(s)) deterministic worst-case bounds [Cole et al., ICALP'06], and to the alphabet independent O(m+sqrt(lg(n)/lglg(n))) deterministic worst-case bounds [Andersson and Thorup, SODA'01], where n is the number of nodes in the trie. The basis of our update procedure is a weighted variant of exponential search trees which, while simple, might be of independent interest.
As one particular application, the above bounds (static and dynamic) apply to suffix trees.