ウェーブレット行列というデータ構造を使えば、文字列に対するrankクエリ（i.e.文字列の先頭から位置iまでの間にアルファベットcが何回出現したか）をO(log C)で処理できます。ただしCはアルファベットの数です。このテクニックを使うと、長さMのクエリ文字…