setfunc/submask_range_query.hpp

• View this file on GitHub
• Last update: 2025-09-16 11:00:58+09:00
• Include: #include "setfunc/submask_range_query.hpp"

Depends on

• alg/monoid/add.hpp
• alg/monoid/xor.hpp
• random/base.hpp
• random/shuffle.hpp

Code

#include "random/shuffle.hpp"
#include "alg/monoid/add.hpp"
#include "alg/monoid/xor.hpp"

// O((4/3)^LOG) per query
template <typename Monoid>
struct SubMask_Range_Query {
  using MX = Monoid;
  using X = typename MX::value_type;
  const int LOG;
  vc<X> S;
  array<u32, 3> mask;
  /*
  0: [x0,x1] -> [x0,x1] -> [x0,x0+x1]
  1: [x0,x1] -> [x0+x1,x0] -> [x0,x0+x1]
  2: [x0,x1] -> [x0+x1,x1] -> [x0,x0+x1]
  */

  SubMask_Range_Query(int LOG) : LOG(LOG), mask{} {
    S.assign(1 << LOG, MX::unit());
    init_by_random();
  }

  void init_by_random() {
    FOR(i, LOG) { mask[RNG(0, 3)] |= 1 << i; }
  }

  void init_by_query(vc<u32>& ADD, vc<u32>& GET) {
    mask[0] = mask[1] = mask[2] = 0;
    auto eval = [&]() -> ll {
      ll ans = 0;
      for (u32 x : ADD) {
        u32 s = 0;
        s ^= (~x) & mask[1];
        s ^= x & mask[2];
        ans += 1 << popcnt(s);
      }
      for (auto& x : GET) {
        u32 s = 0;
        s ^= x & mask[0];
        s ^= (~x) & mask[2];
        ans += 1 << popcnt(s);
      }
      return ans;
    };
    vc<int> I(LOG);
    FOR(i, LOG) I[i] = i;
    shuffle(I);
    array<ll, 3> c;
    for (int i : I) {
      FOR(k, 3) { mask[k] |= 1 << i, c[k] = eval(), mask[k] &= ~(1 << i); }
      int k = min_element(all(c)) - c.begin();
      mask[k] |= 1 << i;
    }
  }

  void add(u32 i, X x) {
    u32 base = i & mask[0];
    u32 s = ((~i) & mask[1]) | (i & mask[2]);
    for (u32 t : all_subset<u32>(s)) {
      S[base | t] = MX::op(S[base | t], x);
    }
  }

  X get_sum(u32 i) {
    u32 base = (~i) & mask[1];
    u32 s = (i & mask[0]) | ((~i) & mask[2]);
    if constexpr (is_same_v<Monoid_Add<X>, MX>) {
      X ANS = 0;
      for (u32 t : all_subset<u32>(s)) {
        ANS += S[base | t] * popcnt_sgn(t & mask[2]);
      }
      return ANS;
    } else if constexpr (is_same_v<Monoid_Xor<X>, MX>) {
      X ANS = 0;
      for (u32 t : all_subset<u32>(s)) {
        ANS ^= S[base | t];
      }
      return ANS;
    } else {
      X a[] = {MX::unit(), MX::unit()};
      for (u32 t : all_subset<u32>(s)) {
        int k = __builtin_parity(t & mask[2]);
        a[k] = MX::op(a[k], S[base | t]);
      }
      return MX::op(a[0], MX::inverse(a[1]));
    }
  }
};

#line 2 "random/base.hpp"

u64 RNG_64() {
  static u64 x_ = u64(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()) * 10150724397891781847ULL;
  x_ ^= x_ << 7;
  return x_ ^= x_ >> 9;
}

u64 RNG(u64 lim) { return RNG_64() % lim; }

ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); }
#line 2 "random/shuffle.hpp"

template <typename T>
void shuffle(vc<T>& A) {
  FOR(i, len(A)) {
    int j = RNG(0, i + 1);
    if (i != j) swap(A[i], A[j]);
  }
}
#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 "alg/monoid/xor.hpp"

template <typename X>
struct Monoid_Xor {
  using value_type = X;
  static X op(X x, X y) { return x ^ y; }
  static constexpr X inverse(const X &x) noexcept { return x; }
  static constexpr X power(const X &x, ll n) noexcept {
    return (n & 1 ? x : 0);
  }
  static constexpr X unit(){return X(0);};
  static constexpr bool commute = true;
};
#line 4 "setfunc/submask_range_query.hpp"

// O((4/3)^LOG) per query
template <typename Monoid>
struct SubMask_Range_Query {
  using MX = Monoid;
  using X = typename MX::value_type;
  const int LOG;
  vc<X> S;
  array<u32, 3> mask;
  /*
  0: [x0,x1] -> [x0,x1] -> [x0,x0+x1]
  1: [x0,x1] -> [x0+x1,x0] -> [x0,x0+x1]
  2: [x0,x1] -> [x0+x1,x1] -> [x0,x0+x1]
  */

  SubMask_Range_Query(int LOG) : LOG(LOG), mask{} {
    S.assign(1 << LOG, MX::unit());
    init_by_random();
  }

  void init_by_random() {
    FOR(i, LOG) { mask[RNG(0, 3)] |= 1 << i; }
  }

  void init_by_query(vc<u32>& ADD, vc<u32>& GET) {
    mask[0] = mask[1] = mask[2] = 0;
    auto eval = [&]() -> ll {
      ll ans = 0;
      for (u32 x : ADD) {
        u32 s = 0;
        s ^= (~x) & mask[1];
        s ^= x & mask[2];
        ans += 1 << popcnt(s);
      }
      for (auto& x : GET) {
        u32 s = 0;
        s ^= x & mask[0];
        s ^= (~x) & mask[2];
        ans += 1 << popcnt(s);
      }
      return ans;
    };
    vc<int> I(LOG);
    FOR(i, LOG) I[i] = i;
    shuffle(I);
    array<ll, 3> c;
    for (int i : I) {
      FOR(k, 3) { mask[k] |= 1 << i, c[k] = eval(), mask[k] &= ~(1 << i); }
      int k = min_element(all(c)) - c.begin();
      mask[k] |= 1 << i;
    }
  }

  void add(u32 i, X x) {
    u32 base = i & mask[0];
    u32 s = ((~i) & mask[1]) | (i & mask[2]);
    for (u32 t : all_subset<u32>(s)) {
      S[base | t] = MX::op(S[base | t], x);
    }
  }

  X get_sum(u32 i) {
    u32 base = (~i) & mask[1];
    u32 s = (i & mask[0]) | ((~i) & mask[2]);
    if constexpr (is_same_v<Monoid_Add<X>, MX>) {
      X ANS = 0;
      for (u32 t : all_subset<u32>(s)) {
        ANS += S[base | t] * popcnt_sgn(t & mask[2]);
      }
      return ANS;
    } else if constexpr (is_same_v<Monoid_Xor<X>, MX>) {
      X ANS = 0;
      for (u32 t : all_subset<u32>(s)) {
        ANS ^= S[base | t];
      }
      return ANS;
    } else {
      X a[] = {MX::unit(), MX::unit()};
      for (u32 t : all_subset<u32>(s)) {
        int k = __builtin_parity(t & mask[2]);
        a[k] = MX::op(a[k], S[base | t]);
      }
      return MX::op(a[0], MX::inverse(a[1]));
    }
  }
};

Back to top page