test/unittest/sparse-tables.test.cpp

View this file on GitHub
Last update: 2026-08-04 11:40:53+00:00

Depends on

Code

// competitive-verifier: STANDALONE

#include <algorithm>
#include <cassert>
#include <functional>
#include <random>
#include <vector>

#include "../../structure/others/disjoint-sparse-table.hpp"
#include "../../structure/others/sparse-table.hpp"

int main() {
  {
    const std::vector<int> values{5, 2, 7, 1, 6};
    const auto table =
        get_sparse_table(values, [](int a, int b) { return std::min(a, b); });
    assert(table.fold(0, 1) == 5);
    assert(table.fold(1, 4) == 1);
    assert(table.fold(0, 5) == 1);
  }

  {
    const std::vector<int> values{42};
    auto table = get_disjoint_sparse_table(values, std::plus<int>());
    assert(table.fold(0, 1) == 42);
  }

  std::mt19937 rng(123456789);
  for (int n = 1; n <= 50; n++) {
    std::vector<int> values(n);
    for (int& value : values) value = (int)(rng() % 201) - 100;

    const auto minimum =
        get_sparse_table(values, [](int a, int b) { return std::min(a, b); });
    auto sum = get_disjoint_sparse_table(values, std::plus<int>());
    for (int left = 0; left < n; left++) {
      int expected_minimum = values[left];
      int expected_sum = 0;
      for (int right = left + 1; right <= n; right++) {
        expected_minimum = std::min(expected_minimum, values[right - 1]);
        expected_sum += values[right - 1];
        assert(minimum.fold(left, right) == expected_minimum);
        assert(sum.fold(left, right) == expected_sum);
      }
    }
  }
}

#line 1 "test/unittest/sparse-tables.test.cpp"
// competitive-verifier: STANDALONE

#include <algorithm>
#include <cassert>
#include <functional>
#include <random>
#include <vector>

#line 2 "structure/others/disjoint-sparse-table.hpp"

#line 5 "structure/others/disjoint-sparse-table.hpp"

/**
 * @brief Disjoint-Sparse-Table
 *
 */
template <typename Semigroup, typename F>
struct DisjointSparseTable {
  const F f;
  std::vector<std::vector<Semigroup>> st;
  std::vector<int> lookup;

  DisjointSparseTable(const std::vector<Semigroup>& v, const F& f) : f(f) {
    const int n = (int)v.size();
    int b = 0;
    while ((1 << b) <= n) ++b;
    st.resize(b, std::vector<Semigroup>(n, Semigroup()));
    for (int i = 0; i < n; i++) st[0][i] = v[i];
    for (int i = 1; i < b; i++) {
      int shift = 1 << i;
      for (int j = 0; j < n; j += shift << 1) {
        int t = std::min(j + shift, n);
        st[i][t - 1] = v[t - 1];
        for (int k = t - 2; k >= j; k--) st[i][k] = f(v[k], st[i][k + 1]);
        if (n <= t) break;
        st[i][t] = v[t];
        int r = std::min(t + shift, n);
        for (int k = t + 1; k < r; k++) st[i][k] = f(st[i][k - 1], v[k]);
      }
    }
    lookup.resize(1 << b);
    for (int i = 2; i < (1 << b); i++) {
      lookup[i] = lookup[i >> 1] + 1;
    }
  }

  Semigroup fold(int l, int r) {
    if (l >= --r) return st[0][l];
    int p = lookup[l ^ r];
    return f(st[p][l], st[p][r]);
  }
};

template <typename SemiGroup, typename F>
DisjointSparseTable<SemiGroup, F> get_disjoint_sparse_table(
    const std::vector<SemiGroup>& v, const F& f) {
  return {v, f};
}
#line 2 "structure/others/sparse-table.hpp"

#line 4 "structure/others/sparse-table.hpp"

/**
 * @brief Sparse-Table(スパーステーブル)
 *
 */
template <typename T, typename F>
struct SparseTable {
  F f;
  std::vector<std::vector<T>> st;
  std::vector<int> lookup;

  SparseTable() = default;

  explicit SparseTable(const std::vector<T>& v, const F& f) : f(f) {
    const int n = (int)v.size();
    const int b = 32 - __builtin_clz(n);
    st.assign(b, std::vector<T>(n));
    for (int i = 0; i < n; i++) {
      st[0][i] = v[i];
    }
    for (int i = 1; i < b; i++) {
      for (int j = 0; j + (1 << i) <= n; j++) {
        st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
      }
    }
    lookup.resize(v.size() + 1);
    for (int i = 2; i <= n; i++) {
      lookup[i] = lookup[i >> 1] + 1;
    }
  }

  inline T fold(int l, int r) const {
    int b = lookup[r - l];
    return f(st[b][l], st[b][r - (1 << b)]);
  }
};

template <typename T, typename F>
SparseTable<T, F> get_sparse_table(const std::vector<T>& v, const F& f) {
  return SparseTable<T, F>(v, f);
}
#line 11 "test/unittest/sparse-tables.test.cpp"

int main() {
  {
    const std::vector<int> values{5, 2, 7, 1, 6};
    const auto table =
        get_sparse_table(values, [](int a, int b) { return std::min(a, b); });
    assert(table.fold(0, 1) == 5);
    assert(table.fold(1, 4) == 1);
    assert(table.fold(0, 5) == 1);
  }

  {
    const std::vector<int> values{42};
    auto table = get_disjoint_sparse_table(values, std::plus<int>());
    assert(table.fold(0, 1) == 42);
  }

  std::mt19937 rng(123456789);
  for (int n = 1; n <= 50; n++) {
    std::vector<int> values(n);
    for (int& value : values) value = (int)(rng() % 201) - 100;

    const auto minimum =
        get_sparse_table(values, [](int a, int b) { return std::min(a, b); });
    auto sum = get_disjoint_sparse_table(values, std::plus<int>());
    for (int left = 0; left < n; left++) {
      int expected_minimum = values[left];
      int expected_sum = 0;
      for (int right = left + 1; right <= n; right++) {
        expected_minimum = std::min(expected_minimum, values[right - 1]);
        expected_sum += values[right - 1];
        assert(minimum.fold(left, right) == expected_minimum);
        assert(sum.fold(left, right) == expected_sum);
      }
    }
  }
}