data_structure/sparse_table.hpp

• View this file on GitHub
• Last update: 2024-10-14 18:11:31+09:00
• Include: #include "data_structure/sparse_table.hpp"

Verified with

• test/data_structure/Static_RMQ.test.cpp

Code

#pragma once

#include <vector>
#include <cassert>

namespace noya2{

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

} // namespace noya2

#line 2 "data_structure/sparse_table.hpp"

#include <vector>
#include <cassert>

namespace noya2{

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

} // namespace noya2

Back to top page