Sparse Table (スパーステーブル)
(DataStructure/sparse_table.hpp)

• View this file on GitHub
• Last update: 2026-11-12 11:56:29+09:00
• Include: #include "DataStructure/sparse_table.hpp"

概要

動的更新はできないが、最初に静的に構築してしまえば、区間最小値を $O(1)$ でとり出すことができる。

仕様

• init(vec): 初期化構築, $O(N \log N)$
• get(a, b): 区間 $[a, b)$ の最小値を取得する, $O(1)$

制約

• 交叉半束 (meet-semi-lattice) 上で動作する
• 半群 (semi-group) 上で動作する上位互換バージョン (disjoint sparse table) もある

問題例

• AtCoder ABC 407 F - Sums of Sliding Window Maximum

参考文献

Verified with

• tests/AtCoder/ABC_407_F_sparse_table.cpp (manual)
• tests/AtCoder/ABC_480_G_anti_monge_dd_smawk.cpp (manual)
• tests/AtCoder/ABC_480_G_li_chao_tree_by_anti_monge_extension_for_all_i_j.cpp (manual)
• tests/AtCoder/ABC_480_G_li_chao_tree_by_anti_monge_shortest_path_using_insert_segment.cpp (manual)
• tests/AtCoder/ABC_480_G_li_chao_tree_using_li_chao_tree_insert_segment.cpp (manual)
• tests/Others/MOFE_monoxercon_202508_K.cpp (manual)

Code

#pragma once
#include <bits/stdc++.h>
#include <cassert>
using namespace std;

// Sparse Table
template<class MeetSemiLattice> struct SparseTable {
    using Func = function<MeetSemiLattice(MeetSemiLattice, MeetSemiLattice)>;

    // core member
    Func OP = [](const MeetSemiLattice &l, const MeetSemiLattice &r) {
        return min(l, r);
    };
    vector<vector<MeetSemiLattice>> dat;
    vector<int> height;
    
    SparseTable() {}
    SparseTable(const vector<MeetSemiLattice> &vec) {
        init(vec);
    }
    SparseTable(const vector<MeetSemiLattice> &vec, const Func &op)  {
        init(vec, op);
    }
    void init(const vector<MeetSemiLattice> &vec) {
        int n = (int)vec.size(), h = 1;
        while ((1<<h) <= n) ++h;
        dat.assign(h, vector<MeetSemiLattice>(1<<h));
        height.assign(n+1, 0);
        for (int i = 2; i <= n; i++) height[i] = height[i>>1]+1;
        for (int i = 0; i < n; ++i) dat[0][i] = vec[i];
        for (int i = 1; i < h; ++i) {
            for (int j = 0; j < n; ++j)
                dat[i][j] = OP(dat[i-1][j], dat[i-1][min(j+(1<<(i-1)),n-1)]);
        }
    }
    void init(const vector<MeetSemiLattice> &vec, const Func &op) {
        OP = op;
        init(vec);
    }
    
    MeetSemiLattice get(int a, int b) {
        return OP(dat[height[b-a]][a], dat[height[b-a]][b-(1<<height[b-a])]);
    }
};

#line 2 "DataStructure/sparse_table.hpp"
#include <bits/stdc++.h>
#line 4 "DataStructure/sparse_table.hpp"
using namespace std;

// Sparse Table
template<class MeetSemiLattice> struct SparseTable {
    using Func = function<MeetSemiLattice(MeetSemiLattice, MeetSemiLattice)>;

    // core member
    Func OP = [](const MeetSemiLattice &l, const MeetSemiLattice &r) {
        return min(l, r);
    };
    vector<vector<MeetSemiLattice>> dat;
    vector<int> height;
    
    SparseTable() {}
    SparseTable(const vector<MeetSemiLattice> &vec) {
        init(vec);
    }
    SparseTable(const vector<MeetSemiLattice> &vec, const Func &op)  {
        init(vec, op);
    }
    void init(const vector<MeetSemiLattice> &vec) {
        int n = (int)vec.size(), h = 1;
        while ((1<<h) <= n) ++h;
        dat.assign(h, vector<MeetSemiLattice>(1<<h));
        height.assign(n+1, 0);
        for (int i = 2; i <= n; i++) height[i] = height[i>>1]+1;
        for (int i = 0; i < n; ++i) dat[0][i] = vec[i];
        for (int i = 1; i < h; ++i) {
            for (int j = 0; j < n; ++j)
                dat[i][j] = OP(dat[i-1][j], dat[i-1][min(j+(1<<(i-1)),n-1)]);
        }
    }
    void init(const vector<MeetSemiLattice> &vec, const Func &op) {
        OP = op;
        init(vec);
    }
    
    MeetSemiLattice get(int a, int b) {
        return OP(dat[height[b-a]][a], dat[height[b-a]][b-(1<<height[b-a])]);
    }
};

Back to top page