noshi91のメモ

データ構造のある風景

スライド最小値を半群に一般化する

概要

以前記事を書いたのですが消したので別の場所にもう一度書きました。 今度はある程度まともな実装付きです (その分遅いですが)。

Sliding Window Aggregation - data-structures



計算量解析

Queue の場合

ポテンシャル関数を  \lbrace 末尾側の \  \rm stack \  の要素数 \rbrace で定義します。

Deque の場合

ポテンシャル関数を  \rm abs ( \lbrace 先頭側の \  \rm stack \  の要素数 \rbrace - \lbrace 末尾側の \  \rm stack \  の要素数 \rbrace ) で定義します