src/structure/sparsetable.hpp

View this file on GitHub
Last update: 2026-01-01 02:03:44+09:00
Include: #include "src/structure/sparsetable.hpp"

Depends on

src/template.hpp

Required by

src/tree/lca.hpp

Verified with

src/test/yosupo_lca.cpp

Code

#pragma once
#include "../template.hpp"

template<typename T> struct SparseTable {
    function<T(T,T)> f;
    vector<vector<T>> st;
    SparseTable(const vector<T> v={T{}},
                const function<T(T,T)>& f_=[] (T a,T b){return min(a,b);}):
        f(f_){
        int n=si(v);
        int l=32-__builtin_clz(n);
        st.resize(l,vector<T>(n));
        st[0]=v;
        rep(k,l-1){
            rep(i,n-(1<<(k+1))+1){st[k+1][i]=f(st[k][i],st[k][i+(1<<k)]);}
        }
    }
    T prod(int l,int r){
        int k=31-__builtin_clz(r-l);
        return f(st[k][l],st[k][r-(1<<k)]);
    }
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/structure/sparsetable.hpp"

template<typename T> struct SparseTable {
    function<T(T,T)> f;
    vector<vector<T>> st;
    SparseTable(const vector<T> v={T{}},
                const function<T(T,T)>& f_=[] (T a,T b){return min(a,b);}):
        f(f_){
        int n=si(v);
        int l=32-__builtin_clz(n);
        st.resize(l,vector<T>(n));
        st[0]=v;
        rep(k,l-1){
            rep(i,n-(1<<(k+1))+1){st[k+1][i]=f(st[k][i],st[k][i+(1<<k)]);}
        }
    }
    T prod(int l,int r){
        int k=31-__builtin_clz(r-l);
        return f(st[k][l],st[k][r-(1<<k)]);
    }
};