スライド区間の昇順 k 個の和
説明
スライドする区間の昇順(降順) $k$ 個の総和を効率良く求めるデータ構造。
使い方
- $\mathrm{PrioritySumStructure}(k, order = \mathrm{INCREASE})$: 昇順(降順) $k$ 個に指定。
- $\mathrm{addElement}(k, x)$: $k$ 番目の要素 $x$ を追加する。
- $\mathrm{deleteElement}(k)$: $k$ 番目の要素を削除する。
- $\mathrm{getSum}()$: 昇順 $k$ 個の和を返す。
- $\mathrm{incrementSize}()$: $k$ を $1$ 増やす。
- $\mathrm{decrementSize}()$: $k$ を $1$ 減らす。
計算量
$O(\log n)$
但しsetを $4$ 個持っていて定数倍が重いので注意。
実装例