ST表
ST算法（Sparse Table）：
它是一种动态规划的方法。以最小值为例。a为所寻找的数组，用一个二维数组
f(i,j)记录区间[i, i+2^j-1]区间中的最小值。其中f[i,0] = a[i];所以，对于任意
的一组(i,j)，f(i,j) = min{f(i,j-1),f(i+2^(j-1),j-1)}来使用动态规划计算出来。
这个算法的高明之处不是在于这个动态规划的建立，而是它的查询：它的查询效
率是O(1)！如果不细想的话，怎么弄也是不会想到有O（1）的算法的。假设我们要求
区间[m,n]中a的最小值，找到一个数k使得2^k<n-m+1，即k=[ln(b-a+1)/ln(2)] 这样，
可以把这个区间分成两个部分：[m,m+2^k-1]和[n-2^k+1,n]！我们发现，这两个区间
是已经初始化好的！前面的区间是f(m,k)，后面的区间是f(n-2^k+1,k)！这样，只要
看这两个区间的最小值，就可以知道整个区间的最小值！
小结：
稀疏表(SparseTable)算法是O(nlogn)-O(1)的，对于查询很多大的情况下比较好。
ST算法预处理：用dp[i,j]表示从i开始的，长度为2^j 的区间的RMQ，则有递推式
dp[i,j]=min{dp[i,j-1],dp[i+2j-1,j-1]}
即用两个相邻的长度为2j-1的块，更新长度为2j的块。因此，预处理时间复杂度为O(nlogn)。
这个算法记录了所有长度形如2k的所有询问的结果。
从这里可以看出，稀疏表算法的空间复杂度为 O(nlogn)。
模板如下：
#include <iostream>
#include <cmath>
using namespace std;
int a[50001];
int f[50001][16];
int n;
void rmq_init() //建立： dp(i,j) = min{dp(i,j-1),dp(i+2^(j-1),j-1) O(nlogn)
{
for(int i=1; i<=n; i++)
f[i][0] = a[i];
int k=floor(log((double)n)/log(2.0)); //C/C++取整函数ceil()大,floor()小
for(int j=1; j<=k; j++)
for(int i=n; i>=1; i--)
{
if(i+(1<<(j-1))<=n) //f(i,j) = min{f(i,j-1),f(i+2^(j-1),j-1)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
int rmq(int i,int j) //查询：返回区间[i,j]的最小值 O(1)
{
int k = floor(log((double)(j-i+1))/log(2.0));
return min(f[i][k],f[j-(1<<k)+1][k]);
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
rmq_init();
printf("%d\n", rmq(2,5));
}
- poj 3264 Balanced Lineup
题意：求区间的最大值和最小值。
这道题有很多种方法（比如线段树），用ST表代码简洁，详细代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 100005
using namespace std;
int n,q,a[N];
int mx[N][18],mn[N][18];
void Rmq_Init(){
int m=floor(log((double)n)/log(2.0));
for(int i=1;i<=n;i++) mx[i][0]=mn[i][0]=a[i];
for(int i=1;i<=m;i++)
for(int j=n;j;j--){
mx[j][i]=mx[j][i-1];
mn[j][i]=mn[j][i-1];
if(j+(1<<(i-1))<=n){
mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);
mn[j][i]=min(mn[j][i],mn[j+(1<<(i-1))][i-1]);
}
}
}
int Rmq_Query(int l,int r){
int m=floor(log((double)(r-l+1))/log(2.0));
int Max=max(mx[l][m],mx[r-(1<<m)+1][m]);
int Min=min(mn[l][m],mn[r-(1<<m)+1][m]);
return Max-Min;
}
int main(){
while(scanf("%d%d",&n,&q)!=EOF){
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
Rmq_Init();
while(q--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",Rmq_Query(l,r));
}
}
return 0;
}
划分树
划分树是一种基于线段树的数据结构。主要用于快速求出(在log(n)的时间复杂度内）序列区间的第k大值。
查找整序列的第k大值往往采用。然而此方法会破坏原序列，并且需要O(n)的时间复杂度。抑或使用二叉平衡树进行维护，此方法每次查找时间复杂度仅为O(logn)。然而此方法丢失了原序列的顺序信息，无法查找出某区间内的第k大值。
划分树的基本思想就是对于某个区间，把它划分成两个子区间，左边区间的数小于右边区间的数。查找的时候通过记录进入左子树的数的个数，确定下一个查找区间，最后范围缩小到1，就找到了。
划分树定义为，它的每一个节点保存区间[lft,rht]所有元素，元素顺序与原数组（输入）相同，但是，两个子树的元素为该节点所有元素排序后(rht-lft+1)/2个进入左子树，其余的到右子树，同时维护一个num域，num[i]表示lft->i这个点有多少个进入了左子树。
如果由下而上看这个图，我们就会发现它和归并排序的（归并树）的过程很类似，或者说正好相反。归并树是由下而上的排序，而它确实是由上而下的排序，但这正是它可以用来解决第k大元素的理由所在。
划分树的存储结构（采用层次存储结构（由下而上，由左到右，每层两个孩子，见上图））
constint N=1e5+5;
int sorted[N]; //对原来集合中的元素排序后的值
struct node
{
int valu[N]; //val记录第k层当前位置元素的值
int num[N]; //num记录元素所在区间的当前位置之前进入左孩子的个数
LL sum[N]; //sum记录比当前元素小的元素的和
}t[20];
划分树的建立
划分树的建立和普通的二叉树的建立过程差不多，仍然采取中序的过程（先根节点，然后左右孩子）。
树的建立相对比较简单，我们依据的是已经排好序的位置进行建树，所以先用快排将原集合还序。要维护每个节点的num域。
void build(int lft,int rht,int ind)
{
if(lft==rht) return;
int mid=MID(lft,rht);
int same=mid-lft+1,ln=lft,rn=mid+1;
for(int i=lft;i<=rht;i++)
if(valu[ind][i]<order[mid]) same--;
for(int i=lft;i<=rht;i++)
{
int flag=0;
if((valu[ind][i]<order[mid])||valu[ind][i]==order[mid]&&same>0)
{
flag=1;
valu[ind+1][ln++]=valu[ind][i];
if(valu[ind][i]==order[mid]) same--;
lsum[ind][i]=lsum[ind][i-1]+valu[ind][i];
}
else
{
lsum[ind][i]=lsum[ind][i-1];
valu[ind+1][rn++]=valu[ind][i];
}
toLft[ind][i]=toLft[ind][i-1]+flag;
}
build(lft,mid,ind+1);
build(mid+1,rht,ind+1);
}
划分树的查找
在区间[a,b]上查找第k大的元素，同时返回它的位置和区间小于[a,b]的所有数的和 。
1.如果t[p].num[b]-t[p].num[a-1]>=k，即，进入左孩子的个数已经超过k个，那么就往左孩子里面查找，同时更新[a,b]=>[lft+t[p].num[a-1]，lft+t[p].num[b]-1]
2.如果t[p].num[b]-t[p].num[a-1]<k，即，进入p的左孩子的个数小于k个，那么就要往右孩子查找第k-s(s表示进入左孩子的个数)个元素。同时更新sum域，因而这样求出的sum只是严格小于在[a,b]区间中第k大的数的和。
int query(int st,int ed,int k,int lft,int rht,int ind)
{
if(lft==rht) return valu[ind][lft];
/*
lx表示从lft到st-1这段区间内有多少个数进入左子树
ly表示从st到ed这段区间内有多少个数进入左子树
rx表示从lft到st-1这段区间内有多少个数进入右子树
ry表示从st到ed这段区间内有多少个数进入右子树
*/
int mid=MID(lft,rht);
int lx=toLft[ind][st-1]-toLft[ind][lft-1];
int ly=toLft[ind][ed]-toLft[ind][st-1];
int rx=st-1-lft+1-lx;
int ry=ed-st+1-ly;
if(ly>=k) return query(lft+lx,lft+lx+ly-1,k,lft,mid,ind+1);
else
{
isum+=lsum[ind][ed]-lsum[ind][st-1];
st=mid+1+rx;
ed=mid+1+rx+ry-1;
return query(st,ed,k-ly,mid+1,rht,ind+1);
}
}
题意：有n个数字排成一列，有m个询问，格式为：left right k 即问在区间[left,right]第k大的数据为多少？
直接用划分树的模板即可。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MID(a,b) (a+((b-a)>>1))
typedef long long LL;
const int N=1e5+5;
struct P_Tree
{
int n,order[N];
int valu[20][N],num[20][N];
LL sum[N],lsum[20][N],isum;
void init(int len)
{
n=len; sum[0]=0;
for(int i=0;i<20;i++) valu[i][0]=0,num[i][0]=0,lsum[i][0]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&order[i]);
valu[0][i]=order[i];
sum[i]=sum[i-1]+order[i];
}
sort(order+1,order+1+n);
build(1,n,0);
}
void build(int lft,int rht,int ind)
{
if(lft==rht) return;
int mid=MID(lft,rht);
int same=mid-lft+1,ln=lft,rn=mid+1;
for(int i=lft;i<=rht;i++)
if(valu[ind][i]<order[mid]) same--;
for(int i=lft;i<=rht;i++)
{
int flag=0;
if((valu[ind][i]<order[mid])||(valu[ind][i]==order[mid]&&same))
{
flag=1;
valu[ind+1][ln++]=valu[ind][i];
lsum[ind][i]=lsum[ind][i-1]+valu[ind][i];
if(valu[ind][i]==order[mid]) same--;
}
else
{
valu[ind+1][rn++]=valu[ind][i];
lsum[ind][i]=lsum[ind][i-1];
}
num[ind][i]=num[ind][i-1]+flag;
}
build(lft,mid,ind+1);
build(mid+1,rht,ind+1);
}
int query(int st,int ed,int k,int lft,int rht,int ind)
{
if(lft==rht) return valu[ind][lft];
int mid=MID(lft,rht);
int lx=num[ind][st-1]-num[ind][lft-1];
int ly=num[ind][ed]-num[ind][st-1];
int rx=st-1-lft+1-lx;
int ry=ed-st+1-ly;
if(ly>=k) return query(lft+lx,lft+lx+ly-1,k,lft,mid,ind+1);
else
{
isum+=lsum[ind][ed]-lsum[ind][st-1];
st=mid+1+rx;
ed=mid+1+rx+ry-1;
return query(st,ed,k-ly,mid+1,rht,ind+1);
}
}
}tree;
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
tree.init(n);
for(int i=0;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
int res=tree.query(a,b,c,1,n,0);
printf("%d\n",res);
}
}
return 0;
}