ds/sparse_table/disjoint_sparse_table.hpp

• View this file on GitHub
• Last update: 2026-08-30 21:09:36+09:00
• Include: #include "ds/sparse_table/disjoint_sparse_table.hpp"

Depends on

• other/bit.hpp

Required by

• ds/static_range_product.hpp
• graph/ds/static_tree_monoid.hpp
• string/basic_substring_structure.hpp
• string/lex_max_suffix_for_all_prefix.hpp
• string/longest_common_substring.hpp
• string/many_string_compare.hpp
• string/sort_substrings.hpp
• string/substring_shortest_border.hpp
• string/suffix_array.hpp
• string/suffix_lcp_change.hpp
• string/suffix_tree.hpp

Verified with

• test/1_mytest/lex_minmax_suffix.test.cpp
• test/1_mytest/longest_common_substr.test.cpp
• test/1_mytest/suffix_lcp_change.test.cpp
• test/2_library_checker/data_structure/staticrmq.test.cpp
• test/2_library_checker/data_structure/staticrmq_dst.test.cpp
• test/2_library_checker/string/longest_common_substring.test.cpp
• test/2_library_checker/string/number_of_substrings.test.cpp
• test/2_library_checker/string/suffix_array.test.cpp
• test/2_library_checker/string/suffix_array_vec.test.cpp
• test/2_library_checker/string/zalgorithm_by_rollinghash2.test.cpp
• test/3_yukicoder/1216.test.cpp
• test/3_yukicoder/1216_2.test.cpp
• test/3_yukicoder/1600_2.test.cpp
• test/3_yukicoder/2005.test.cpp
• test/3_yukicoder/2361.test.cpp

Code

#include "other/bit.hpp"

template <class Monoid>
struct Disjoint_Sparse_Table {
  using MX = Monoid;
  using X = typename MX::value_type;
  int n, log;
  vvc<X> dat;

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

  void build(int m) {
    build(m, [](int i) -> X { return MX::id(); });
  }
  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m, log = 1;
    while ((1 << log) < n) ++log;
    dat.resize(log);
    dat[0].reserve(n);
    FOR(i, n) dat[0].eb(f(i));
    FOR(i, 1, log) {
      auto& v = dat[i];
      v = dat[0];
      int b = 1 << i;
      for (int m = b; m <= n; m += 2 * b) {
        int L = m - b, R = min(n, m + b);
        FOR_R(j, L + 1, m) v[j - 1] = MX::op(v[j - 1], v[j]);
        FOR(j, m, R - 1) v[j + 1] = MX::op(v[j], v[j + 1]);
      }
    }
  }

  X prod(int L, int R) const {
    if (L == R) return MX::id();
    --R;
    if (L == R) return dat[0][L];
    int k = topbit(L ^ R);
    return MX::op(dat[k][L], dat[k][R]);
  }

  template <class F>
  int max_right(const F check, int L) const {
    assert(0 <= L && L <= n && check(MX::id()));
    if (L == n) return n;
    int ok = L, ng = n + 1;
    while (ok + 1 < ng) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(L, k));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }

  template <class F>
  int min_left(const F check, int R) const {
    assert(0 <= R && R <= n && check(MX::id()));
    if (R == 0) return 0;
    int ok = R, ng = -1;
    while (ng + 1 < ok) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(k, R));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }
};

#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) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return x >> k & 1;
}

template <typename UINT>
struct all_bit {
  static_assert(is_unsigned<UINT>::value);
  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 {
  static_assert(is_unsigned<UINT>::value);
  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) {
  assert(0 <= n && n <= 64);
  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 2 "ds/sparse_table/disjoint_sparse_table.hpp"

template <class Monoid>
struct Disjoint_Sparse_Table {
  using MX = Monoid;
  using X = typename MX::value_type;
  int n, log;
  vvc<X> dat;

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

  void build(int m) {
    build(m, [](int i) -> X { return MX::id(); });
  }
  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m, log = 1;
    while ((1 << log) < n) ++log;
    dat.resize(log);
    dat[0].reserve(n);
    FOR(i, n) dat[0].eb(f(i));
    FOR(i, 1, log) {
      auto& v = dat[i];
      v = dat[0];
      int b = 1 << i;
      for (int m = b; m <= n; m += 2 * b) {
        int L = m - b, R = min(n, m + b);
        FOR_R(j, L + 1, m) v[j - 1] = MX::op(v[j - 1], v[j]);
        FOR(j, m, R - 1) v[j + 1] = MX::op(v[j], v[j + 1]);
      }
    }
  }

  X prod(int L, int R) const {
    if (L == R) return MX::id();
    --R;
    if (L == R) return dat[0][L];
    int k = topbit(L ^ R);
    return MX::op(dat[k][L], dat[k][R]);
  }

  template <class F>
  int max_right(const F check, int L) const {
    assert(0 <= L && L <= n && check(MX::id()));
    if (L == n) return n;
    int ok = L, ng = n + 1;
    while (ok + 1 < ng) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(L, k));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }

  template <class F>
  int min_left(const F check, int R) const {
    assert(0 <= R && R <= n && check(MX::id()));
    if (R == 0) return 0;
    int ok = R, ng = -1;
    while (ng + 1 < ok) {
      int k = (ok + ng) / 2;
      bool bl = check(prod(k, R));
      if (bl) ok = k;
      if (!bl) ng = k;
    }
    return ok;
  }
};

Back to top page