Sliding Window Aggregation - data-structures

#Sequences Operations 半群の列 を扱う． 空間計算量 空の状態でデータ構造を作成する 時間計算量 を計算する 時間計算量 を末尾に追加する 時間計算量 を削除する 時間計算量 Summary Queue をつの Stack でシミュレートする技法を用いる それぞれの Stack は要素の他に、最初の要素からその位置までの累積和も管理する 先頭側の Stack 全体と末尾側の Stack 全体の fold 結果はわかっているので，それらを結合すればに答えられる 先頭側の Stack が空でないとき，単に先頭側の Stack を pop する 先頭側の Stack が空になった際に末尾側の Stack の全要素を反転して先頭にする この操作にはかかるが，つの要素が Stack に される回数を考えると償却定数時間になることが言える． References Knapsack