領域O(n)、構築O(n*sqrt(n/log(n)))、クエリO(sqrt(n*log(n)))、を示す数列を大バケットと小バケットの2種類のバケットで分割するn : 数列長 B : 大バケットのサイズ b : 小バケットのサイズ n=Bb大バケットがb個ある、小バケットがB個ある、b≦sqrt(n)≦B、と…

WM(ウェーブレット行列)は上位ビットからの基数ソートのようなものであること、基数ソートを1ビット単位で行うより8ビット単位で行うほうが速そうであること、以上のことから動的WMも8ビット単位で行うと速くなるかもしれないので試すことにした次の処理がで…