Disjoint sparse table
(sparse_table/disjoint_sparse_table.hpp)

• View this file on GitHub
• Last update: 2021-11-02 23:36:31+09:00
• Include: #include "sparse_table/disjoint_sparse_table.hpp"
• Link: https://discuss.codechef.com/t/tutorial-disjoint-sparse-table/17404
• Link: https://drken1215.hatenablog.com/entry/2018/09/08/162600

Disjoint sparse table の実装．AC Library の Segtree と同様のインターフェース．前計算 $O(N \log N)$，クエリ $O(1)$．Sparse table と異なり，S の二項演算 op は結合法則が成り立てばよい．

使用方法

S op(S l, S r);                 // 半群の元同士の演算．結合法則が成り立てばよい．
vector<S> A(N);                 // 列．
disj_sparse_table<S, op> st(A);
cout << st.prod(l, r) << '\n';  // 半開区間積クエリ．

問題例

• Library Checker: Static RMQ

Verified with

• sparse_table/test/disjoint_sparse_table_rmq.test.cpp
• sparse_table/test/disjoint_sparse_table_rsq.test.cpp

Code

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

// CUT begin
// Disjoint sparse table
// https://discuss.codechef.com/t/tutorial-disjoint-sparse-table/17404
// https://drken1215.hatenablog.com/entry/2018/09/08/162600
// Complexity: O(NlogN) for precalculation, O(1) per query
// - get(l, r): return op(x_l, ..., x_{r - 1})
template <class S, S (*op)(S, S)> struct disj_sparse_table {
    int N, sz;
    std::vector<std::vector<S>> d;
    static int _msb(int x) noexcept { return x == 0 ? 0 : (__builtin_clz(x) ^ 31); }
    disj_sparse_table() = default;
    disj_sparse_table(const std::vector<S> &seq) : N(seq.size()) {
        sz = 1 << (_msb(N - 1) + 1);
        d.assign(_msb(sz) + 1, std::vector<S>(sz));
        std::copy(seq.begin(), seq.end(), d[0].begin());

        for (int h = 1, half = 2; half < N; ++h, half <<= 1) {
            for (int i = half; i < sz; i += half * 2) {
                d[h][i - 1] = d[0][i - 1];
                for (int j = i - 2; j >= i - half; --j) d[h][j] = op(d[0][j], d[h][j + 1]);
                d[h][i] = d[0][i];
                for (int j = i + 1; j < i + half; ++j) d[h][j] = op(d[h][j - 1], d[0][j]);
            }
        }
    }
    // [l, r), 0-indexed
    S prod(int l, int r) const {
        assert(l >= 0 and r <= N and l < r);
        if (l + 1 == r) return d[0][l];
        int h = _msb(l ^ (r - 1));
        return op(d[h][l], d[h][r - 1]);
    }
};

#line 2 "sparse_table/disjoint_sparse_table.hpp"
#include <algorithm>
#include <cassert>
#include <vector>

// CUT begin
// Disjoint sparse table
// https://discuss.codechef.com/t/tutorial-disjoint-sparse-table/17404
// https://drken1215.hatenablog.com/entry/2018/09/08/162600
// Complexity: O(NlogN) for precalculation, O(1) per query
// - get(l, r): return op(x_l, ..., x_{r - 1})
template <class S, S (*op)(S, S)> struct disj_sparse_table {
    int N, sz;
    std::vector<std::vector<S>> d;
    static int _msb(int x) noexcept { return x == 0 ? 0 : (__builtin_clz(x) ^ 31); }
    disj_sparse_table() = default;
    disj_sparse_table(const std::vector<S> &seq) : N(seq.size()) {
        sz = 1 << (_msb(N - 1) + 1);
        d.assign(_msb(sz) + 1, std::vector<S>(sz));
        std::copy(seq.begin(), seq.end(), d[0].begin());

        for (int h = 1, half = 2; half < N; ++h, half <<= 1) {
            for (int i = half; i < sz; i += half * 2) {
                d[h][i - 1] = d[0][i - 1];
                for (int j = i - 2; j >= i - half; --j) d[h][j] = op(d[0][j], d[h][j + 1]);
                d[h][i] = d[0][i];
                for (int j = i + 1; j < i + half; ++j) d[h][j] = op(d[h][j - 1], d[0][j]);
            }
        }
    }
    // [l, r), 0-indexed
    S prod(int l, int r) const {
        assert(l >= 0 and r <= N and l < r);
        if (l + 1 == r) return d[0][l];
        int h = _msb(l ^ (r - 1));
        return op(d[h][l], d[h][r - 1]);
    }
};

Back to top page