ST表模板

如题目＞▽＜

基础

1. ST表（Sparse Table，稀疏表）是一种简单的数据结构，主要用来解决RMQ（Range Maximum/Minimum Query，区间最大/最小值查询）问题。它主要应用倍增的思想，可以实现 [公式] 预处理、 [公式] 查询。
2. RMQ 表示区间最大（最小）值。
3. 可重复贡献问题是指对于运算，满足f（a，a）=a，则对应的区间询问就是一个可重复贡献问题。例如，最大值max(a, a) = a ，最大公因数gcd(a, a) = a，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。但像区间和就不具有这个性质。

   代码模板

   int Max[P][21];
   
   int query(int l, int r) {// 求区间【l,r】的所求值
       int k = log2(r - l + 1);
       return max(Max[l][k], Max[r - (1 << k) + 1][k]);
   }
   
   scanf("%d%d", &n, &m);
   for (int i = 1; i <= n; i++) {// 初始数据输入
       scanf("%d", &Max[i][0]);
   }
   
   for (int j = 1; (1 << j) <= n; j++) {// st表的创建
           for (int i = 1; i + (1 << j) - 1 <= n; i++)
           {
               Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);
           }
       }
   
   for (int i = 0; i < m; i++)// 区间查询
       {
           int l, r;
           scanf("%d%d", &l, &r);
           printf("%d\n", query(l, r));
       }

赏

来根小鱼干好吗o( =·ω·= )m

支付宝

微信