WTの詳しくはここで読んでください。

• 汎用性が高く
• 計算量が低く
• メモリ量が少なく

という原因で、WTがすごく大事なデータ構造です。
Tのテキスト、とQのクエリとのWTは次の操作を定時間でサポートできる。

• Lookup  ( T, pos) T[pos]を返す
• Rank_c    ( T, pos) T[0, pos]中のcの出現回数を返す
• Selectc  ( T, pos)　　(i+1)番目のcの位置を返す
• Quantile ( T, p, sp, ep)　　T[sp,ep]中の文字の大順番のp+1番目の文字を返す
• FreqList ( T, p, sp, ep)　　T[sp,ep]中の出現頻度の大順番のp+1番目の文字を返す
• RangeList( T, sp, ep, min, max) 　　Return{T[i]}s.t.min≦[i]<max,sp≦i<ep
• RangeFreq( T, sp, ep, min, max) Return|RangeList(T,sp,ep,min,max)|