ランキング計算以外も実現できる？

id:koherentさんがajn8向けに作成されたスライドを見ながら、同じことができるか考えてみました。
http://www.slideshare.net/koher/skiplists20100604

• P.36　リストの要素数･･･一番上の階層の保持する人数。O(1)で計算可能。
• P.37　要素番号による検索･･･要するに「○位の人は何点」。ランキング計算同様、O(log 16 (X))で計算可能。
• P.39　総和・平均･･･同様に、配列と一緒に格納された要素の総和を保持すれば可能。一番上のLayerから取得すれば良いので、O(1)でOK。
• P.40　範囲に対する集約･･･同様に実現可能。
• P.41　最大・最小・中央値･･･要素数番目・0番目・要素数/2番目の検索として実現可能。全部O(log 16 (X))。
• P.42　キー値以外の集約･･･これも同様に配列と一緒に保持すれば可能。
• P.43　キー値以外の最大・最小･･･これも同様にやれば多分可能そうですね。

という訳で、集計関係はほぼ同じ事が実現できそうです。

その他、Pagingは一応無理すれば条件付きで実現できそうなんですが･･･これに関しては無理やりな感じが否めないので、割愛します。