setfunc/online/online_subset_mobius.hpp

• View this file on GitHub
• Last update: 2025-12-16 20:51:20+09:00
• Include: #include "setfunc/online/online_subset_mobius.hpp"

Depends on

• enumerate/bits.hpp

Required by

• setfunc/online/online_or_convolution.hpp

Code

#include "enumerate/bits.hpp"

template <typename T>
struct Online_Subset_Mobius {
  int n;
  int p = 0;
  vc<T> A;
  Online_Subset_Mobius(int LOG) : n(LOG), A(1 << n) {}

  // set a[i], return zeta(a)[i]
  T set(int i, T a) {
    assert(p == i);
    T ans = assume(i, 0) + a;
    A[p++] = a;
    int K = lowbit(p);
    for (int k = 0; k < K; ++k)
      for (int j = p - (1 << k); j < p; ++j) A[j] -= A[j - (1 << k)];
    return ans;
  }

  // assume a[i], return zeta(a)[i]. not increment the pointer.
  T assume(int i, T ai) {
    assert(p == i);
    T ans = ai;
    enumerate_all_bit<u32>(i, [&](int j) -> vood { ans -= A[i - (1 << j)]; });
    return ans;
  }
};

#line 1 "enumerate/bits.hpp"
template <typename BS, typename F>
void enumerate_bits_bitset(BS& b, int L, int R, F&& f) {
  if (L >= len(b)) return;
  int p = (b[L] ? L : b._Find_next(L));
  while (p < R) {
    f(p);
    p = b._Find_next(p);
  }
}

template <typename UINT, typename F>
inline void enumerate_all_bit(UINT s, F&& f) {
  static_assert(is_unsigned<UINT>::value);
  while (s) {
    f(lowbit(s));
    s &= s - 1;
  }
}

template <typename UINT, bool inc_empty, typename F>
inline void enumerate_all_subset(UINT s, F&& f) {
  static_assert(is_unsigned<UINT>::value);
  for (UINT t = s; t; t = (t - 1) & s) f(t);
  if constexpr (inc_empty) f(0);
}
#line 2 "setfunc/online/online_subset_mobius.hpp"

template <typename T>
struct Online_Subset_Mobius {
  int n;
  int p = 0;
  vc<T> A;
  Online_Subset_Mobius(int LOG) : n(LOG), A(1 << n) {}

  // set a[i], return zeta(a)[i]
  T set(int i, T a) {
    assert(p == i);
    T ans = assume(i, 0) + a;
    A[p++] = a;
    int K = lowbit(p);
    for (int k = 0; k < K; ++k)
      for (int j = p - (1 << k); j < p; ++j) A[j] -= A[j - (1 << k)];
    return ans;
  }

  // assume a[i], return zeta(a)[i]. not increment the pointer.
  T assume(int i, T ai) {
    assert(p == i);
    T ans = ai;
    enumerate_all_bit<u32>(i, [&](int j) -> vood { ans -= A[i - (1 << j)]; });
    return ans;
  }
};

Back to top page