ds/fenwicktree/fenwicktree_range_add.hpp

• View this file on GitHub
• Last update: 2026-08-19 06:34:57+09:00
• Include: #include "ds/fenwicktree/fenwicktree_range_add.hpp"
• Link: https://codeforces.com/contest/860/submission/228355081
• Link: https://maspypy.github.io/library/test/mytest/fenwick_raq.test.cpp

Depends on

• alg/monoid/add.hpp
• ds/fenwicktree/fenwicktree.hpp
• other/bit.hpp

Verified with

• test/1_mytest/fenwick_raq.test.cpp

Code

#include "ds/fenwicktree/fenwicktree.hpp"

// 遅延セグ木より 4 ～ 5 倍高速？
// https://maspypy.github.io/library/test/mytest/fenwick_raq.test.cpp
// https://codeforces.com/contest/860/submission/228355081
template <typename AbelianGroup>
struct FenwickTree_Range_Add {
  using G = AbelianGroup;
  using E = typename AbelianGroup::value_type;
  int n;
  FenwickTree<G> bit0;
  FenwickTree<G> bit1;

  FenwickTree_Range_Add() {}
  FenwickTree_Range_Add(int n) { build(n); }
  template <typename F>
  FenwickTree_Range_Add(int n, F f) {
    build(n, f);
  }
  FenwickTree_Range_Add(const vc<E>& v) { build(v); }

  void build(int m) {
    n = m;
    bit0.build(n), bit1.build(n);
  }
  void build(const vc<E>& v) {
    build(len(v), [&](int i) -> E { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m;
    bit0.build(m, f);
    bit1.build(m);
  }

  void add_at(int i, E val) { bit0.add(i, val); }

  void add(int L, int R, E val) {
    bit0.add(L, G::power(val, -L));
    bit0.add(R, G::power(val, R));
    bit1.add(L, val);
    bit1.add(R, G::inverse(val));
  }

  E prod(int L, int R) {
    E prod_R = G::op(G::power(bit1.prod(R), R), bit0.prod(R));
    E prod_L = G::op(G::power(bit1.prod(L), L), bit0.prod(L));
    return G::op(G::inverse(prod_L), prod_R);
  }
};

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

#line 1 "other/bit.hpp"

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(unsigned(x)) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T>
T kth_bit(int k) {
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  return x >> k & 1;
}

template <typename UINT>
struct all_bit {
  UINT s;
  all_bit(UINT s) : s(s) {}
  struct iter {
    UINT s;
    int operator*() const { return lowbit(s); }
    void operator++() { s &= s - 1; }
    bool operator!=(nullptr_t) const { return s; }
  };
  iter begin() const { return {s}; }
  nullptr_t end() const { return nullptr; }
};

template <typename UINT>
struct all_subset {
  UINT s;
  all_subset(UINT s) : s(s) {}
  struct iter {
    UINT s, t;
    bool done = false;
    UINT operator*() const { return t; }
    void operator++() {
      done = (t == 0);
      t = (t - 1) & s;
    }
    bool operator!=(nullptr_t) const { return !done; }
  };
  iter begin() const { return {s, s}; }
  nullptr_t end() const { return nullptr; }
};

constexpr u64 full_mask(int n) { return n == 64 ? -1ULL : (1ULL << n) - 1; }

u64 bit_reverse(u64 x) {
  x = ((x & 0x5555555555555555ULL) << 1) | ((x >> 1) & 0x5555555555555555ULL);
  x = ((x & 0x3333333333333333ULL) << 2) | ((x >> 2) & 0x3333333333333333ULL);
  x = ((x & 0x0f0f0f0f0f0f0f0fULL) << 4) | ((x >> 4) & 0x0f0f0f0f0f0f0f0fULL);
  x = ((x & 0x00ff00ff00ff00ffULL) << 8) | ((x >> 8) & 0x00ff00ff00ff00ffULL);
  x = ((x & 0x0000ffff0000ffffULL) << 16) | ((x >> 16) & 0x0000ffff0000ffffULL);
  x = (x << 32) | (x >> 32);
  return x;
}
#line 1 "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/fenwicktree.hpp"

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

  FenwickTree() {}
  FenwickTree(int n) { build(n); }
  template <typename F>
  FenwickTree(int n, F f) {
    build(n, f);
  }
  FenwickTree(const vc<E>& v) { build(v); }

  void build(int m) {
    n = m;
    dat.assign(m, G::unit());
    total = G::unit();
  }
  void build(const vc<E>& v) {
    build(len(v), [&](int i) -> E { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m;
    dat.clear();
    dat.reserve(n);
    total = G::unit();
    FOR(i, n) { dat.eb(f(i)); }
    for (int i = 1; i <= n; ++i) {
      int j = i + (i & -i);
      if (j <= n) dat[j - 1] = G::op(dat[i - 1], dat[j - 1]);
    }
    total = prefix_sum(m);
  }

  E prod_all() const { return total; }
  E sum_all() const { return total; }
  E sum(int k) const { return prefix_sum(k); }
  E prod(int k) const { return prefix_prod(k); }
  E prefix_sum(int k) const { return prefix_prod(k); }
  E prefix_prod(int k) const {
    chmin(k, n);
    E ret = G::unit();
    for (; k > 0; k -= k & -k) ret = G::op(ret, dat[k - 1]);
    return ret;
  }
  E sum(int L, int R) const { return prod(L, R); }
  E prod(int L, int R) const {
    chmax(L, 0), chmin(R, n);
    if (L == 0) return prefix_prod(R);
    assert(0 <= L && L <= R && R <= n);
    E pos = G::unit(), neg = G::unit();
    while (L < R) {
      pos = G::op(pos, dat[R - 1]), R -= R & -R;
    }
    while (R < L) {
      neg = G::op(neg, dat[L - 1]), L -= L & -L;
    }
    return G::op(pos, G::inverse(neg));
  }

  vc<E> get_all() const {
    vc<E> res(n);
    FOR(i, n) res[i] = prod(i, i + 1);
    return res;
  }

  void add(int k, E x) { multiply(k, x); }
  void multiply(int k, E x) {
    static_assert(G::commute);
    total = G::op(total, x);
    for (++k; k <= n; k += k & -k) dat[k - 1] = G::op(dat[k - 1], x);
  }
  void set(int k, E x) { add(k, G::op(G::inverse(prod(k, k + 1)), x)); }

  template <class F>
  int max_right(const F check, int L = 0) const {
    assert(check(G::unit()));
    E s = G::unit();
    int i = L;
    // 2^k 進むとダメ
    int k = [&]() {
      while (1) {
        if (i % 2 == 1) {
          s = G::op(s, G::inverse(dat[i - 1])), i -= 1;
        }
        if (i == 0) {
          return topbit(n) + 1;
        }
        int k = lowbit(i) - 1;
        if (i + (1 << k) > n) return k;
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (!check(t)) {
          return k;
        }
        s = G::op(s, G::inverse(dat[i - 1])), i -= i & -i;
      }
    }();
    while (k) {
      --k;
      if (i + (1 << k) - 1 < len(dat)) {
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (i + (1 << k) <= L || check(t)) {
          i += (1 << k), s = t;
        }
      }
    }
    return i;
  }

  // check(i, x)
  template <class F>
  int max_right_with_index(const F check, int L = 0) const {
    assert(check(L, G::unit()));
    E s = G::unit();
    int i = L;
    // 2^k 進むとダメ
    int k = [&]() {
      while (1) {
        if (i % 2 == 1) {
          s = G::op(s, G::inverse(dat[i - 1])), i -= 1;
        }
        if (i == 0) {
          return topbit(n) + 1;
        }
        int k = lowbit(i) - 1;
        if (i + (1 << k) > n) return k;
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (!check(i + (1 << k), t)) {
          return k;
        }
        s = G::op(s, G::inverse(dat[i - 1])), i -= i & -i;
      }
    }();
    while (k) {
      --k;
      if (i + (1 << k) - 1 < len(dat)) {
        E t = G::op(s, dat[i + (1 << k) - 1]);
        if (i + (1 << k) <= L || check(i + (1 << k), t)) {
          i += (1 << k), s = t;
        }
      }
    }
    return i;
  }

  template <class F>
  int min_left(const F check, int R) const {
    assert(check(G::unit()));
    E s = G::unit();
    int i = R;
    // false になるところまで戻る
    int k = 0;
    while (i > 0 && check(s)) {
      s = G::op(s, dat[i - 1]);
      k = lowbit(i);
      i -= i & -i;
    }
    if (check(s)) {
      assert(i == 0);
      return 0;
    }
    // 2^k 進むと ok になる
    // false を維持して進む
    while (k) {
      --k;
      E t = G::op(s, G::inverse(dat[i + (1 << k) - 1]));
      if (!check(t)) {
        i += (1 << k), s = t;
      }
    }
    return i + 1;
  }

  int kth(E k, int L = 0) const {
    return max_right([&k](E x) -> bool { return x <= k; }, L);
  }
};
#line 3 "ds/fenwicktree/fenwicktree_range_add.hpp"

// 遅延セグ木より 4 ～ 5 倍高速？
// https://maspypy.github.io/library/test/mytest/fenwick_raq.test.cpp
// https://codeforces.com/contest/860/submission/228355081
template <typename AbelianGroup>
struct FenwickTree_Range_Add {
  using G = AbelianGroup;
  using E = typename AbelianGroup::value_type;
  int n;
  FenwickTree<G> bit0;
  FenwickTree<G> bit1;

  FenwickTree_Range_Add() {}
  FenwickTree_Range_Add(int n) { build(n); }
  template <typename F>
  FenwickTree_Range_Add(int n, F f) {
    build(n, f);
  }
  FenwickTree_Range_Add(const vc<E>& v) { build(v); }

  void build(int m) {
    n = m;
    bit0.build(n), bit1.build(n);
  }
  void build(const vc<E>& v) {
    build(len(v), [&](int i) -> E { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m;
    bit0.build(m, f);
    bit1.build(m);
  }

  void add_at(int i, E val) { bit0.add(i, val); }

  void add(int L, int R, E val) {
    bit0.add(L, G::power(val, -L));
    bit0.add(R, G::power(val, R));
    bit1.add(L, val);
    bit1.add(R, G::inverse(val));
  }

  E prod(int L, int R) {
    E prod_R = G::op(G::power(bit1.prod(R), R), bit0.prod(R));
    E prod_L = G::op(G::power(bit1.prod(L), L), bit0.prod(L));
    return G::op(G::inverse(prod_L), prod_R);
  }
};

Back to top page