ds/static_range_product_group.hpp

• View this file on GitHub
• Last update: 2025-03-31 01:16:57+09:00
• Include: #include "ds/static_range_product_group.hpp"
• Link: View error logs on GitHub Actions

Depends on

• alg/monoid/add.hpp

Verified with

• test/1_mytest/wavelet_matrix.test.cpp
• test/2_library_checker/data_structure/rectangle_sum_wm.test.cpp
• test/2_library_checker/data_structure/rectangle_sum_wm_abel.test.cpp
• test/2_library_checker/data_structure/static_range_sum.test.cpp
• test/3_yukicoder/2065.test.cpp
• test/3_yukicoder/924.test.cpp

Code

#include "alg/monoid/add.hpp"

template <typename Monoid>
struct Static_Range_Product_Group {
  using MX = Monoid;
  using X = typename MX::value_type;
  int n;
  vc<X> dat;
  Static_Range_Product_Group() {}
  template <typename F>
  Static_Range_Product_Group(int m, F f) {
    build(m, f);
  }
  Static_Range_Product_Group(vc<X>& A) {
    build(len(A), [&](int i) -> X { return A[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m;
    dat.assign(n + 1, MX::unit());
    for (int i = 0; i < n; ++i) dat[i + 1] = MX::op(dat[i], f(i));
  }
  void build(vc<X>& A) {
    n = len(A);
    dat.assign(n + 1, MX::unit());
    for (int i = 0; i < n; ++i) dat[i + 1] = MX::op(dat[i], A[i]);
  }
  X prod(int l, int r) { return MX::op(MX::inverse(dat[l]), dat[r]); }
};

template <typename T>
using Prefix_Sum = Static_Range_Product_Group<Monoid_Add<T>>;

#line 2 "alg/monoid/add.hpp"

template <typename E>
struct Monoid_Add {
  using X = E;
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#line 2 "ds/static_range_product_group.hpp"

template <typename Monoid>
struct Static_Range_Product_Group {
  using MX = Monoid;
  using X = typename MX::value_type;
  int n;
  vc<X> dat;
  Static_Range_Product_Group() {}
  template <typename F>
  Static_Range_Product_Group(int m, F f) {
    build(m, f);
  }
  Static_Range_Product_Group(vc<X>& A) {
    build(len(A), [&](int i) -> X { return A[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m;
    dat.assign(n + 1, MX::unit());
    for (int i = 0; i < n; ++i) dat[i + 1] = MX::op(dat[i], f(i));
  }
  void build(vc<X>& A) {
    n = len(A);
    dat.assign(n + 1, MX::unit());
    for (int i = 0; i < n; ++i) dat[i + 1] = MX::op(dat[i], A[i]);
  }
  X prod(int l, int r) { return MX::op(MX::inverse(dat[l]), dat[r]); }
};

template <typename T>
using Prefix_Sum = Static_Range_Product_Group<Monoid_Add<T>>;

Back to top page