Sparse Table
(byslib/ds/sparse_table.hpp)

• View this file on GitHub
• Last update: 2022-12-02 16:14:56+09:00
• Include: #include "byslib/ds/sparse_table.hpp"
• Link: https://ikatakos.com/pot/programming_algorithm/data_structure/sparse_table

Depends on

• byslib/core/int_alias.hpp

Required by

• Lowest Common Ancestor (byslib/graph/lca.hpp)

Verified with

• test/yosupo/staticrmq.test.cpp

Code

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

#include "../core/int_alias.hpp"
/**
 * @file sparse_table.hpp
 * @brief Sparse Table
 */
namespace bys {
/**
 * @brief Sparse Table
 *
 * 構築: O(NlogN)
 * クエリ: O(1)
 * See:
 * https://ikatakos.com/pot/programming_algorithm/data_structure/sparse_table
 *
 * @tparam Band モノイドで冪等性があるもの
 */
template <class Band> class SparseTable {
    using T = typename Band::set_type;
    i32 n;
    std::vector<i32> lookup;
    std::vector<std::vector<T>> table;

  public:
    SparseTable() {}
    SparseTable(const std::vector<T>& v) { build(v); }

    void build(const std::vector<T>& v) {
        n = v.size();
        lookup.resize(n + 1);

        for (i32 i = 2; i < n + 1; ++i) lookup[i] = lookup[i >> 1] + 1;
        i32 max_k = lookup.back();
        table.assign(max_k + 1, std::vector<T>(n));
        std::copy(v.begin(), v.end(), table[0].begin());
        for (i32 i = 1; i <= max_k; ++i) {
            for (i32 j = 0; j <= n - (1 << i); ++j) {
                table[i][j] = Band::operation(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    T fold(i32 l, i32 r) {
        assert(0 <= l && l <= n);
        assert(0 <= r && r <= n);
        if (l >= r) return Band::identity;
        i32 w = r - l;
        return Band::operation(table[lookup[w]][l], table[lookup[w]][r - (1 << lookup[w])]);
    }
};
}  // namespace bys

#include <algorithm>
#include <cassert>
#include <vector>

#include <cstdint>
namespace bys {
using i8 = std::int8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;
using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;
using f32 = float;
using f64 = double;
using f128 = long double;

using isize = std::ptrdiff_t;
using usize = std::size_t;

#define DEFINE_NUM_LITERAL(name, type) \
    constexpr auto operator"" name(unsigned long long x) { return static_cast<type>(x); }

DEFINE_NUM_LITERAL(_i8, std::int8_t);
DEFINE_NUM_LITERAL(_i16, std::int16_t);
DEFINE_NUM_LITERAL(_i32, std::int32_t);
DEFINE_NUM_LITERAL(_i64, std::int64_t);
DEFINE_NUM_LITERAL(_i128, __int128_t);
DEFINE_NUM_LITERAL(_u8, std::uint8_t);
DEFINE_NUM_LITERAL(_u16, std::uint16_t);
DEFINE_NUM_LITERAL(_u32, std::uint32_t);
DEFINE_NUM_LITERAL(_u64, std::uint64_t);
DEFINE_NUM_LITERAL(_u128, __uint128_t);
DEFINE_NUM_LITERAL(_z, std::size_t);
#undef DEFINE_NUM_LITERAL
}  // namespace bys
/**
 * @file sparse_table.hpp
 * @brief Sparse Table
 */
namespace bys {
/**
 * @brief Sparse Table
 *
 * 構築: O(NlogN)
 * クエリ: O(1)
 * See:
 * https://ikatakos.com/pot/programming_algorithm/data_structure/sparse_table
 *
 * @tparam Band モノイドで冪等性があるもの
 */
template <class Band> class SparseTable {
    using T = typename Band::set_type;
    i32 n;
    std::vector<i32> lookup;
    std::vector<std::vector<T>> table;

  public:
    SparseTable() {}
    SparseTable(const std::vector<T>& v) { build(v); }

    void build(const std::vector<T>& v) {
        n = v.size();
        lookup.resize(n + 1);

        for (i32 i = 2; i < n + 1; ++i) lookup[i] = lookup[i >> 1] + 1;
        i32 max_k = lookup.back();
        table.assign(max_k + 1, std::vector<T>(n));
        std::copy(v.begin(), v.end(), table[0].begin());
        for (i32 i = 1; i <= max_k; ++i) {
            for (i32 j = 0; j <= n - (1 << i); ++j) {
                table[i][j] = Band::operation(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    T fold(i32 l, i32 r) {
        assert(0 <= l && l <= n);
        assert(0 <= r && r <= n);
        if (l >= r) return Band::identity;
        i32 w = r - l;
        return Band::operation(table[lookup[w]][l], table[lookup[w]][r - (1 << lookup[w])]);
    }
};
}  // namespace bys

Back to top page