静态区间查询（条件动态）——ST表

• 问题引入
• 思路一览
• 具体分析
• 条件动态？

问题引入

给出一个长度为n的数组a，并且给出m咨询问，每次询问给出边间lt和rt，要求给出lt和rt之间的最大值

思路一览

1. 暴力法：记录数组，对于每一次询问，就从lt到rt遍历一遍
2. ST：对数组的区间做一个倍增处理，将每一个区间的答案记录下来，最后使用区间进行比较找出答案

具体分析

假设我们开一个数组，为f[i][j]表示数组中从下标为i的点往后2^j位的区间的答案（包括该点），比如f[1][0]就是第一位往后一位的答案，那么其实f[1][0]就是a[1]，f[1][1]就是max(a[1], a[2])，其实也就是max(f[1][0], f[2][0])，由此我们可以大胆猜测一下f数组是否是一个可以递推的关系，简单的画出下面的图

现在我们要求f[i][3]，那么我们可以从已经求过的区间即f[i][2]和f[i+4][2]求出，观察关系，其实f[i+4][2] = f[2²][2]，也就是说，我们可以从小区间向高区间推，我们刚开始的条件就是f[n]0
那么该递推式的退出条件是什么呢，假设 现在正在求点i，那么该区间的重点就是end = i+(1<<j)-1，当end <= n时，那么该区间可以正常计算，当end > n时，有两种情况，一种是数组越界报错，另外一种是额外的数组默认值会对答案进行影响，因此，该递推式结束的条件应该是end <= n即i+(1<<j)-1 <= n，由此，我们可以写出以下的预处理代码

for(int i=1; i<=n; i++) cin >> f[i][0];
for(int j=1; j<=20; j++) {
  //j的取值上限大致就是log2(n)级别
  for(int i=1; i+(1<<j)-1<=n; j++) f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);
}

以上是预处理过程，当我们要查询的时候，只有两个边界条件lt和rt，据此我们可以求出区间长度和区间级别，k=log2（(rt-lt+1)），不妨假设lt=2，rt=9，因此它的区间级别应该是3，即从2开始向后查8个，j=3，但是这是刚刚好的情况，当这个区间大一点，比如是[2, 10]，这样的话就会漏查，因此在从区间右边查一遍，起点就是rt-(1<<k)+1，由此我们写出以下的查询代码

int k = log2(rt-lt+1);
int ans = max(f[lt][k], f[rt-(1<<k)+1][k]);

正常的查询大致就是这样，这里给出洛谷P2880以及又臭又长的Code

条件动态？

上面说的都是静态查询，至于标题中的条件动态就是来源于洛谷P1198这个题目的提醒，条件是什么呢，该题目给出的条件是只往数组的末尾加元素，这样的话就会只影响到idx-(1<<j)+1的数，其中idx为数组的末尾指针，只需要列举区间即可（对于一个特定的区间，需要修改的也只有一个点），也就是更新该点的该区间值即可，那么按照这个说法，其实往头插应该也是可以的，往头插的话就是只需要更改头结点的值即可，但是比较麻烦的就是它的遍历问题，但是往中间插就是肯定不行了，因为往中间插的话f数组就需要时时更新了，代价太大，不如树状数组出马，这里给出上面一题的Code