Sparse Table
(DataStructure/SparseTable.cpp)

• View this file on GitHub
• Last update: 2021-06-18 21:14:35+09:00

説明

ある区間に対する最小値・最大値などのクエリを処理する。

• SparseTable(vector<T> v) st : vを表現する Sparse Table を作成する。vのサイズを $n$ とすると計算量は $O(n \log n)$
• T st.query(int l,int r) : min(v[l], v[l + 1], … , v[r - 1])を求める。計算量 $O(1)$

※ クエリで用いる演算は min だけでなく冪等半群（英版版 Wikipedia）であればどれでも出来る。todo : min 以外にも対応出来るようにする

Verified with

• Test/yosupo-judge/SparseTable.test.cpp

Code

template <typename T>
class SparseTable {
    vector<vector<T>> table;
    vector<int> lookup;

public:

    SparseTable(vector<T> v) {
        int b = 0;

        while((1 << b) <= v.size()) {
            b++;
        }

        table.resize(b,vector<T>(1 << b));

        for(int i = 0;i < v.size();i++) {
            table[0][i] = v[i];
        }

        for(int i = 1;i < b;i++) {
            for(int j = 0;j + (1 << i) <= (1 << b);j++) {
                table[i][j] = min(table[i - 1][j],table[i - 1][j + (1 << (i - 1))]);
            }
        }

        lookup.resize(v.size() + 1);

        for(int i = 2;i < lookup.size();i++) {
            lookup[i] = lookup[i >> 1] + 1;
        }
    }

    T query(int l,int r) {
        int b = lookup[r - l];
        return min(table[b][l],table[b][r - (1 << b)]);
    }
};

#line 1 "DataStructure/SparseTable.cpp"
template <typename T>
class SparseTable {
    vector<vector<T>> table;
    vector<int> lookup;

public:

    SparseTable(vector<T> v) {
        int b = 0;

        while((1 << b) <= v.size()) {
            b++;
        }

        table.resize(b,vector<T>(1 << b));

        for(int i = 0;i < v.size();i++) {
            table[0][i] = v[i];
        }

        for(int i = 1;i < b;i++) {
            for(int j = 0;j + (1 << i) <= (1 << b);j++) {
                table[i][j] = min(table[i - 1][j],table[i - 1][j + (1 << (i - 1))]);
            }
        }

        lookup.resize(v.size() + 1);

        for(int i = 2;i < lookup.size();i++) {
            lookup[i] = lookup[i >> 1] + 1;
        }
    }

    T query(int l,int r) {
        int b = lookup[r - l];
        return min(table[b][l],table[b][r - (1 << b)]);
    }
};

Back to top page