Sparse Table

2026-04-262026-05-05

线下模版

普通ST表

using T = int;
vector<vector<T>> st;
int n, logn;

inline T Pred(T a, T b) {
  return max(a, b);
}

void init(const vector<T>& a) { // a为0-based
  logn = __lg(n);
  st.resize(logn + 1, vector<T>(n));
  st[0] = a;
  for (int k = 1; k <= logn; k ++) {
    for (int r = (1 << k) - 1; r < n; r ++) {
      st[k][r] = Pred(st[k - 1][r], st[k - 1][r - (1 << (k - 1))]);
    }
  }
}

T query(int l, int r) {
  int k = __lg(r - l + 1);
  return Pred(st[k][r], st[k][l + (1 << k) - 1]);
}

尾部更新ST表

#include <bits/stdc++.h>
using namespace std;

using T = int;

vector<vector<T>> st;
int n, logn; // 当前 ST 表中的元素个数

inline T Pred(T a, T b) {
    return max(a, b);
}

// 多测时清空 ST 表
void init() {
  logn = __lg(n);
  st.resize(logn + 1, vector<T>(n));
  st[0] = a;
  for (int k = 1; k <= logn; k ++) {
    for (int r = (1 << k) - 1; r < n; r ++) {
      st[k][r] = Pred(st[k - 1][r], st[k - 1][r - (1 << (k - 1))]);
    }
  }
}

// 在尾部动态追加一个元素，时间复杂度 O(log N)
void add(const T& x) {
    int i = n++; // 当前插入的下标（0-based）
    int logn = __lg(n); // 当前需要的最大倍增层数

    // 如果需要的层数超过了现有的二维 vector 大小，动态增加一层
    if (st.size() <= logn) {
        st.resize(logn + 1);
    }

    // 0 层直接压入原数值
    st[0].push_back(x);

    // 递推计算以当前元素 i 为右端点的各个倍增区间
    for (int k = 1; k <= logn; k++) {
        // 【核心对齐技巧】：
        // 长度为 2^k 的区间，其右端点 i 至少要是 (1<<k)-1
        // 对于前面不够长的位置，我们塞入无意义的占位符 T()，强行让下标与 i 对齐
        while (st[k].size() < i) {
            st[k].push_back(T()); 
        }
        // 计算并存入 st[k][i]
        st[k].push_back(Pred(st[k - 1][i], st[k - 1][i - (1 << (k - 1))]));
    }
}

// O(1) 在线区间查询
inline T query(int l, int r) {
    int k = __lg(r - l + 1);
    return Pred(st[k][r], st[k][l + (1 << k) - 1]);
}