ST表

2021-05-09 | 阅读：次

===

Index

简介
算法实现
模板代码
例题
- 奶牛排队
- 非递减序列的区间众数

简介

ST 表是用于解决 可重复贡献问题 的数据结构。

可重复贡献问题

可重复贡献问题 是指对于运算 opt，满足 x opt x = x，则对应的区间询问就是一个可重复贡献问题。

例如：max(x, x) = x, gcd(x, x) = x;

所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次.

另外，opt还必须满足结合律才能使用 ST 表求解。

什么是RMQ

RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。

算法实现

预处理

以最大值为例，设 f(i,j) 表示区间 [i, i + pow(2, j) - 1] 的最大值，

则 f(i,0) = a[i]

根据 倍增 思路， f(i,j) = max(f(i,j-1), f(i+pow(2,j-1), j-1))

查询

对于每个询问 [l,r] ，把它分成两部分：f[l, l+pow(2,s)-1] 与 f[r-pow(2,s)+1,r]

由于最大值是“可重复贡献问题”，重叠并不会对区间最大值产生影响。又因为这两个区间完全覆盖了，可以保证答案的正确性。

模板代码

template <class T, T (*op)(T, T)>
class ST {
 public:
  int n;
  vector<vector<T>> mat;
 
  ST(const vector<T>& a) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = op(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }
 
  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return op(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

使用方法

维护区间最大值

int op(int x, int y) {
    return max(x, y);
}
int main() {
    vector<int> a{4,6,1,9,0,3}
    ST<int, op> st(a);
    
    int x = 1, y = 3;
    int mx = st.get(x, y); //查询 a[x] ... a[y]区间内的最大值
}

st表维护其它信息

除了区间最值外，其它的 可重复贡献问题

区间按位和
区间按位或
区间 GCD

例题

奶牛排队

acwing 1274 奶牛排队

题目大意：给一个数组，和多个询问，每次询问输出某个 区间最大值与最小值的差

int op1(int x, int y) {return max(x, y);}
int op2(int x, int y) {return min(x, y);}
int main() {
    scanf("%d%d", &n, &q);
    vector<int> a(n);
    for (int i = 0; i < n; i ++ ){
        scanf("%d", &a[i]);
    }
    ST<int,op1> st1(a);
    ST<int,op2> st2(a);
    for (int i = 0; i < q; i ++ ){
        scanf("%d%d", &x, &y);
        cout << st1.get(x-1,y-1)-st2.get(x-1,y-1)<<"\n";
    }
}

非递减序列的区间众数

poj 3368

给定长度为n的非递减数组a，和q个询问，每个询问给定l,r，求区间[l,r] 中出现次数最多的数出现的次数。

1 <= n, q <= 1e5
-1e5 <= a[i] <= 1e5

template <class T>
class RMQ_cnt {
 public:
  int n;
  vector<vector<T> > mat;
  vector<T> vl, vr;
 
  RMQ_cnt(const vector<T>& a) {
    n = static_cast<int>(a.size());
    vl.assign(n, 1);
    vr.assign(n, 1);

    for (int i = 1; i < n; ++i) {
        if (a[i] == a[i - 1]) vl[i] += vl[i - 1];
    }

    for (int i = n - 2; i >= 0; --i) {
        if (a[i] == a[i + 1]) vr[i] += vr[i + 1];
    }

    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0].resize(n);
    
    for (int i = 0; i < n; ++i) {
        mat[0][i] = vl[i] + vr[i] - 1;
    }
    for (int j = 1; j < max_log; j++) {
        mat[j].resize(n - (1 << j) + 1);
        for (int i = 0; i <= n - (1 << j); i++) {
            mat[j][i] = max(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
        }
    }
  }

  T get(int l, int r) const {
    T k = r - l + 1, x = min(k, vr[l]), y = min(k, vl[r]);
    l += x, r -= y;
    if (r < l) return max(x, y);
    int lg = 32 - __builtin_clz(r - l + 1) - 1;
    return max(max(x, y), max(mat[lg][l], mat[lg][r - (1 << lg) + 1]));
  }
};

RMQ_cnt<int> q(a);
void solve(int l, int r) {
    return q.get(l, r);
}

king-yyf