ds/fenwicktree/dual_fenwicktree.hpp

• View this file on GitHub
• Last update: 2024-01-23 05:58:02+09:00
• Include: #include "ds/fenwicktree/dual_fenwicktree.hpp"

Depends on

• alg/monoid/add.hpp

Verified with

• test/mytest/dual_fenwick.test.cpp

Code

#include "alg/monoid/add.hpp"

template <typename Monoid>
struct Dual_FenwickTree {
  using G = Monoid;
  using E = typename G::value_type;
  int n;
  vector<E> dat;

  Dual_FenwickTree() {}
  Dual_FenwickTree(int n) { build(n); }

  void build(int m) {
    n = m;
    dat.assign(m, G::unit());
  }

  E get(int k) {
    E x = G::unit();
    for (++k; k <= n; k += k & -k) x = G::op(x, dat[k - 1]);
    return x;
  }
  vc<E> get_all() {
    vc<E> A = dat;
    FOR_R(i, 1, len(A) + 1) {
      int j = i + (i & -i);
      if (j <= len(A)) A[i - 1] += A[j - 1];
    }
    return A;
  }

  void apply(int L, int R, E x) {
    assert(0 <= L && L <= R && R <= n);
    E neg_x = G::inverse(x);
    while (L < R) { dat[R - 1] = G::op(x, dat[R - 1]), R -= R & -R; };
    while (R < L) { dat[L - 1] = G::op(neg_x, dat[L - 1]), L -= L & -L; };
  }
};

#line 1 "ds/fenwicktree/dual_fenwicktree.hpp"

#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 3 "ds/fenwicktree/dual_fenwicktree.hpp"

template <typename Monoid>
struct Dual_FenwickTree {
  using G = Monoid;
  using E = typename G::value_type;
  int n;
  vector<E> dat;

  Dual_FenwickTree() {}
  Dual_FenwickTree(int n) { build(n); }

  void build(int m) {
    n = m;
    dat.assign(m, G::unit());
  }

  E get(int k) {
    E x = G::unit();
    for (++k; k <= n; k += k & -k) x = G::op(x, dat[k - 1]);
    return x;
  }
  vc<E> get_all() {
    vc<E> A = dat;
    FOR_R(i, 1, len(A) + 1) {
      int j = i + (i & -i);
      if (j <= len(A)) A[i - 1] += A[j - 1];
    }
    return A;
  }

  void apply(int L, int R, E x) {
    assert(0 <= L && L <= R && R <= n);
    E neg_x = G::inverse(x);
    while (L < R) { dat[R - 1] = G::op(x, dat[R - 1]), R -= R & -R; };
    while (R < L) { dat[L - 1] = G::op(neg_x, dat[L - 1]), L -= L & -L; };
  }
};

Back to top page