string/rolling-hash-segment-tree.hpp

View this file on GitHub
Last update: 2026-07-25 02:01:37+09:00
Include: #include "string/rolling-hash-segment-tree.hpp"

Depends on

Verified with

verify/string/UNIT_rolling_hash.test.cpp

Code

#pragma once

#include "segment-tree/segment-tree.hpp"
#include "string/rolling-hash-monoid.hpp"

template <class Value = char>
struct RollingHashSegmentTree : SegmentTree<RollingHashMonoid> {
  using M = RollingHashMonoid;
  using SegTree = SegmentTree<M>;
  RollingHashSegmentTree() : SegTree() {}
  explicit RollingHashSegmentTree(const vector<Value>& a) : SegTree(M::init(a)) {}
  explicit RollingHashSegmentTree(const string& s) : SegTree(M::init(s)) {}
  void set(int p, Value v) { SegTree::set(p, M::single(v)); }
  Value get(int p) { return RollingHashBase::restore<Value>(SegTree::get(p).hash); }
  RollingHashValue prod(int l, int r) { return SegTree::prod(l, r); }
};

template <class Value = char>
struct RollingHashSegmentTreeReversible : SegmentTree<RollingHashMonoidReversible> {
  using M = RollingHashMonoidReversible;
  using SegTree = SegmentTree<M>;
  RollingHashSegmentTreeReversible() : SegTree() {}
  explicit RollingHashSegmentTreeReversible(const vector<Value>& a) : SegTree(M::init(a)) {}
  explicit RollingHashSegmentTreeReversible(const string& s) : SegTree(M::init(s)) {}
  void set(int p, Value v) { SegTree::set(p, M::single(v)); }
  Value get(int p) { return RollingHashBase::restore<Value>(SegTree::get(p).hash); }
  RollingHashValueReversible prod(int l, int r) { return SegTree::prod(l, r); }
};

#line 2 "string/rolling-hash-segment-tree.hpp"

#line 2 "algebraic-structure/util.hpp"
#ifdef __cpp_concepts
#define REQUIRES(...) requires __VA_ARGS__
#else
#define REQUIRES(...)
#endif
#line 3 "algebraic-structure/magma.hpp"

#ifdef __cpp_concepts
template <class M>
concept Magma = requires(typename M::value_type x, typename M::value_type y) {
  typename M::value_type;
  { M::op(x, y) } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMagma {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
};
template <class T>
struct MulMagma {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
};
template <class T, T id>
struct MaxMagma {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
};
template <class T, T id>
struct MinMagma {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
};
#line 3 "algebraic-structure/monoid.hpp"

#ifdef __cpp_concepts
template <class M>
concept Monoid = Magma<M> && requires {
  { M::e() } -> same_as<typename M::value_type>;
};
#endif

template <class T>
struct AddMonoid {
  using value_type = T;
  static T op(T x, T y) { return x + y; }
  static T e() { return T(0); }
};
template <class T>
struct MulMonoid {
  using value_type = T;
  static T op(T x, T y) { return x * y; }
  static T e() { return T(1); }
};
template <class T, T id>
struct MaxMonoid {
  using value_type = T;
  static T op(T x, T y) { return x > y ? x : y; }
  static T e() { return id; }
};
template <class T, T id>
struct MinMonoid {
  using value_type = T;
  static T op(T x, T y) { return x < y ? x : y; }
  static T e() { return id; }
};
#line 3 "segment-tree/segment-tree.hpp"

template <class M>
REQUIRES(Monoid<M>)
struct SegmentTree {
  using T = typename M::value_type;

 private:
  int _n, size, log;
  vector<T> d;
  void update(int p) { d[p] = M::op(d[2 * p], d[2 * p + 1]); }

 public:
  SegmentTree() : SegmentTree(0) {}
  explicit SegmentTree(int sz) : SegmentTree(vector<T>(sz, M::e())) {}
  explicit SegmentTree(const vector<T>& v) : _n(v.size()) {
    size = 1, log = 0;
    while (size < _n) size <<= 1, log++;
    d.assign(2 * size, M::e());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i > 0; i--) update(i);
  }
  void clear() { fill(d.begin(), d.end(), M::e()); }

  void set_without_update(int p, T v) { d[p + size] = v; }
  void all_update() {
    for (int i = size - 1; i > 0; i--) update(i);
  }
  T get(int p) {
    assert(0 <= p && p <= _n);
    return d[p + size];
  }
  void set(int p, T v) {
    assert(0 <= p && p <= _n);
    p += size;
    d[p] = v;
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  void apply(int p, T v) {
    assert(0 <= p && p <= _n);
    p += size;
    d[p] = M::op(d[p], v);
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  T all_prod() { return d[1]; }
  T prod(int l, int r) {
    if (l >= r) return M::e();
    assert(0 <= l && l <= r && r <= _n);
    T sl = M::e(), sr = M::e();
    l += size, r += size;
    while (l < r) {
      if ((l & 1) != 0) sl = M::op(sl, d[l++]);
      if ((r & 1) != 0) sr = M::op(d[--r], sr);
      l >>= 1, r >>= 1;
    }
    return M::op(sl, sr);
  }

  template <bool (*f)(T)>
  int max_right(int l) const {
    return max_right(l, [](T x) { return f(x); });
  }
  template <class F>
  int max_right(int l, F f) const {
    assert(0 <= l && l <= size);
    assert(f(M::e()));
    if (l == _n) return _n;
    l += size;
    T s = M::e();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!f(M::op(s, d[l]))) {
        while (l < size) {
          l <<= 1;
          if (f(M::op(s, d[l]))) s = M::op(s, d[l++]);
        }
        return l - size;
      }
      s = M::op(s, d[l++]);
    } while ((l & -l) != l);
    return _n;
  }

  template <bool (*f)(T)>
  int min_left(int r) const {
    return min_left(r, [](T x) { return f(x); });
  }
  template <class F>
  int min_left(int r, F f) const {
    assert(0 <= r && r <= _n);
    assert(f(M::e()));
    if (r == 0) return 0;
    r += size;
    T s = M::e();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!f(M::op(d[r], s))) {
        while (r < size) {
          r <<= 1, r++;
          if (f(M::op(d[r], s))) s = M::op(d[r--], s);
        }
        return r + 1 - size;
      }
      s = M::op(d[r], s);
    } while ((r & -r) != r);
    return 0;
  }
};

/**
 * @brief Segment Tree
 * @docs docs/segment-tree/segment-tree.md
 */
#line 2 "string/rolling-hash-monoid.hpp"

#line 2 "string/rolling-hash-value.hpp"

#line 2 "string/rolling-hash-base.hpp"

struct RollingHashBase {
  using u128 = __uint128_t;
  using i128 = __int128_t;
  using u64 = uint64_t;
  static constexpr u64 MOD = (1ull << 61) - 1;
  static u64 base;
  static u64 add(u64 x, u64 y) {
    if ((x += y) >= MOD) x -= MOD;
    return x;
  }
  static u64 sub(u64 x, u64 y) {
    if ((x -= y) >= MOD) x += MOD;
    return x;
  }
  static u64 mul(u64 x, u64 y) {
    u128 z = (u128)x * y;
    u64 v = (u64(z) & MOD) + u64(z >> 61);
    return v >= MOD ? v - MOD : v;
  }
  static u64 normalize(u64 v) {
    u64 x = (v & MOD) + (v >> 61);
    return x >= MOD ? x - MOD : x;
  }
  template <class T>
  static u64 normalize(T v) {
    static_assert(is_integral_v<T> && sizeof(T) <= sizeof(u64));
    if constexpr (is_signed_v<T>) {
      if (v < 0) {
        u64 x = normalize(u64(-i128(v)));
        return x == 0 ? 0 : MOD - x;
      }
    }
    return normalize(u64(v));
  }
  template <class T>
  static T restore(u64 v) {
    static_assert(is_integral_v<T> && sizeof(T) <= sizeof(u64));
    assert(v < MOD);
    if constexpr (is_signed_v<T>) {
      if (v <= u64(numeric_limits<T>::max())) return T(v);
      u64 x = MOD - v;
      assert(i128(x) <= -i128(numeric_limits<T>::min()));
      return T(-i128(x));
    } else {
      assert(v <= u64(numeric_limits<T>::max()));
      return T(v);
    }
  }
};
inline RollingHashBase::u64 RollingHashBase::base = []() {
  random_device seed_gen;
  mt19937_64 rnd(seed_gen());
  return uniform_int_distribution<u64>(256, MOD - 2)(rnd);
}();
#line 4 "string/rolling-hash-value.hpp"

struct RollingHashValue : RollingHashBase {
  u64 hash, power;
  RollingHashValue() : hash(0), power(1) {}
  RollingHashValue(u64 h, u64 p) : hash(h), power(p) {}
  template <class T>
  static RollingHashValue single(T v) {
    return RollingHashValue(normalize(v), base);
  }
  RollingHashValue& operator+=(RollingHashValue rhs) {
    hash = add(mul(hash, rhs.power), rhs.hash);
    power = mul(power, rhs.power);
    return *this;
  }
  friend RollingHashValue operator+(RollingHashValue lhs, RollingHashValue rhs) {
    return lhs += rhs;
  }
  friend bool operator==(RollingHashValue lhs, RollingHashValue rhs) {
    return lhs.hash == rhs.hash && lhs.power == rhs.power;
  }
};

struct RollingHashValueReversible : RollingHashBase {
  u64 hash, reverse_hash, power;
  RollingHashValueReversible() : hash(0), reverse_hash(0), power(1) {}
  RollingHashValueReversible(u64 h, u64 rh, u64 p) : hash(h), reverse_hash(rh), power(p) {}
  template <class T>
  static RollingHashValueReversible single(T v) {
    u64 h = normalize(v);
    return RollingHashValueReversible(h, h, base);
  }
  RollingHashValueReversible& operator+=(RollingHashValueReversible rhs) {
    hash = add(mul(hash, rhs.power), rhs.hash);
    reverse_hash = add(reverse_hash, mul(rhs.reverse_hash, power));
    power = mul(power, rhs.power);
    return *this;
  }
  RollingHashValueReversible reversed() const {
    return RollingHashValueReversible(reverse_hash, hash, power);
  }
  friend RollingHashValueReversible operator+(RollingHashValueReversible lhs,
                                              RollingHashValueReversible rhs) {
    return lhs += rhs;
  }
  friend bool operator==(RollingHashValueReversible lhs, RollingHashValueReversible rhs) {
    return lhs.hash == rhs.hash && lhs.reverse_hash == rhs.reverse_hash &&
           lhs.power == rhs.power;
  }
};
#line 4 "string/rolling-hash-monoid.hpp"

struct RollingHashMonoid {
  using value_type = RollingHashValue;
  static value_type op(value_type x, value_type y) { return x + y; }
  static value_type e() { return value_type(); }
  template <class T>
  static value_type single(T v) {
    return value_type::single(v);
  }
  template <class Sequence>
  static vector<value_type> init(const Sequence& a) {
    vector<value_type> v(a.size());
    for (int i = 0; i < (int)a.size(); i++) v[i] = single(a[i]);
    return v;
  }
};

struct RollingHashMonoidReversible {
  using value_type = RollingHashValueReversible;
  static value_type op(value_type x, value_type y) { return x + y; }
  static value_type e() { return value_type(); }
  template <class T>
  static value_type single(T v) {
    return value_type::single(v);
  }
  template <class Sequence>
  static vector<value_type> init(const Sequence& a) {
    vector<value_type> v(a.size());
    for (int i = 0; i < (int)a.size(); i++) v[i] = single(a[i]);
    return v;
  }
};
#line 5 "string/rolling-hash-segment-tree.hpp"

template <class Value = char>
struct RollingHashSegmentTree : SegmentTree<RollingHashMonoid> {
  using M = RollingHashMonoid;
  using SegTree = SegmentTree<M>;
  RollingHashSegmentTree() : SegTree() {}
  explicit RollingHashSegmentTree(const vector<Value>& a) : SegTree(M::init(a)) {}
  explicit RollingHashSegmentTree(const string& s) : SegTree(M::init(s)) {}
  void set(int p, Value v) { SegTree::set(p, M::single(v)); }
  Value get(int p) { return RollingHashBase::restore<Value>(SegTree::get(p).hash); }
  RollingHashValue prod(int l, int r) { return SegTree::prod(l, r); }
};

template <class Value = char>
struct RollingHashSegmentTreeReversible : SegmentTree<RollingHashMonoidReversible> {
  using M = RollingHashMonoidReversible;
  using SegTree = SegmentTree<M>;
  RollingHashSegmentTreeReversible() : SegTree() {}
  explicit RollingHashSegmentTreeReversible(const vector<Value>& a) : SegTree(M::init(a)) {}
  explicit RollingHashSegmentTreeReversible(const string& s) : SegTree(M::init(s)) {}
  void set(int p, Value v) { SegTree::set(p, M::single(v)); }
  Value get(int p) { return RollingHashBase::restore<Value>(SegTree::get(p).hash); }
  RollingHashValueReversible prod(int l, int r) { return SegTree::prod(l, r); }
};