Foldable Deque(Slide Window Aggregation)
(structure/slide-window-aggregation.hpp)

• View this file on GitHub
• Last update: 2024-08-21 21:41:37+09:00
• Include: #include "structure/slide-window-aggregation.hpp"

単位元があって、結合的な演算(逆元は必要なし)(可換じゃなくてもいいよ(!!))について、両端キュー(Deque)っぽい操作と、Deque内の要素の総積が(ならしも入れて) $O(1)$ で計算できるデータ構造です。セグ木でいいかも。

名称についてはSlide Window Aggregation(SWAG)というのも結構覇権だけど、https://qiita.com/Shirotsume/items/4a2837b5895ef9a7aeb1 の記事がFoldable Dequeという名称を推していたのでそれを採用してる。

計算量解析について

あとはまかせた:

https://noshi91.hatenablog.com/entry/2019/10/10/230032

コンストラクタ

FoldableDeque<S, op, e>()

S: モノイド, op: 二項演算, e: 二項演算の単位元を返す関数。

push_back

dequeっぽく扱える。

計算量

• $O(1)$

push_front

dequeっぽく扱える。

計算量

• $O(1)$

pop_front

dequeっぽく扱える。

計算量

• $O(1)$ (ならし)

pop_back

dequeっぽく扱える。

計算量

• $O(1)$ (ならし)

all_prod

S all_prod()

Deque内にある要素の(先頭側から末尾側の順に計算した)総積を返す。

計算量

• $O(1)$ これがスゴイポイントであるけど、セグ木でいいじゃんかも。

Verified with

• test/verify/yosupo-deque-operate-all-composite.test.cpp
• test/verify/yosupo-queue-operate-all-composite.test.cpp

Code

#ifndef HARUILIB_LIBRARY_STRUCTURE_SLIDE_WINDOW_AGGREGATION_HPP
#define HARUILIB_LIBRARY_STRUCTURE_SLIDE_WINDOW_AGGREGATION_HPP

#include <vector>
#include <algorithm>

template <class S, S (*op)(S, S), S (*e)()>
struct FoldableDeque {
  struct Node {
    S val;
    S prod;
  };

  std::vector<Node> front, back;

  FoldableDeque() : front(), back() {}
  size_t size() const { return front.size() + back.size(); }
  bool empty() const { return front.size() + back.size() == 0; }


  // nyaanさんのをパクっており
  void rebalance() {
    int n = front.size() + back.size();
    int s0 = n / 2 + (front.empty() ? n % 2 : 0);
    // frontにs0個
    // backにN - s0個入れる
    vector<Node> a{front};
    std::reverse(begin(a), end(a));
    std::copy(begin(back), end(back), back_inserter(a));
    front.clear(), back.clear();
    for (int i = s0 - 1; i >= 0; i--) push_front(a[i].val);
    for (int i = s0; i < n; i++) push_back(a[i].val);
    return;
  }

  S all_prod() const {
    if (front.empty() && back.empty() ) return e();

    if (front.empty()) {
      return back.back().prod;
    }
    else if (back.empty()) {
      return front.back().prod;
    }

    else return op(front.back().prod, back.back().prod) ;
  }

  void push_back(const S& x) {
    if (back.empty()) {
      back.push_back({x, x});
    }
    else {
      // 順序怪しいかも
      back.push_back({x, op(back.back().prod, x) });
    }
  }

  void push_front(const S& x) {
    if (front.empty()) {
      front.push_back({x, x});
    }
    else {
      // 順序怪しいかも
      front.push_back({x, op(x, front.back().prod) });
    }  
  }

  void pop_back() {
    assert(size() > 0);
    if (back.empty()) rebalance();
    back.pop_back();
  }

  void pop_front() {
    assert(size() > 0);
    if (front.empty()) rebalance();
    front.pop_back();
  }
};
#endif // HARUILIB_LIBRARY_STRUCTURE_SLIDE_WINDOW_AGGREGATION_HPP

#line 1 "structure/slide-window-aggregation.hpp"



#include <vector>
#include <algorithm>

template <class S, S (*op)(S, S), S (*e)()>
struct FoldableDeque {
  struct Node {
    S val;
    S prod;
  };

  std::vector<Node> front, back;

  FoldableDeque() : front(), back() {}
  size_t size() const { return front.size() + back.size(); }
  bool empty() const { return front.size() + back.size() == 0; }


  // nyaanさんのをパクっており
  void rebalance() {
    int n = front.size() + back.size();
    int s0 = n / 2 + (front.empty() ? n % 2 : 0);
    // frontにs0個
    // backにN - s0個入れる
    vector<Node> a{front};
    std::reverse(begin(a), end(a));
    std::copy(begin(back), end(back), back_inserter(a));
    front.clear(), back.clear();
    for (int i = s0 - 1; i >= 0; i--) push_front(a[i].val);
    for (int i = s0; i < n; i++) push_back(a[i].val);
    return;
  }

  S all_prod() const {
    if (front.empty() && back.empty() ) return e();

    if (front.empty()) {
      return back.back().prod;
    }
    else if (back.empty()) {
      return front.back().prod;
    }

    else return op(front.back().prod, back.back().prod) ;
  }

  void push_back(const S& x) {
    if (back.empty()) {
      back.push_back({x, x});
    }
    else {
      // 順序怪しいかも
      back.push_back({x, op(back.back().prod, x) });
    }
  }

  void push_front(const S& x) {
    if (front.empty()) {
      front.push_back({x, x});
    }
    else {
      // 順序怪しいかも
      front.push_back({x, op(x, front.back().prod) });
    }  
  }

  void pop_back() {
    assert(size() > 0);
    if (back.empty()) rebalance();
    back.pop_back();
  }

  void pop_front() {
    assert(size() > 0);
    if (front.empty()) rebalance();
    front.pop_back();
  }
};

Back to top page