Deque Aggregation (ds/deque_aggregation.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-09-20 15:32:13+07:00
• Include: #include "ds/deque_aggregation.hpp"

Description

Deque Aggregation maintains a double-ended queue with range query support under a monoid. Supports push/pop at both ends and querying the product of all elements in $\mathcal O(1)$ amortized time per operation. Example monoid:

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

Operations

• DequeAggregation<M>()
  • Constructs empty deque aggregation
  • Time complexity: $\mathcal O(1)$
• T front() or T back()
  • Returns the front/back element
  • Time complexity: $\mathcal O(1)$
• void push_front(const T &x) or void push_back(const T &x)
  • Inserts element at front/back
  • Time complexity: $\mathcal O(1)$ amortized
• void pop_front() or void pop_back()
  • Removes element from front/back
  • Time complexity: $\mathcal O(1)$ amortized
• T query()
  • Returns the product of all elements in the deque
  • Time complexity: $\mathcal O(1)$
• int size() or bool empty()
  • Returns size or whether deque is empty
  • Time complexity: $\mathcal O(1)$

Verified with

• test/yosupo/ds/deque_operate_all_composite.test.cpp

Code

#pragma once

template<class M> struct DequeAggregation {
    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_front(const T &x) { f.push_back({x, M::op(x, getf<1>())}); }
    void push_back(const T &x) { b.push_back({x, M::op(getb<1>(), x)}); }
    void pop_front() {
        assert(size());
        if (f.empty()) rebalance();
        f.pop_back();
    }
    void pop_back() {
        assert(size());
        if (b.empty()) rebalance();
        b.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;

  private:
    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();
    }
    void rebalance() {
        bool ef = f.empty();
        int n = size(), i = 0, m = n / 2 + ef;
        vector<T> xs(n);
        for (; f.size(); f.pop_back()) xs[i++] = getf();
        for (; b.size(); b.pop_back()) xs[i++] = getb();
        if (ef) reverse(begin(xs), end(xs));
        for (i = m - 1; i >= 0; i--) push_front(xs[i]);
        for (i = m; i < n; i++) push_back(xs[i]);
    }
};

#line 2 "ds/deque_aggregation.hpp"

template<class M> struct DequeAggregation {
    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_front(const T &x) { f.push_back({x, M::op(x, getf<1>())}); }
    void push_back(const T &x) { b.push_back({x, M::op(getb<1>(), x)}); }
    void pop_front() {
        assert(size());
        if (f.empty()) rebalance();
        f.pop_back();
    }
    void pop_back() {
        assert(size());
        if (b.empty()) rebalance();
        b.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;

  private:
    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();
    }
    void rebalance() {
        bool ef = f.empty();
        int n = size(), i = 0, m = n / 2 + ef;
        vector<T> xs(n);
        for (; f.size(); f.pop_back()) xs[i++] = getf();
        for (; b.size(); b.pop_back()) xs[i++] = getb();
        if (ef) reverse(begin(xs), end(xs));
        for (i = m - 1; i >= 0; i--) push_front(xs[i]);
        for (i = m; i < n; i++) push_back(xs[i]);
    }
};

Back to top page