SWAG のライブラリを書きました.ソースはこちら
使用法
auto sw1 = make_swag(plus<ll>(), 0LL);
auto sw = make_swag(multiplies<MyMatrix>(), MyMatrix{{1,0},{0,1}});
// operator and its unit element.
// operator should be associative.
sw.push(obj1); // push obj1 into the queue
sw.pop(); // pop the front element
T v = sw.get_val(); // calculate the aggregated value e1 `op` e2 `op` ... `op` en
// where e1 is the front and en is the back
T a = sw.front(); // the front element
T b = sw.back(); // the back element
auto vec = sw.vec_view(); // list the elements for debugging
メモ
- SWAG = Sliding Window AGgregation
- 結合法則を満たす (実装の都合上単位元も持つ) 演算
- 機能:
- queue に push
- queue から pop
- queue の要素全体に演算を適用 (fold).入れた順に左から
- 計算量: push, pop, 演算適用とも,ならし $O(1)$.
- 4本のスタック (要素と値,後ろ半分と前半分) で実現.