Sliding Window Aggregation (SWAG)
(DataStructure/SlidingWindowAggregation.cpp)

• View this file on GitHub
• Last update: 2021-09-20 19:48:28+09:00

説明

半群 $(S,\bullet)$ とその配列 $(a_0,a_1,\cdots,a_{N - 1})$ を扱う。

実装は、キューをスタック 2 個で表現する方法を用いている。

• SWAG<S> swag(std::function<S(S,S)>) : 空の配列を作成する。
• bool swag.empty() : 配列が空であるかを確かめる。時間計算量 $O(1)$
• S swag.fold_all() : $a_0 \bullet a_1 \bullet \cdots \bullet a_{N - 1}$ を求める。時間計算量 $O(1)$
• S swag.push(S x) : 配列に $x$ を追加する。時間計算量 $O(1)$
• S swag.pop() : 配列の先頭の要素を削除する。時間計算量 $O(1)\ \mathrm{amortized}$

Verified with

• Test/yosupo-judge/SlidingWindowAggregation.test.cpp

Code

template<class T>
class SWAG {
    class Node {
    public:
        T val,sum;
        Node(const T& val,const T& sum) : val(val),sum(sum) {}
    };

    std::stack<Node> front_stack,back_stack;
    function<T(T,T)> op;

public:
    SWAG(const function<T(T,T)> op) : op(op) {}

    bool empty() {
        return front_stack.empty() && back_stack.empty();
    }

    T fold_all() {
        assert(!empty());
        if(front_stack.empty()) {
            return back_stack.top().sum;
        }
        else if(back_stack.empty()) {
            return front_stack.top().sum;
        }
        else {
            return op(front_stack.top().sum,back_stack.top().sum);
        }
    }

    void push(T x) {
        if(back_stack.empty()) back_stack.emplace(x,x);
        else back_stack.emplace(x,op(back_stack.top().sum,x));
    }

    void pop() {
        assert(!empty());
        if(front_stack.empty()) {
            front_stack.emplace(back_stack.top().val,back_stack.top().val);
            back_stack.pop();
            while(!back_stack.empty()) {
                T tmp{op(back_stack.top().val,front_stack.top().sum)};
                front_stack.emplace(back_stack.top().val,tmp);
                back_stack.pop();
            }
        }
        front_stack.pop();
    }
};

#line 1 "DataStructure/SlidingWindowAggregation.cpp"
template<class T>
class SWAG {
    class Node {
    public:
        T val,sum;
        Node(const T& val,const T& sum) : val(val),sum(sum) {}
    };

    std::stack<Node> front_stack,back_stack;
    function<T(T,T)> op;

public:
    SWAG(const function<T(T,T)> op) : op(op) {}

    bool empty() {
        return front_stack.empty() && back_stack.empty();
    }

    T fold_all() {
        assert(!empty());
        if(front_stack.empty()) {
            return back_stack.top().sum;
        }
        else if(back_stack.empty()) {
            return front_stack.top().sum;
        }
        else {
            return op(front_stack.top().sum,back_stack.top().sum);
        }
    }

    void push(T x) {
        if(back_stack.empty()) back_stack.emplace(x,x);
        else back_stack.emplace(x,op(back_stack.top().sum,x));
    }

    void pop() {
        assert(!empty());
        if(front_stack.empty()) {
            front_stack.emplace(back_stack.top().val,back_stack.top().val);
            back_stack.pop();
            while(!back_stack.empty()) {
                T tmp{op(back_stack.top().val,front_stack.top().sum)};
                front_stack.emplace(back_stack.top().val,tmp);
                back_stack.pop();
            }
        }
        front_stack.pop();
    }
};

Back to top page