領域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、となる (Bとbは整数で、Bはbの整数倍とする) (必要に応じて番兵を入れてnを調整する)WM(ウェーブレット行列)を使うので数列は0以上n未満の整数値に変換する 順列に変換しても問題ないので変換後の数列は順列とするI(X) : 数列の区間Xの転倒数 I(X,Y) : 集合{(x,y)|x…