Sparse Table
(data_structure/sparse_table.hpp)

• View this file on GitHub
• Last update: 2023-06-29 15:06:40+09:00
• Include: #include "data_structure/sparse_table.hpp"

説明

区間クエリを構築 $O(N\log N)$、クエリ $O(1)$ で処理するデータ構造

コンストラクタ

$1$ 次元の配列を渡して、Sparse Tableを構築する。 $O(N\log N)$

get(l, r)

$[l, r)$ のクエリを処理する。 $O(1)$

Depends on

• テンプレート (template/template.hpp)

Verified with

• test/data_structure/StaticRMQ.test.cpp

Code

#pragma once

#include "../template/template.hpp"

namespace lib {

template <class S, S (*op)(S, S)> struct SparseTable {
    vector<vector<S>> table;
    vector<int> clz;
    SparseTable(const vector<S> &vec) {
        int n = vec.size(), n2 = 0;
        while ((1 << n2) < n) n2++;
        table.resize(n2 + 1);
        rep(i, 0, n2 + 1) {
            table[i].resize(n);
            if (i == 0) {
                rep(j, 0, n) table[i][j] = vec[j];
            } else {
                rep(j, 0, n) {
                    if (j + (1 << (i - 1)) < n)
                        table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
                    else
                        table[i][j] = table[i - 1][j];
                }
            }
        }
        clz.resize(n + 1);
        rep(i, 0, n2 + 1) {
            for (int j = (1 << i); j < (2 << i) && j <= n; j++) {
                clz[j] = i;
            }
        }
    }
    // 単位元を要求しないので if (l >= r) return e()
    // みたいなことをしていない、注意すること！！
    S get(int l, int r) {
        assert(r - l > 0);
        // int lgs = 31 - __builtin_clz((unsigned int)(r-l));
        int lgs = clz[r - l];
        return op(table[lgs][l], table[lgs][r - (1 << lgs)]);
    }
};

}  // namespace lib

#line 2 "data_structure/sparse_table.hpp"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 4 "data_structure/sparse_table.hpp"

namespace lib {

template <class S, S (*op)(S, S)> struct SparseTable {
    vector<vector<S>> table;
    vector<int> clz;
    SparseTable(const vector<S> &vec) {
        int n = vec.size(), n2 = 0;
        while ((1 << n2) < n) n2++;
        table.resize(n2 + 1);
        rep(i, 0, n2 + 1) {
            table[i].resize(n);
            if (i == 0) {
                rep(j, 0, n) table[i][j] = vec[j];
            } else {
                rep(j, 0, n) {
                    if (j + (1 << (i - 1)) < n)
                        table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
                    else
                        table[i][j] = table[i - 1][j];
                }
            }
        }
        clz.resize(n + 1);
        rep(i, 0, n2 + 1) {
            for (int j = (1 << i); j < (2 << i) && j <= n; j++) {
                clz[j] = i;
            }
        }
    }
    // 単位元を要求しないので if (l >= r) return e()
    // みたいなことをしていない、注意すること！！
    S get(int l, int r) {
        assert(r - l > 0);
        // int lgs = 31 - __builtin_clz((unsigned int)(r-l));
        int lgs = clz[r - l];
        return op(table[lgs][l], table[lgs][r - (1 << lgs)]);
    }
};

}  // namespace lib

Back to top page