poj 2104 2761 树状数据结构
2011年10月07日 00:51
两道题都是裸裸的求区间第k大数(kth number)，先给出总的区间，每个查询给出小区间[l，r]和k。
用这两道题学习了不少数据结构，感觉有些非常巧妙，记录一下。
1 平衡树
平衡树就是平衡的二叉搜索树(BST)，对每个区间建立平衡树并维护size域(以此节点为根的树的节点数)，便可很容易的实现select(找第k大数)和rank(查某数是第几大)两个操作。因为要反复针对区间建树，所以先对区间排好序会比较好，这样后一个区间的树就是对前一个区间的树的增删操作了。
1.1 Treap
Tree就是Tree(BST)+Heap。 首先要满足BST的性质，节点的key要左小于中小于右。然后每个节点加上了一个附加域fix，这个域没什么意义，就是个随机数，但是需要保持树上的这个域符合堆的性质，比如最小堆，中小于左右。 怎么能又保持BST又保持Heap呢？这就要靠一个神奇的BST的操作了！BST中的左旋和右旋是不会破坏BST的性质的！于是先保证树是BST，再用左旋和右旋把整棵树调整成Heap。于是就可以看到添加节点时，先加到最下面，然后，扭啊扭啊扭上去，删除时把节点扭啊扭啊扭下去再删掉~ 显然，fix和堆的存在就是为了搅乱整棵树的，这样就不会对特定的数据恶化了。而且扭的过程中还可以降低树的高度，所以Treap是随机平衡的树，各操作均摊复杂度才是O(nlogn)，不像AVL和红黑树那样是近似绝对平衡的树。但是Treap编程难度低啊，所以很好用，我觉得，这个把BST和Heap结合起来的扭来扭去的树和Dancing links一样优美~ 对size域的维护放到旋转时就可以了。具体资料可见《随机平衡二叉查找树 Treap 的分析与应用 by 郭家宝》。
#include <cstdio>
#include <cstdlib>
#define nil 0
#define MAX 1000010
int key[MAX],left[MAX],right[MAX],size[MAX],fix[MAX];
int root,node;
inline void Left_Rotate(int &x) {
int k = right[x];
right[x] = left[k];
left[k] = x;
size[k] = size[x];
size[x] = size[left[x]] + size[right[x]] + 1;
x = k;
}
inline void Right_Rotate(int &y) {
int k = left[y];
left[y] = right[k];
right[k] = y;
size[k] = size[y];
size[y] = size[left[y]] + size[right[y]] + 1;
y = k;
}
void Insert(int &T,int v) {
if(T == nil) {
key[T = ++node]= v;
fix[T]=rand(); size[T]=1;
} else {
size[T]++;
if(v < key[T]) {
Insert(left[T], v);
if(fix[left[T]]<fix[T])
Right_Rotate(T);
} else {
Insert(right[T], v);
if(fix[right[T]]<fix[T])
Left_Rotate(T);
}
}
}
void Delete(int &T,int v) {
if(!T) return;
size[T]--;
if(v == key[T]){
if(!left[T] || !right[T])
T=left[T]+right[T];
else if(fix[left[T]]<fix[right[T]]) {
Right_Rotate(T);
Delete(right[T],v);
} else {
Left_Rotate(T);
Delete(left[T],v);
}
} else if (v < key[T])
Delete(left[T],v);
else
Delete(right[T],v);
}
int Select(int &T,int k)
{
int r = size[left[T]] + 1;
if(k == r)
return key[T];
else if(k < r)
return Select(left[T], k);
else
return Select(right[T], k - r);
}
int arr[100010];
typedef struct {int l,r,k,org;} Q;
Q q[50010];
int ans[50010];
int cmp(const void *a,const void *b)
{
Q *qa=(Q*)a,*qb=(Q*)b;
if(qa->l!=qb->l) return qa->l-qb->l;
else return qa->r-qb->r;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
//init
//srand(1984);
root=0;
int n,m; scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",arr+i);
for(int i=1;i<=m;i++)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
q[i].l=l; q[i].r=r; q[i].k=k; q[i].org=i;
}
qsort(q+1,m,sizeof(Q),cmp);
int lastl=1,lastr=0;
for(int t=1;t<=m;t++)
{
int l=q[t].l,r=q[t].r,k=q[t].k;
if(lastr<l)
{
for(int i=lastl;i<=lastr;i++)
Delete(root,arr[i]);
for(int i=l;i<=r;i++)
Insert(root,arr[i]);
}
else if(lastr<=r)
{
for(int i=lastl;i<l;i++)
Delete(root,arr[i]);
for(int i=lastr+1;i<=r;i++)
Insert(root,arr[i]);
}
else
{
for(int i=lastl;i<l;i++)
Delete(root,arr[i]);
for(int i=r+1;i<=lastr;i++)
Delete(root,arr[i]);
}
lastl=l;lastr=r;
ans[q[t].org]=Select(root,k);
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
1.2 Splay
Splay和Treap很像，也是扭来扭去的。Splay树的独特之处就是splay操作，把某一个节点扭到root处，在扭的过程中同样可以搅乱整棵树，降低树高。Splay操作也仅仅是用单旋和双旋两种操作，应对节点和节点父亲及节点的父亲的父亲之间的多种情况，快速的把节点向上提升。 Splay树中的插入操作是在普通BST插入操作后，把插入节点splay到根。删除操作有多种实现，我是先把要删除节点splay到根，再把左子树中最大的节点splay到根，然后，其右节点即为要删除的节点，而此时他只有右子树了，所以很容易就删除了。Splay也是随机的平衡树，可以证明的是splay操作均摊复杂度为O(1)，所以各操作的均摊复杂度为O(nlogn)了。size域的维护在单旋和删除操作时维护即可。资料参见《伸展树的基本操作与应用 by 杨思雨》、《伸展树操作详解 By Ma Shuo》和《The Magical Splay by sqybi》。
#include <cstdio>
#include <cstdlib>
struct Node
{
Node *pre,*ch[2]; int size,key;
Node(){pre=ch[0]=ch[1]=NULL;size=1;}
} node[1000100];
int tot=0;
Node *root;
void print(Node *x)
{
if(!x) return;
print(x->ch[0]);
printf("%d ",x->key);
print(x->ch[1]);
}
void Rotate(Node *x)
{
bool c=(x->pre->ch[0]==x);//0:left(zag) 1:right(zig)
Node *y=x->pre;
y->ch[!c]=x->ch[c];
if(x->ch[c]!=NULL) x->ch[c]->pre=y;
x->pre = y->pre;
if(y->pre!=NULL)
y->pre->ch[y->pre->ch[0]!=y]=x;
x->ch[c]=y; y->pre=x;
x->size=y->size; y->size=1;
for(int i=0;i<2;i++)
if(y->ch[i]) y->size+=y->ch[i]->size;
if(y==root) root=x;
}
// up x until x->pre = f, f==NULL means root
void Splay(Node *x,Node *f=NULL)
{
while(x->pre!=f)
if(x->pre->pre==f)
Rotate(x);
else
{
Node *y=x->pre,*z=y->pre;
if((z->ch[0]==y)==(y->ch[0]==x))
Rotate(y), Rotate(x);
else
Rotate(x), Rotate(x);
}
if(f==NULL) root=x;
}
Node* Search(Node *x,int k)//return the last found
{
if(!x) return NULL;
while(k != x->key)
{
bool c=(k > x->key);
if(x->ch[c]==NULL) break;
x=x->ch[c];
}
return x;
}
void Insert(int k)
{
Node *x=root,*y=NULL;
while(x)// && k != x->key)
{
x->size++;
y=x; x=x->ch[k > x->key];
}
Node *z=&node[tot++]; z->key=k;
z->pre=y;
if(y==NULL)
root=z;
else
y->ch[k > y->key]=z;
Splay(z);
}
Node* Extreme(Node *x,bool c)
{
while(x && x->ch[c]!=NULL)
x=x->ch[c];
return x;
}
bool Delete(int k)
{
Node *x=Search(root,k);
if(!x || x->key!=k) return false;
Splay(x);//make x the root
if(!x->ch[0] || !x->ch[1])// one or none child
{
bool c=(x->ch[0])?0:1;
if(x->ch[c]) x->ch[c]->pre=NULL;
root=x->ch[c];
}
else //combine x's childs
{
Node *l=x->ch[0],*r=x->ch[1];
Splay(Extreme(l,1));
root->ch[1]=r; r->pre=root;
root->size--;
}
//delete(x);
return true;
}
int Select(Node *x,int k)
{
int r=1+((x->ch[0])?x->ch[0]->size:0);
if(k==r)
return x->key;
else if(k < r)
return Select(x->ch[0],k);
else
return Select(x->ch[1],k-r);
}
int arr[1000500];
struct Q{int l,r,k,org;} q[50050];
int ans[50050];
int cmp(const void *a,const void *b)
{
Q *qa=(Q*)a,*qb=(Q*)b;
if(qa->l!=qb->l) return qa->l-qb->l;
else return qa->r-qb->r;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
int n,m; scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",arr+i);
for(int i=1;i<=m;i++)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
q[i].l=l; q[i].r=r; q[i].k=k; q[i].org=i;
}
qsort(q+1,m,sizeof(Q),cmp);
int lastl=1,lastr=0;
for(int t=1;t<=m;t++)
{
int l=q[t].l,r=q[t].r,k=q[t].k;
if(lastr<l)
{
for(int i=lastl;i<=lastr;i++)
Delete(arr[i]);
for(int i=l;i<=r;i++)
Insert(arr[i]);
}
else if(lastr<r)
{
for(int i=lastl;i<l;i++)
Delete(arr[i]);
for(int i=lastr+1;i<=r;i++)
Insert(arr[i]);
}
else
{
for(int i=lastl;i<l;i++)
Delete(arr[i]);
for(int i=r+1;i<=lastr;i++)
Delete(arr[i]);
}
lastl=l;lastr=r;
ans[q[t].org]=Select(root,k);
//printf("l:%d r:%d k:%d :: ",l,r,k);
//print(root);puts("");
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
1.3 SBT（Size Balanced Tree）
名字大亮，"傻叉树" or "Super BT"树。如其本名，是直接用size域实现近似绝对平衡的树。较复杂，不介绍了，参见《Size Balanced Tree by Chen Qifeng(此树作者)》、《由二叉查找树到容均树 by 田劲锋》（写的大好啊，我就是用这个里面的代码做模板的）。
#include <cstdio>
#include <cstdlib>
int arr[100010];
typedef struct {int l,r,k,org;} Q;
Q q[50100];
int ans[50100];
#define nil 0
const int MAX = 100010;
int key[MAX], left[MAX], right[MAX], size[MAX];
int T, node;
int record; // This is used for the commented Delete
inline void Left_Rotate(int &x) {
int k = right[x];
right[x] = left[k];
left[k] = x;
size[k] = size[x];
size[x] = size[left[x]] + size[right[x]] + 1;
x = k;
}
inline void Right_Rotate(int &y) {
int k = left[y];
left[y] = right[k];
right[k] = y;
size[k] = size[y];
size[y] = size[left[y]] + size[right[y]] + 1;
y = k;
}
void Maintain(int &T, bool flag);
void Insert(int &T, int v) {
if(T == nil) {
key[T = ++node] = v;
size[T] = 1;
} else {
size[T]++;
if(v < key[T])
Insert(left[T], v);
else
Insert(right[T], v);
Maintain(T, v >= key[T]);
}
}
int Delete(int &T, int v) {
size[T]--;
if( (v == key[T]) || (v < key[T] && left[T] == nil) || (v > key
[T] && right[T] == nil) ) {
int r = key[T];
if(left[T] == nil || right[T] == nil)
T = left[T] + right[T];
else
key[T] = Delete(left[T], key[T] + 1);
return r;
} else {
if(v < key[T])
return Delete(left[T], v);
else
return Delete(right[T], v);
}
}
void Maintain(int &T, bool flag) {
if(flag == false) {
if(size[left[left[T]]] > size[right[T]])
Right_Rotate(T);
else {
if(size[right[left[T]]] > size[right[T]]) {
Left_Rotate(left[T]);
Right_Rotate(T);
} else return;
}
} else {
if(size[right[right[T]]] > size[left[T]])
Left_Rotate(T);
else {
if(size[left[right[T]]] > size[left[T]]) {
Right_Rotate(right[T]);
Left_Rotate(T);
} else return;
}
}
Maintain(left[T], false);
Maintain(right[T], true);
Maintain(T, true);
Maintain(T, false);
}
int Select(int T, int k) {
int r = size[left[T]] + 1;
if(k == r)
return key[T];
else if(k < r)
return Select(left[T], k);
else
return Select(right[T], k - r);
}
int cmp(const void *a,const void *b)
{
Q *qa=(Q*)a,*qb=(Q*)b;
if(qa->l!=qb->l) return qa->l-qb->l;
else return qa->r-qb->r;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
int n,m,lastl=1,lastr=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",arr+i);
//sort query
for(int i=1;i<=m;i++)
{
int l,r,k; scanf("%d%d%d",&l,&r,&k);
q[i].l=l; q[i].r=r; q[i].k=k; q[i].org=i;
}
qsort(q+1,m,sizeof(Q),cmp);
//do
for(int t=1;t<=m;t++)
{
int l=q[t].l,r=q[t].r,k=q[t].k;
if(lastr<l)
{
for(int i=lastl;i<=lastr;i++)
Delete(T,arr[i]);
for(int i=l;i<=r;i++)
Insert(T,arr[i]);
}
else if(lastr<=r)
{
for(int i=lastl;i<l;i++)
Delete(T,arr[i]);
for(int i=lastr+1;i<=r;i++)
Insert(T,arr[i]);
}
else
{
for(int i=lastl;i<l;i++)
Delete(T,arr[i]);
for(int i=r+1;i<=lastr;i++)
Delete(T,arr[i]);
}
lastl=l;lastr=r;
ans[q[t].org]=Select(T,k);
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
2 线段树
wr大牛说线段树也是一种平衡树，不过至少在这个问题的应用上还是有很大区别的。线段树的解法不再是构造每个查询区间的树了，而是构造好整个区间的（线段）树，再从上到下查询。
2.1 划分树
据说是专门用来解决kth number问题的。划分树的原理基于快排，线段树的每一层都是快排的一级，最上层就是整个数组，从上往下建立。为了保持绝对平衡，使用中位数做支点，左右平均，所以左右两边可能有相同的元素，在建树时要注意。建树时同时建立好num_left数组，记录每个线段树节点的区间中，在其左侧小于等于某元素的元素数。整个查找过程是从上到下分析num_left并选择向左还是向右的过程。具体参见这里。
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define max 1000010
struct Tree { int l,r; } tree[max*3];
int leftsum[30][max],seg[30][max],arr[max];
void parti_build(int r,int s,int t,int d)
{
tree[r].l=s;tree[r].r=t;
if(t==s) return;
int mid=(s+t)>>1;
int lsame=mid-s+1;
for(int i=s;i<=t;i++)
if(seg[d][i]<arr[mid])
lsame--;
int lpos=s,rpos=mid+1;
for(int i=s;i<=t;i++)
{
leftsum[d][i] = (i==s)?0:leftsum[d][i-1];
if(seg[d][i]<arr[mid])
{
leftsum[d][i]++;
seg[d+1][lpos++]=seg[d][i];
}
else if(seg[d][i]>arr[mid])
seg[d+1][rpos++]=seg[d][i];
else
{
if(lsame)
{
lsame--; leftsum[d][i]++;
seg[d+1][lpos++]=seg[d][i];
}
else
seg[d+1][rpos++]=seg[d][i];
}
}
parti_build(r*2,s,mid,d+1);
parti_build(r*2+1,mid+1,t,d+1);
}
int find(int r,int s,int t,int d,int k)
{
int tl=tree[r].l,tr=tree[r].r;
if(tr==tl) return seg[d][s];
int s_left_sum=(s==tl)?0:leftsum[d][s-1];
int s_to_t_sum=leftsum[d][t]-s_left_sum;
if(s_to_t_sum >=k)
return find(r*2,tl+s_left_sum,tl+leftsum[d][t]-1,d+1,k);
else
{
int mid=(tl+tr)>>1;
int s_right_sum=s-tl-s_left_sum;
int s_to_t_r_sum=t-s+1-s_to_t_sum;
return find(r*2+1,mid+s_right_sum+1,mid+s_right_sum+s_to_t_r_sum,d+1,k-s_to_t_sum);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",arr+i);
seg[1][i]=arr[i];
}
sort(arr+1,arr+1+n);
parti_build(1,1,n,1);
while(m--)
{
int s,t,k;
scanf("%d%d%d",&s,&t,&k);
printf("%d\n",find(1,s,t,1,k));
}
}
2.2 归并树
和划分树不同,归并树用的是归并排序的思想，每一层都是归并排序的一级，从下到上构建，每一个节点区间内都是排好序的（和划分树不同）。线段树是用来查某数的rank的，比较典型的线段树查询操作，不用附加域，而是用二分的思想，因为节点区间内都是排好序的，注意因为有重复值的可能所以二分求的是区间内小于某数的数的个数。对每个查询的结果是用其在所给小区间rank值二分的，注意二分是求使rank值为k的最大的数，原因不太好想。介绍可看这里，代码可看这里。
#include <cstdio>
#include <cstdlib>
#define MAX 1000010
struct Tree {int l,r,lev;} tree[MAX*3];
int seg[22][MAX];
int n,m;
int arr[MAX],max,min;
void build(int root,int lev,int l,int r)
{
tree[root].l=l;tree[root].r=r;tree[root].lev=lev;
if(l==r)
{
seg[lev][l]=arr[l];
return;
}
int mid=(l+r)/2;
build(root*2,lev+1,l,mid);
build(root*2+1,lev+1,mid+1,r);
int p=l,p1=l,p2=mid+1;
while(p<=r)
{
if(p1>mid)
seg[lev][p++]=seg[lev+1][p2++];
else if(p2>r)
seg[lev][p++]=seg[lev+1][p1++];
else if(seg[lev+1][p1]<=seg[lev+1][p2])
seg[lev][p++]=seg[lev+1][p1++];
else
seg[lev][p++]=seg[lev+1][p2++];
}
}
//the count in a that a[i]<x
int count(int *a,int l,int r,int x)
{
int m,orgl=l;
if(a[l]>=x) return 0;
else if(a[r]<x) return r-l+1;
while(l+1<r) //assert: a[l]<x && x<=a[r]
{
m=(l+r)>>1;
if(a[m]<x) l=m; else r=m;
}
return l-orgl+1;
}
int rank(int root,int l,int r,int x)
{
if(tree[root].l==l && tree[root].r==r)
return count(seg[tree[root].lev],l,r,x);
int mid=(tree[root].l+tree[root].r)/2;
if(r<=mid)
return rank(root*2,l,r,x);
else if(l>mid)
return rank(root*2+1,l,r,x);
else
return rank(root*2,l,mid,x)+
rank(root*2+1,mid+1,r,x);
}
int query(int l,int r,int k)
{
int s=seg[1][0],t=seg[1][n-1]+1,m;
while(s+1<t) // [s,t) <= ans
{
m=(s+t)/2;
int rk=rank(1,l,r,m)+1;
if(rk>k) t=m;
else s=m;
}
return s;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",arr+i);
build(1,1,0,n-1);
int l,r,k;
while(m--)
{
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",query(l-1,r-1,k));
}
}
