スパーステーブル (lib/data_structure/sparse_table.hpp)

• View this file on GitHub
• Last update: 2025-02-22 20:56:01+09:00
• Include: #include "lib/data_structure/sparse_table.hpp"

Required by

• 線形 Sparse Table (lib/data_structure/linear_sparse_table.hpp)
• lib/tree/auxiliary_tree.hpp
• lib/tree/linear_lca.hpp

Verified with

• test/aoj/challenge/2270.test.cpp
• test/aoj/course/ALDS1_14_D.test.cpp
• test/yosupo/data_structure/static_rmq.3.test.cpp
• test/yosupo/data_structure/static_rmq.test.cpp
• test/yosupo/tree/lowest_common_ancestor.2.test.cpp
• test/yukicoder/0901.test.cpp

Code

#pragma once
#include <bit>
#include <cassert>
#include <vector>

/// @brief スパーステーブル
template <class M>
struct sparse_table {
  private:
    using T = typename M::value_type;

  public:
    sparse_table() = default;
    sparse_table(const std::vector<T> &v) : _size(v.size()), data() {
        int b = std::max(1, std::countr_zero(std::bit_ceil<unsigned>(_size)));
        data.emplace_back(v);
        for (int i = 1; i < b; ++i) data.emplace_back(_size + 1 - (1 << i));
        for (int i = 1; i < b; ++i) {
            for (int j = 0; j + (1 << i) <= _size; ++j) {
                data[i][j] = M::op(data[i - 1][j], data[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _size);
        if (l == r) return M::id();
        if (l + 1 == r) return data[0][l];
        int b = 31 - std::countl_zero<unsigned>(r - l - 1);
        return M::op(data[b][l], data[b][r - (1 << b)]);
    }

  private:
    int _size;
    std::vector<std::vector<T>> data;
};

#line 2 "lib/data_structure/sparse_table.hpp"
#include <bit>
#include <cassert>
#include <vector>

/// @brief スパーステーブル
template <class M>
struct sparse_table {
  private:
    using T = typename M::value_type;

  public:
    sparse_table() = default;
    sparse_table(const std::vector<T> &v) : _size(v.size()), data() {
        int b = std::max(1, std::countr_zero(std::bit_ceil<unsigned>(_size)));
        data.emplace_back(v);
        for (int i = 1; i < b; ++i) data.emplace_back(_size + 1 - (1 << i));
        for (int i = 1; i < b; ++i) {
            for (int j = 0; j + (1 << i) <= _size; ++j) {
                data[i][j] = M::op(data[i - 1][j], data[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _size);
        if (l == r) return M::id();
        if (l + 1 == r) return data[0][l];
        int b = 31 - std::countl_zero<unsigned>(r - l - 1);
        return M::op(data[b][l], data[b][r - (1 << b)]);
    }

  private:
    int _size;
    std::vector<std::vector<T>> data;
};

Back to top page