Sparse Table
(data-structure/sparse-table.hpp)

• View this file on GitHub
• Last update: 2023-01-31 00:28:06+09:00
• Include: #include "data-structure/sparse-table.hpp"

Required by

• string/string-search.hpp
• string/suffix-array.hpp

Verified with

• verify/verify-unit-test/sparse-table.test.cpp
• verify/verify-unit-test/string-search.test.cpp
• verify/verify-yosupo-ds/yosupo-static-rmq.test.cpp
• verify/verify-yosupo-string/yosupo-number-of-substrings.test.cpp
• verify/verify-yosupo-string/yosupo-suffix-array.test.cpp
• verify/verify-yosupo-string/yosupo-zalgo-suffixarray.test.cpp
• verify/verify-yuki/yuki-2231.test.cpp

Code

#pragma once

#include <cassert>
#include <limits>
#include <vector>
using namespace std;

template <typename T>
struct SparseTable {
  inline static constexpr T INF = numeric_limits<T>::max() / 2;
  int N;
  vector<vector<T> > table;
  T f(T a, T b) { return min(a, b); }
  SparseTable() {}
  SparseTable(const vector<T> &v) : N(v.size()) {
    int b = 1;
    while ((1 << b) <= N) ++b;
    table.push_back(v);
    for (int i = 1; i < b; i++) {
      table.push_back(vector<T>(N, INF));
      for (int j = 0; j + (1 << i) <= N; j++) {
        table[i][j] = f(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
      }
    }
  }
  // [l, r)
  T query(int l, int r) {
    assert(0 <= l and l <= r and r <= N);
    if (l == r) return INF;
    int b = 31 - __builtin_clz(r - l);
    return f(table[b][l], table[b][r - (1 << b)]);
  }
};

/**
 * @brief Sparse Table
 */

#line 2 "data-structure/sparse-table.hpp"

#include <cassert>
#include <limits>
#include <vector>
using namespace std;

template <typename T>
struct SparseTable {
  inline static constexpr T INF = numeric_limits<T>::max() / 2;
  int N;
  vector<vector<T> > table;
  T f(T a, T b) { return min(a, b); }
  SparseTable() {}
  SparseTable(const vector<T> &v) : N(v.size()) {
    int b = 1;
    while ((1 << b) <= N) ++b;
    table.push_back(v);
    for (int i = 1; i < b; i++) {
      table.push_back(vector<T>(N, INF));
      for (int j = 0; j + (1 << i) <= N; j++) {
        table[i][j] = f(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
      }
    }
  }
  // [l, r)
  T query(int l, int r) {
    assert(0 <= l and l <= r and r <= N);
    if (l == r) return INF;
    int b = 31 - __builtin_clz(r - l);
    return f(table[b][l], table[b][r - (1 << b)]);
  }
};

/**
 * @brief Sparse Table
 */

Back to top page