ST表模板.cpp

inline int h_bit(unsigned long long x) {
    return sizeof(unsigned long long) * 8 - 1 - __builtin_clzll(x); // or return 63 - __builtin_clzll(x); ??
}
template <typename  T, typename Compare = std::less<T>>
struct ST{
    size_t n; // 0-indexed
    vv<T> a;
//    const static Compare comp;
    template <typename ptr_t>
    ST(ptr_t beg, ptr_t end):n(end-beg){
        a.resize((size_t)h_bit(n)+1); // 注意：不能写成 h_bit(n)
        a[0].assign(beg, end);
        rng (i, 0, SZ(a)-1) {
            a[i+1].resize(n);
            rng(j, 0, n - (1 << i)) {
                a[i+1][j] = min(a[i][j], a[i][j+(1<<i)], Compare());
            }
            rng(j, n-(1 << i), n) {
                a[i+1][j] = a[i][j];
            }
        }
    }

    T query(size_t l, size_t r) { // l <=  r
        int i = h_bit(r - l + 1);
        return min(a[i][l], a[i][r+1-(1<<i)], Compare());
    }
};

给 ST 声明一个 static const Compare comp; 会不会跑得更快呢？