ds/sparseTable.cpp

• View this file on GitHub
• Last update: 2024-01-24 20:41:29+08:00

Verified with

• test/static_RMQ.test.cpp

Code

template<class T>
struct sparseTable{
  vector<vector<T> > table;
  function<T(const T&, const T&)> comb;
  int size = 0;

  sparseTable(vector<T> base, function<T(const T&, const T&)> _comb) {
    comb = _comb;
    size = base.size();
    table.resize(bit_width((unsigned)size), std::vector<T>(size));
    
    table[0] = base;
    for(int i = 1; i < ssize(table); i++) {
      for(int j = 0; j < size; j++) {
        if (j + (1 << (i - 1)) < size)
          table[i][j] = comb(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
        else
          table[i][j] = table[i - 1][j];
      }
    }
  }

  T query(int l, int r) {
    int range = bit_width((unsigned)(r - l)) - 1;
    return comb(table[range][l], table[range][r - (1 << range)]);
  }
};

#line 1 "ds/sparseTable.cpp"
template<class T>
struct sparseTable{
  vector<vector<T> > table;
  function<T(const T&, const T&)> comb;
  int size = 0;

  sparseTable(vector<T> base, function<T(const T&, const T&)> _comb) {
    comb = _comb;
    size = base.size();
    table.resize(bit_width((unsigned)size), std::vector<T>(size));
    
    table[0] = base;
    for(int i = 1; i < ssize(table); i++) {
      for(int j = 0; j < size; j++) {
        if (j + (1 << (i - 1)) < size)
          table[i][j] = comb(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
        else
          table[i][j] = table[i - 1][j];
      }
    }
  }

  T query(int l, int r) {
    int range = bit_width((unsigned)(r - l)) - 1;
    return comb(table[range][l], table[range][r - (1 << range)]);
  }
};

Back to top page