Sliding Window Aggregation

Info

末尾追加と先頭消去の操作が可能な半群の列のfoldができるデータ構造

Complexity

末尾追加 - \(O(1)\ \text{amortized}\)
先頭消去 - \(O(1)\ \text{amortized}\)
全体fold - \(O(1)\)

Interface

SWAG<T>(func g) 要素の型\(T\)と関数\(g:(T,T)\rightarrow T\)で初期化する
push(T a) 末尾に\(a\)を追加する
pop() 先頭から要素を一つ消去する
fold_all() 全体をfoldした値を返す

Code

using lnt = long long;
/* <SWAG> */

template <typename T = lnt>
struct SWAG
{
	std::stack<T> f,b,fa,ba;
	const std::function<T(T,T)> g;
	SWAG(std::function<T(T,T)> g)
		: g(g) {}
	bool empty() const { return f.empty()&&b.empty(); }
	void push(T a) {
		b.emplace(a);
		if(ba.empty()) ba.emplace(a);
		else ba.emplace(g(ba.top(),a));
	}
	void pop() {
		assert(!empty());
		if(f.empty()) {
			while(!b.empty()) {
				f.emplace(b.top()); b.pop(); ba.pop();
				if(fa.empty()) fa.emplace(f.top());
				else fa.emplace(g(f.top(), fa.top()));
			}
		}
		f.pop(); fa.pop();
	}
	T fold_all() const {
		assert(!empty());
		if(fa.empty()) return ba.top();
		if(ba.empty()) return fa.top();
		return g(fa.top(),ba.top());
	}
};

/* <SWAG> */

Examples

SWAG<int> sw([](int a, int b){return std::gcd(a,b)});
sw.push(2);
sw.push(4);
sw.push(8);
sw.push(16);
std::cout << sw.fold_all() << '\n'; // 2
sw.pop();
std::cout << sw.fold_all() << '\n'; // 4
sw.push(6);
std::cout << sw.fold_all() << '\n'; // 2