st表 模板整理

[Draymonders]

老年选手留下了菜菜的眼泪

const int N = 1e5 + 10;
// 2^20 = 1e6 是能cover的
// dp[i][j] 表示 以i为区间起点，2^j为区间长度，所计算的值
int dp[N][19];
int Log[N];

void init(vector<int> & arr) {
    memset(dp, 0, sizeof(dp));
    memset(Log, 0, sizeof(Log));
    int n = arr.size();

    for (int i=0; (1<<i) <= n; i++) {
        Log[(1<<i)] = i; 
    }
    for (int i=1; i<=n; i++) {
        if (!Log[i])
            Log[i] = Log[i-1];
    }

    for (int i=1; i<=n; i++)
        dp[i][0] = arr[i-1];
    for (int j=1; j<19; j++) {
        for (int i=1; i<=n; i++) {
            if (i+(1<<j)-1 <= n) {
                dp[i][j] = (dp[i][j-1] & dp[i+(1<<(j-1))][j-1]);
            } else
                break;
        }
    }
}

int query(int l, int r) {
    int len = (r - l + 1);
    return dp[l][Log[len]] & dp[r - (1<<Log[len]) + 1][Log[len]];
}

int query1(int l, int r) {
    if (l == r)  {
        return dp[l][0];
    } 
    int len = (r - l + 1);
    int cnt = log2(len) + 1;
    int x = 0;
    bool first = true;
    for (int i=cnt; i>=0; i--) {
        if ((len >> i) & 1) {
            if (first) {
                x = dp[l][i];
                l += (1<<i);
                first = false;
            } else {
                x &= dp[l][i];
            }
        }
    }
    return x;
}