Slide Window Aggrigation
(data-structure/slide-window-aggregation.hpp)

• View this file on GitHub
• Last update: 2023-09-02 22:21:41+09:00
• Include: #include "data-structure/slide-window-aggregation.hpp"

Slide Window Aggrigation

概要

Slide Window Aggrigation は、モノイド$(S,\bullet,I)$の$S$の要素の列$A$に対して、以下の操作を高速に実行できる構造である。

• 末尾への要素の挿入
• 先頭の要素の削除
• $A$全体の集約値$A_0 \bullet A_1 \bullet A_2 \bullet \cdots \bullet A_{\vert A \vert -1}$の取得

構造は、挿入用と削除用の$2$つのスタックを持ち、削除用のスタックの中身が尽きたときに挿入用からすべての要素を移し替える。

使い方

• テンプレート引数 typename T: $S$の要素の型。
• テンプレート引数 typename F: 演算$\bullet$を定義するオブジェクトの型。オブジェクトはT f(const T& a,const T& b);の形の関数として呼び出せて、$a \bullet b$の値を返す。
• SlideWindowAggregation<F, T>(f_, I_): f_を演算、I_を単位元として設定し、$A$を空の列で初期化する。
• push(x): 要素xを$A$の末尾に挿入する。計算量均し$\mathrm{O}(1)$。
• pop(): $A$から先頭の要素を削除する。計算量均し$\mathrm{O}(1)$。
• query(): 集約値$A_0 \bullet A_1 \bullet A_2 \bullet \cdots \bullet A_ {\vert A \vert -1}$を返す。計算量$\mathrm{O}(1)$。

注意点

• $A$が空のときにpopを呼んではならない。
• 上記の計算量ではf_の計算量を$\mathrm{O}(1)$と仮定している。

Verified with

• verify/verify-yosupo-ds/yosupo-swag.test.cpp

Code

#pragma once

#include <vector>
using namespace std;

template <typename T, typename F>
struct SlideWindowAggregation {
  vector<T> a0, a1, r0, r1;
  F f;
  T I, f0, f1;

  SlideWindowAggregation(F _f, T _i) : f(_f), I(_i), f0(_i), f1(_i) {}

 private:
  void push_s0(const T &x) {
    a0.push_back(x);
    r0.push_back(f0 = f(x, f0));
  }
  void push_s1(const T &x) {
    a1.push_back(x);
    r1.push_back(f1 = f(f1, x));
  }
  void transfer() {
    while (!a1.empty()) {
      push_s0(a1.back());
      a1.pop_back();
    }
    while (!r1.empty()) r1.pop_back();
    f1 = I;
  }

 public:
  void push(const T &x) {
    if (a0.empty()) {
      push_s0(x);
      transfer();
    } else {
      push_s1(x);
    }
  }
  void pop() {
    if (a0.empty()) transfer();
    a0.pop_back();
    r0.pop_back();
    f0 = r0.empty() ? I : r0.back();
  }
  T query() { return f(f0, f1); }
};

/**
 * @brief Slide Window Aggrigation
 * @docs docs/data-structure/slide-window-aggregation.md
 */

#line 2 "data-structure/slide-window-aggregation.hpp"

#include <vector>
using namespace std;

template <typename T, typename F>
struct SlideWindowAggregation {
  vector<T> a0, a1, r0, r1;
  F f;
  T I, f0, f1;

  SlideWindowAggregation(F _f, T _i) : f(_f), I(_i), f0(_i), f1(_i) {}

 private:
  void push_s0(const T &x) {
    a0.push_back(x);
    r0.push_back(f0 = f(x, f0));
  }
  void push_s1(const T &x) {
    a1.push_back(x);
    r1.push_back(f1 = f(f1, x));
  }
  void transfer() {
    while (!a1.empty()) {
      push_s0(a1.back());
      a1.pop_back();
    }
    while (!r1.empty()) r1.pop_back();
    f1 = I;
  }

 public:
  void push(const T &x) {
    if (a0.empty()) {
      push_s0(x);
      transfer();
    } else {
      push_s1(x);
    }
  }
  void pop() {
    if (a0.empty()) transfer();
    a0.pop_back();
    r0.pop_back();
    f0 = r0.empty() ? I : r0.back();
  }
  T query() { return f(f0, f1); }
};

/**
 * @brief Slide Window Aggrigation
 * @docs docs/data-structure/slide-window-aggregation.md
 */

Back to top page