data-structure/SparseTable.hpp

• View this file on GitHub
• Last update: 2023-03-13 02:01:43+09:00
• Include: #include "data-structure/SparseTable.hpp"

Verified with

• test/yosupo/Data-Structure/Static-RMQ.test.cpp

Code

template <class T, const T&(*op)(const T&,const T&)>
struct SparseTable {
  int n;
  vector<T> a;
  private:
  vector<vector<T>> d;
  vector<int> len;
  T inf = numeric_limits<T>::max();
  public:
  SparseTable(const int n) : n(n), a(n), len(n + 1){}
  SparseTable(const vector<T> &a) : a(a), n(a.size()), len(a.size() + 1){}
  T &operator[](const int i){ return a[i]; }
  void build(){
    inf = -op(inf, -inf);
    int logn = 0;
    while((1 << logn) < n) logn++;
    d.resize(logn + 1, vector<T>(n, inf));
    d[0] = a;
    for(int i = 0; i < logn; i++){
      for(int j = 0; j <= n - (1 << i); j++){
        d[i + 1][j] = op(d[i][j], d[i][j + (1 << i)]);
      }
    }
    for(int i = 2; i <= n; i++) len[i] = len[i >> 1] + 1;
  }
  T query(const int l, const int r) const{
    assert(0 <= l && l <= r && r <= n);
    if(l == r) return inf;
    const int range = len[r - l];
    assert(0 <= range && range < d.size());
    return op(d[range][l], d[range][r - (1 << range)]);
  }
};

#line 1 "data-structure/SparseTable.hpp"
template <class T, const T&(*op)(const T&,const T&)>
struct SparseTable {
  int n;
  vector<T> a;
  private:
  vector<vector<T>> d;
  vector<int> len;
  T inf = numeric_limits<T>::max();
  public:
  SparseTable(const int n) : n(n), a(n), len(n + 1){}
  SparseTable(const vector<T> &a) : a(a), n(a.size()), len(a.size() + 1){}
  T &operator[](const int i){ return a[i]; }
  void build(){
    inf = -op(inf, -inf);
    int logn = 0;
    while((1 << logn) < n) logn++;
    d.resize(logn + 1, vector<T>(n, inf));
    d[0] = a;
    for(int i = 0; i < logn; i++){
      for(int j = 0; j <= n - (1 << i); j++){
        d[i + 1][j] = op(d[i][j], d[i][j + (1 << i)]);
      }
    }
    for(int i = 2; i <= n; i++) len[i] = len[i >> 1] + 1;
  }
  T query(const int l, const int r) const{
    assert(0 <= l && l <= r && r <= n);
    if(l == r) return inf;
    const int range = len[r - l];
    assert(0 <= range && range < d.size());
    return op(d[range][l], d[range][r - (1 << range)]);
  }
};

Back to top page