Sparse Table
(data-structure/sparse_table.hpp)

• View this file on GitHub
• Last update: 2024-01-08 02:22:28+09:00
• Include: #include "data-structure/sparse_table.hpp"

Description

Sparse table は，冪等モノイド $(T, \cdot, e)$ の静的な列の区間積を高速に計算するデータ構造である．

冪等な二項演算とは， $\forall a \in T, a \cdot a = a$ が成り立つような写像 $\cdot: T \times T \rightarrow T$ である．冪等な二項演算には，max, min, gcd, bitwise and, bitwise or などがある．

空間計算量: $O(n \log n)$

Operations

• SparseTable(vector<T> v)
  • vの要素から sparse table を構築する
  • 時間計算量: $O(n \log n)$
• T fold(int l, int r)
  • 区間 $[l, r)$ の値を fold する
  • 時間計算量: $O(1)$

Reference

• Sparse Table

Verified with

• test/aoj/DSL_3_D.sparse_table.test.cpp

Code

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

template <typename M>
class SparseTable {
    using T = M::T;

   public:
    SparseTable() = default;
    explicit SparseTable(const std::vector<T>& v) {
        const int n = v.size();
        const int b = std::bit_width((unsigned int)n);
        lookup.resize(b, std::vector<T>(n));
        std::ranges::copy(v, lookup[0].begin());
        for (int i = 1; i < b; ++i) {
            for (int j = 0; j + (1 << i) <= n; ++j) {
                lookup[i][j] =
                    M::op(lookup[i - 1][j], lookup[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    T fold(int l, int r) const {
        if (l == r) return M::id();
        int i = std::bit_width((unsigned int)(r - l)) - 1;
        return M::op(lookup[i][l], lookup[i][r - (1 << i)]);
    }

   private:
    std::vector<std::vector<T>> lookup;
};

#line 2 "data-structure/sparse_table.hpp"
#include <algorithm>
#include <bit>
#include <vector>

template <typename M>
class SparseTable {
    using T = M::T;

   public:
    SparseTable() = default;
    explicit SparseTable(const std::vector<T>& v) {
        const int n = v.size();
        const int b = std::bit_width((unsigned int)n);
        lookup.resize(b, std::vector<T>(n));
        std::ranges::copy(v, lookup[0].begin());
        for (int i = 1; i < b; ++i) {
            for (int j = 0; j + (1 << i) <= n; ++j) {
                lookup[i][j] =
                    M::op(lookup[i - 1][j], lookup[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    T fold(int l, int r) const {
        if (l == r) return M::id();
        int i = std::bit_width((unsigned int)(r - l)) - 1;
        return M::op(lookup[i][l], lookup[i][r - (1 << i)]);
    }

   private:
    std::vector<std::vector<T>> lookup;
};

Back to top page