Sliding Window Aggregation (SWAG) (ds/swag.hpp)

Description

Sliding Window Aggregation (SWAG) maintains a queue and supports querying the aggregate of all elements in the queue under a monoid.

Example monoid:

struct Sum {
  using T = int;
  static T id() { return 0; }
  static T op(T l, T r) { return l + r; }
};

Operations

SWAG<M>()
- Constructs empty SWAG
- Time complexity: $\mathcal O(1)$
void push(const T &x)
- Pushes x to the back of the queue
- Time complexity: $\mathcal O(1)$ amortized
void pop()
- Pops from the front of the queue
- Time complexity: $\mathcal O(1)$ amortized
T front()
- Returns the front element
- Time complexity: $\mathcal O(1)$
T back()
- Returns the back element
- Time complexity: $\mathcal O(1)$
T query()
- Returns the aggregate of all elements in the queue
- Time complexity: $\mathcal O(1)$
int size()
- Returns the number of elements in the queue
- Time complexity: $\mathcal O(1)$
bool empty()
- Returns whether the queue is empty
- Time complexity: $\mathcal O(1)$

Verified with

test/yosupo/ds/queue_operate_all_composite.test.cpp

Code

#pragma once

template<class M> struct SWAG {
    using T = typename M::T;

    T front() const { return f.size() ? getf() : b.front()[0]; }
    T back() const { return b.size() ? getb() : f.back()[0]; }
    void push(const T &x) { b.push_back({x, M::op(getb<1>(), x)}); }
    void pop() {
        assert(size());
        if (f.empty()) {
            int n = size(), i = 0;
            vector<T> xs(n);
            for (; b.size(); b.pop_back()) xs[i++] = b.back()[0];
            for (i = 0; i < n; i++)
                f.push_back({xs[i], M::op(xs[i], getf<1>())});
        }
        f.pop_back();
    }

    T query() const { return M::op(getf<1>(), getb<1>()); }

    int size() const { return int(f.size() + b.size()); }
    bool empty() const { return size() == 0; }

    vector<array<T, 2>> f, b;
    template<int d = 0> T getf() const {
        return f.size() ? f.back()[d] : M::id();
    }
    template<int d = 0> T getb() const {
        return b.size() ? b.back()[d] : M::id();
    }
};

#line 2 "ds/swag.hpp"

template<class M> struct SWAG {
    using T = typename M::T;

    T front() const { return f.size() ? getf() : b.front()[0]; }
    T back() const { return b.size() ? getb() : f.back()[0]; }
    void push(const T &x) { b.push_back({x, M::op(getb<1>(), x)}); }
    void pop() {
        assert(size());
        if (f.empty()) {
            int n = size(), i = 0;
            vector<T> xs(n);
            for (; b.size(); b.pop_back()) xs[i++] = b.back()[0];
            for (i = 0; i < n; i++)
                f.push_back({xs[i], M::op(xs[i], getf<1>())});
        }
        f.pop_back();
    }

    T query() const { return M::op(getf<1>(), getb<1>()); }

    int size() const { return int(f.size() + b.size()); }
    bool empty() const { return size() == 0; }

    vector<array<T, 2>> f, b;
    template<int d = 0> T getf() const {
        return f.size() ? f.back()[d] : M::id();
    }
    template<int d = 0> T getb() const {
        return b.size() ? b.back()[d] : M::id();
    }
};