Sparse Table
(Library/DataStructure/SparseTable.hpp)

• View this file on GitHub
• Last update: 2026-06-01 14:08:55+09:00
• Include: #include "Library/DataStructure/SparseTable.hpp"

Sparse Table

長さ $N$ の静的な列 $A = (A_0, \dots, A_{N - 1})$ について、半開区間 $[l, r)$ に対して $\min_{k \in [l, r)} A_k$ を効率的に計算することができるデータ構造です。

Function

Constructor

SparseTable(const vector<Ordered> &A)

• 長さ $N$ の列 $A$ を渡し、Sparse Table を構築します。

制約

• $1 \le N \le 10^6$

計算量

• 時間計算量 : $\textrm{O}(N \log N)$
• 空間計算量 : $\textrm{O}(N \log N)$

---

Fold

inline Ordered Fold(int l, int r) const

• 半開区間 $[l, r)$ に対して $\displaystyle \underset{k \in [l, r)}{\min}\ A_k$ を返します。

制約

• $0 \le l < r \le N$

計算量

• $\textrm{O}(1)$

---

最終更新 : Ver.6.0.0

---

Depends on

• Library/Common.hpp

Verified with

• verify/LC-StaricRMQ.test.cpp

Code

#pragma once

#include "../Common.hpp"

template<typename Ordered>
class SparseTable{
    public:
    SparseTable(const vector<Ordered> &A) : N((int)A.size()){
        int row = 0;
        while(1 << (row + 1) <= N) ++row;
        data_.resize(row + 1, vector<Ordered>(N + 1));
        for(int i = 0; i < N; ++i) data_[0][i] = A[i];
        for(int k = 0; k < row; ++k){
            for(int i = 0; i + (1 << k) <= N; ++i){
                data_[k + 1][i] = min(data_[k][i], data_[k][i + (1 << k)]);
            }
        }
    }

    inline Ordered Fold(int l, int r) const {
        assert(0 <= l && l < r && r <= N);
        int k = bit_width((uint32_t)r - l) - 1;
        return min(data_[k][l], data_[k][r - (1 << k)]);
    }

    private:
    vector<vector<Ordered>> data_;
    int N;
};

#line 2 "Library/DataStructure/SparseTable.hpp"

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 4 "Library/DataStructure/SparseTable.hpp"

template<typename Ordered>
class SparseTable{
    public:
    SparseTable(const vector<Ordered> &A) : N((int)A.size()){
        int row = 0;
        while(1 << (row + 1) <= N) ++row;
        data_.resize(row + 1, vector<Ordered>(N + 1));
        for(int i = 0; i < N; ++i) data_[0][i] = A[i];
        for(int k = 0; k < row; ++k){
            for(int i = 0; i + (1 << k) <= N; ++i){
                data_[k + 1][i] = min(data_[k][i], data_[k][i + (1 << k)]);
            }
        }
    }

    inline Ordered Fold(int l, int r) const {
        assert(0 <= l && l < r && r <= N);
        int k = bit_width((uint32_t)r - l) - 1;
        return min(data_[k][l], data_[k][r - (1 << k)]);
    }

    private:
    vector<vector<Ordered>> data_;
    int N;
};

Back to top page