ST表------解决区间不可重复贡献问题

在阅读本文章之前，请确保您有足够的ST表基础。

1、ST表的概念

普通的ST表是能够解决RMQ(可重复贡献问题)的数据结构，能够在$O(nlogn)$时间复杂度预处理，在$O(1)$时间复杂度回答每个询问，遗憾的是不能解决带修改的RMQ问题，也不能解决区间可重复贡献问题。

2、ST表的实现

我们以区间最大值为例：
首先，规定 $f_{i,j}$ 表示从 $i$ 开始，到第 $i+2^j-1$ 个数中间的最大值，很显然，$f_{i,0}$ 就是 当前的数组中下标为 $i$ 的值(方便起见，以后简称 $a_i$)。那么我们怎么转移呢？要想得知 $f_{i,j}$ 的值，而且必须 $O(1)$ 时间内转移过来，我们首先规定两个前提：

1、计算到 $f_{i,j}$ 时，所有 $f_{i,k}(0\le k<j)$ 都已经计算过。
2、计算到 $f_{i,j}$ 时，所有 $f_{s,t}(i<s\le n,0\le t<j)$ 都已经计算过。

满足第一个前提，我们可以递增 $j$ 来计算；满足第二个前提，我们可以递减 $i$ 来计算，这样，状态转移方程就可以列举出来了。
$$f_{i,j}=max(f_{i,j-1},f_{i+(1<<j)-1,j-1})$$
(其它RMQ问题同理，如区间 $gcd$ ，则把 $max()$ 改为 $gcd()$ 即可)

3、如何解决区间不可重复贡献问题

1、分析

这里以解决区间异或和作为例子。
题目大意：

   给你一个长度为 $n$ 的数组 $a$ ，和 $m$ 次询问 $l_i,r_i(l_i\le r_i)$，求出每次询问中 $a_{l_i}⨁a_{l_i+1}⨁...⨁a_{r_i}$ 的值，我们以 $⨁$ 表示 C++ 中的 $xor$ (按位异或) 运算。

不少人看到这里可能会想起线段树，但是线段树的常数稍微有一点大，我们有没有更加快的方法呢？

我们先按照ST表的公式 $f_{i,j}=f_{i,j-1}⨁f_{i+(1<<j)-1,j-1}$，依次求出每一个 $f_{i,j}$ ，然后观察题目，我们发现这是一个区间不可重复贡献问题，但是，俗话说得好，负负得正，$a⨁a=0$，而再异或上一个 $a$，即 $a⨁a⨁a$，结果又等于 $a$ 了，于是，我们有了一个大胆的想法。
给你 $l_i,r_i$，我们先找到最小的 $x$ ，使得 $f_{l_i,x}$ 与 $f_{r_i-1<<x+1,x}$ 能够覆盖整个 $l_i,r_i$ 区间(此处以 $L$ 表示 $l_i$ ，$R$ 表示 $r_i$，$s$ 表示 $l_i+(1<<x)-1$，$t$ 表示 $R-(1<<x)+1$，$len$ 表示 $1<<x$(即区间的长度))。

2、找最小的 $x$

怎么找最小的 $x$ 呢？不能用普通ST表中的 $log(r-l+1)/log(2)$，那样的话会多出来一段不必要的区间，从而影响此算法的正确性。
初始化最小的 $x$：

	j=1;
	for(i=1;i<=n;i++){
	op[i] = op[i-1];
	    for(;j*2<i;j*=2,op[i]++);
	}

$o{p}_i$ 表示当区间长度为 $i$ 时，$x$ 至少为 $o{p}_i$ 才能覆盖整个区间。
因为 $o{p}_i$ 一定大于等于 $o{p}_{i-1}$ ，所以我们用双指针 $O(n)$ 预处理，当处理询问时，直接赋值即可。

3、找边界条件

第一幅图中，假如直接计算出 $f_{l,x}⨁f_{t,x}$，答案肯定是不对的，因为中间的 $[t,s]$ 这一段区间重复算过了，但是，根据异或的基本原理，如果再异或一次 $[t,s]$，答案就又会变得正确，所以，我们递归处理这个问题，当有重复的区间，令 $L=t,R=s$ 继续计算，每次答案都异或上 $f_{L,x}$ 和 $f_{t,x}$。但是，这样下去，递归就会无穷无尽，因此，我们需要找到一个边界条件。

第一种边界条件：

即 $t$ 恰好等于 $s+1$，恰好把 $[L,R]$ 区间覆盖完，没有重复的，当出现这种情况的时候，更新完 $ans$，就可以 $return$ 了。

第二种边界条件：

这一层递归结束，$L=t$，$R=s$， $L$ 恰好等于 $R$，当出现这种情况的时候，直接异或一次重复的那个元素 ($a_L$)，就可以结束递归了。

4、代码

综上所述，这就是ST表解决区间 $xor$ 问题的几个步骤，下面放详细代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[300005],st[300005][35],i,j,m,x,y,ans,op[300005],w1,w2;
char ch;
//快速读入，一般问题的数据量都很大
ll read(){
	w1=0,w2=1;ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') w2=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') w1=w1*10+ch-'0',ch=getchar();
	return w1*w2;
}
//此处用循环代替递归，减少栈空间消耗
void cmp(ll l,ll r){
	while(1){
		if(l==r){
			ans^=st[l][0];     //第二种边界情况
			return;
		}
		//x直接赋值，不用计算log
		ll x = op[r-l+1],s = l+(1<<x)-1,t = r-(1<<x)+1;     //求出x,s,t
		if(t-s==1){                    //第一种边界情况
			ans=ans^st[l][x]^st[t][x];
			return ;
		}
		else{
			ans=ans^st[l][x]^st[t][x];    //其它情况，继续循环
			l=t,r=s;
		}
	}
}
int main(){
	n=read(),m=read();
	for(i=1;i<=n;i++) a[i]=read();
	//普通ST表处理步骤
	for(i=n;i>=1;i--){
		st[i][0] = a[i];
		for(j=1;i+(1<<j)-1<=n;j++){
			st[i][j]=st[i][j-1]^st[i+(1<<(j-1))][j-1];
		}
	}
	j=1;
	//处理长度为len的区间，x至少是多少
	for(i=1;i<=n;i++){
	op[i] = op[i-1];
	    for(;j*2<i;j*=2,op[i]++);
	}
	while(m--){
		ans=0;         //记得初始化
		x=read(),y=read();
		cmp(x,y);
		printf("%lld\n",ans);
	}
}

$problem：$ 快速区间xor

4、一些扩展

这种ST表不仅可以解决区间 $xor$ 问题，还可以解决区间和，只不过呢，要多一个参数，表示当前应该减去 $f_{i,j}$，还是加上 $f_{i,j}$，同样的，边界条件也是只有那两种情况。

void cmp(ll l,ll r){
	ll p = 0;    //当标记为0，表示加；当标记为1，表示减
	while(1){
		if(l==r){
			if(p==0) ans+=st[l][0];     //第二种边界情况
			else ans-=st[l][0];
			return;
		}
		//x直接赋值，不用计算log
		ll x = op[r-l+1],s = l+(1<<x)-1,t = r-(1<<x)+1;     //求出x,s,t
		if(t-s==1){                    //第一种边界情况
			if(p==0) ans=ans+st[l][x]+st[t][x];
			else ans=ans-st[l][x]-st[t][x];
			return ;
		}
		else{
			if(p==0) ans=ans+st[l][x]+st[t][x];
			else ans=ans-st[l][x]-st[t][x];
			l=t,r=s;
		}
		p=(p+1)%2;    //标记
	}
}

5、时间复杂度

这种ST表由于是用循环处理每个询问，所以时间复杂度不是 $O(1)$，假设当前区间长度为 $n$，那么递归下一层有三种情况：
$$n=\{\begin{array}{r}return(n=1)\\ return(n=2^x)\\ n=2^x-n(Other)\end{array}$$
其中，保证 $2^x$ 最接近 $n$，公式中不难看出，整个算法时间复杂度最坏情况下 $O(nlogn)$，最好情况 $O(1)$ 搞定。
实践证明，在 $1$ 到 $1\times 10^6$ 中，只有四个数的递归次数达到了 $O(nlogn)$ 的时间复杂度：$524287,786431,917503,983039$，有超过 $\%60$ 的数的递归次数小于 $10$ 次，超过 $\%99$ 的数递归次数小于 $15$ 次。而且这种算法常数很小，几乎为 $1$，综上所述，总的时间复杂度为最好：$O(nlogn+n+m)$；最坏：$O(nlogn+n+mlogn)$，在随机数据中时间快得飞起。

此处附上验证代码：

#include<bits/stdc++.h>
using namespace std;
long long dp[1000005],i,j,ans;
int main(){
	for(i=1;i<=1000000;i++) dp[i]=1e13;  //赋初值
	dp[1] = ans = 1;       //n=1
	for(i=2;i<=1000000;i++){
		for(j=0;(1ll<<j)<=i;j++){
			if((1ll<<j)==i) dp[i]=1;       //n=2^x
		}
		for(j=0;i+(1ll<<j)<=1000000;j++) dp[i+(1ll<<j)]=min(dp[i+(1ll<<j)],dp[i]+1);
		//状态转移
		ans=max(ans,dp[i]);     //记录
	}
	cout<<ans;
}

6、后记

虽然这种ST表可以解决区间不可重复贡献问题，但是，依然逃脱不了ST表的本质：

1、不可修改
2、以倍增为基础框架

同时，这种方法由于不可修改的限制，在有修改的问题上，不如线段树灵活；另外一些没有修改问题上，比线段树又要快。

总而言之，各种数据结构都各有各的优点和缺点，我们需要掌握每种数据结构，才能在赛场上应对自如，得心应手。今天介绍的解决区间不可重复贡献问题的ST表就到这了，如果觉得好的话，就留下你宝贵的赞吧；相反，如果觉得不好，欢迎提出更多意见！