src/ds/st.hpp

View this file on GitHub
Last update: 2025-10-01 17:55:45+08:00
Include: #include "src/ds/st.hpp"

Verified with

test/ds/st.test.cpp

Code

template <typename T, typename Op>
struct SparseTable {
  int n, m;
  Op op;
  vector<vector<T>> data;
  SparseTable(vector<T> vec, Op op)
      : n(vec.size()), m(32 - __builtin_clz(n)), op(op), data(m, vector<T>(n)) {
    data[0] = move(vec);
    for (int j = 1; j < m; j++)
      for (int i = 0; i + (1 << j) <= n; i++)
        data[j][i] = op(data[j - 1][i], data[j - 1][i + (1 << (j - 1))]);
  }
  T query(int l, int r) const {
    int q = __lg(r - l);
    return op(data[q][l], data[q][r - (1 << q)]);
  }
};

#line 1 "src/ds/st.hpp"
template <typename T, typename Op>
struct SparseTable {
  int n, m;
  Op op;
  vector<vector<T>> data;
  SparseTable(vector<T> vec, Op op)
      : n(vec.size()), m(32 - __builtin_clz(n)), op(op), data(m, vector<T>(n)) {
    data[0] = move(vec);
    for (int j = 1; j < m; j++)
      for (int i = 0; i + (1 << j) <= n; i++)
        data[j][i] = op(data[j - 1][i], data[j - 1][i + (1 << (j - 1))]);
  }
  T query(int l, int r) const {
    int q = __lg(r - l);
    return op(data[q][l], data[q][r - (1 << q)]);
  }
};