sparse_table.hpp

View this file on GitHub
Last update: 2025-01-19 15:28:01+08:00
Include: #include "sparse_table.hpp"

Depends on

monoid.hpp

Verified with

test/data_structure/staticrmq.0.test.cpp

Code

#pragma once

#include "monoid.hpp"
#include <cassert>
#include <vector>

template<typename Tp, typename Op> class SparseTable {
public:
    const int N;
    const Monoid<Tp, Op> M;
    std::vector<Tp> T;

    SparseTable(const std::vector<Tp> &V, const Monoid<Tp, Op> &M) : N(V.size()), M(M) {
        int LogN = 0;
        while ((1 << LogN) < N) ++LogN;
        T.resize((LogN + 1) * N);
        for (int i = 0; i < N; ++i) T[i] = V[i];
        for (int i = 1; i <= LogN; ++i) {
            auto P = T.begin() + (i - 1) * N, C = P + N;
            for (int j = 0; j < N - (1 << i) + 1; ++j) C[j] = M(P[j], P[j + (1 << (i - 1))]);
        }
    }

    // returns M(V[L],...,V[R-1])
    Tp query(int L, int R) const {
        assert(L <= R);
        if (L == R) return M.id();
        const int lv = 31 - __builtin_clz(R - L);
        return M(T[lv * N + L], T[lv * N + R - (1 << lv)]);
    }
};

#line 2 "sparse_table.hpp"

#line 2 "monoid.hpp"

#include <type_traits>

template<typename Tp, typename Op,
         std::enable_if_t<std::is_invocable_r_v<Tp, Op, const Tp &, const Tp &>, int> = 0>
class Monoid {
public:
    Op F;
    Tp Id;

    explicit Monoid(Op F, const Tp &Id = {}) : F(F), Id(Id) {}

    const Tp &id() const { return Id; }
    Tp operator()(const Tp &L, const Tp &R) const { return F(L, R); }
};
#line 4 "sparse_table.hpp"
#include <cassert>
#include <vector>

template<typename Tp, typename Op> class SparseTable {
public:
    const int N;
    const Monoid<Tp, Op> M;
    std::vector<Tp> T;

    SparseTable(const std::vector<Tp> &V, const Monoid<Tp, Op> &M) : N(V.size()), M(M) {
        int LogN = 0;
        while ((1 << LogN) < N) ++LogN;
        T.resize((LogN + 1) * N);
        for (int i = 0; i < N; ++i) T[i] = V[i];
        for (int i = 1; i <= LogN; ++i) {
            auto P = T.begin() + (i - 1) * N, C = P + N;
            for (int j = 0; j < N - (1 << i) + 1; ++j) C[j] = M(P[j], P[j + (1 << (i - 1))]);
        }
    }

    // returns M(V[L],...,V[R-1])
    Tp query(int L, int R) const {
        assert(L <= R);
        if (L == R) return M.id();
        const int lv = 31 - __builtin_clz(R - L);
        return M(T[lv * N + L], T[lv * N + R - (1 << lv)]);
    }
};