ST表 SparseTable

代码模板

template <typename T, T (*op)(T, T)> struct SparseTable {
    vector<vector<T>> dat;
    SparseTable(const vector<T> &v) {
        int n = v.size(), logn = __lg(n);
        dat.assign(n + 1, vector<T>(logn + 1, 0));
        for (int i = 1; i <= n; ++i)
            dat[i][0] = v[i - 1];
        for (int j = 1; j <= logn; ++j)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                dat[i][j] = op(dat[i][j - 1], dat[i + (1 << j - 1)][j - 1]);
    }
    T query(int l, int r) {
        int s = __lg(r - l + 1);
        return op(dat[l][s], dat[r - (1 << s) + 1][s]);
    }
};
int maxn(int a, int b) { return a > b ? a : b; }

1. 首先证明倍增最长枚举范围为 $[0,logn]$

对于 $i=1$ 位置具有最长的枚举范围，满足 $i+2^j-1\le n$，则 $j\le \lfloor \log n\rfloor$，证毕

1. 证明倍增的空间复杂度的下界

• 首先考虑 $n=2^k-1$ 的情况

对于每个 i 的最长枚举长度为 $\lfloor \log (n+1-i)\rfloor +1$

总长度为

&\sum\limits_{i=1}^{n} \lfloor\log(n+1-i)\rfloor+1 \

&=\sum\limits_{i=1}^{n}\lfloor\log(i)\rfloor+1 \

&=\sum\limits_{i=0}^{k-1} (i+1)2^i \

&=(k-1)2^k+1

\end{align*}$$