Sparse Table
(library/datastructure/sparse_table.hpp)

• View this file on GitHub
• Last update: 2022-05-29 02:48:02+09:00
• Include: #include "library/datastructure/sparse_table.hpp"

Sparse Table

Required by

• 隣接要素の差が $\pm 1$ の場合の RMQ (library/algorithm/rmq_pm1.hpp)
• 隣接要素の差が $\pm 1$ の場合の RMQ (添字の復元付き) (library/algorithm/rmq_pm1_with_index.hpp)
• Compare Substring (library/string/compare_substring.hpp)
• Lowest Common Ancestor (library/tree/lowest_common_ancestor.hpp)

Verified with

• test/src/string/compare_substring/abc141_e.test.cpp
• test/src/string/compare_substring/dummy.test.cpp
• test/src/string/compare_substring/string_search.test.cpp
• test/src/string/compare_substring/substring.test.cpp
• test/src/tree/level_ancestor/jump_on_tree.test.cpp
• test/src/tree/lowest_common_anceestor/lowest_common_anceestor.test.cpp

Code

#ifndef SUISEN_SPARSE_TABLE
#define SUISEN_SPARSE_TABLE

#include <vector>

namespace suisen {
    template <typename T, T(*op)(T, T), T(*e)()>
    struct SparseTable {
        SparseTable() = default;
        SparseTable(std::vector<T>&& a) : n(a.size()), log(floor_log2(n)), table(log + 1), flog(n + 1, 0) {
            build_table(std::move(a));
            build_flog_table();
        }
        SparseTable(const std::vector<T>& a) : SparseTable(std::vector<T>(a)) {}
        T operator()(int l, int r) const {
            if (l >= r) return e();
            int i = flog[r - l];
            return op(table[i][l], table[i][r - (1 << i)]);
        }
        T prod(int l, int r) const {
            return (*this)(l, r);
        }
    private:
        int n;
        int log;
        std::vector<std::vector<T>> table;
        std::vector<int> flog;

        void build_table(std::vector<T>&& a) {
            table[0] = std::move(a);
            for (int i = 0; i < log; ++i) {
                int lmax = n - (1 << (i + 1));
                table[i + 1].resize(lmax + 1);
                for (int l = 0; l <= lmax; ++l) table[i + 1][l] = op(table[i][l], table[i][l + (1 << i)]);
            }
        }
        void build_flog_table() {
            for (int l = 0; l < log; ++l) {
                std::fill(flog.begin() + (1 << l), flog.begin() + (1 << (l + 1)), l);
            }
            std::fill(flog.begin() + (1 << log), flog.end(), log);
        }
        static int floor_log2(int i) {
            return 31 - __builtin_clz(i);
        }
    };
} // namespace suisen

#endif // SUISEN_SPARSE_TABLE

#line 1 "library/datastructure/sparse_table.hpp"



#include <vector>

namespace suisen {
    template <typename T, T(*op)(T, T), T(*e)()>
    struct SparseTable {
        SparseTable() = default;
        SparseTable(std::vector<T>&& a) : n(a.size()), log(floor_log2(n)), table(log + 1), flog(n + 1, 0) {
            build_table(std::move(a));
            build_flog_table();
        }
        SparseTable(const std::vector<T>& a) : SparseTable(std::vector<T>(a)) {}
        T operator()(int l, int r) const {
            if (l >= r) return e();
            int i = flog[r - l];
            return op(table[i][l], table[i][r - (1 << i)]);
        }
        T prod(int l, int r) const {
            return (*this)(l, r);
        }
    private:
        int n;
        int log;
        std::vector<std::vector<T>> table;
        std::vector<int> flog;

        void build_table(std::vector<T>&& a) {
            table[0] = std::move(a);
            for (int i = 0; i < log; ++i) {
                int lmax = n - (1 << (i + 1));
                table[i + 1].resize(lmax + 1);
                for (int l = 0; l <= lmax; ++l) table[i + 1][l] = op(table[i][l], table[i][l + (1 << i)]);
            }
        }
        void build_flog_table() {
            for (int l = 0; l < log; ++l) {
                std::fill(flog.begin() + (1 << l), flog.begin() + (1 << (l + 1)), l);
            }
            std::fill(flog.begin() + (1 << log), flog.end(), log);
        }
        static int floor_log2(int i) {
            return 31 - __builtin_clz(i);
        }
    };
} // namespace suisen

Back to top page