分桶法(bucketmethod)是把一排物品或者平面分成桶，每个桶分别维护自己内部的信息，以达到高效计算的目的的方法。
其中，平方分割(sqrtdecomposition)是把排成一排的n个元素每根号n个分在一个桶内进行维护的方法的统称。这样的分割方法可以使对区间的操作的复杂度降至O(根号n)。
和线段树一样，根据维护的数据不同，平方分割可以支持很多不同的操作。接下来，和线段树一样，我们以RMQ为例对平方分割进行详解。
1. 基于平方分割的RMQ
给定一个数列a1,a2,…,an,目标是在O(根号n)复杂度内实现两个功能
*给定s，t，求as,as+1,…,at的最小值
*给定t, x,把ai的值变为x。
2.基于平方分割RMQ的预处理
令b=floor(根号n),把a中的元素每b分成一个桶，并且计算出每个桶内的最小值。
3.基于平方分割的RMQ的查询
如下图所示，查询
*如果桶完全包含在区间内，则查询桶的最小值
*如果元素所在的桶不完全被区间包含，则逐个检查最小值
他们的最小值就是区间的最小值了。
4.基于平方分割的RMQ的值的更新
在更新元素的值时，需要更新该元素所在的桶的最小值。这时只要遍历一遍桶内的元素就可以了。
5.平方分割和线段树
因此，在平方分割中，对于任意区间，完全包含于其中的桶的数量和剩余元素的数量都是O(根号n)，所以可以在O(根号n)时间内完成各种操作。
在上面的RMQ的例题中，线段树进行各种操作的复杂度是O(logn)，比平方分割更快一些。一般地，如果线段树和平方分割都能实现某个功能，多数情况下线段树会比平方分割快。但是，因为平方分割在实现上比线段树简单，所以如果运行时间限制不是太紧时，也可以考虑使用平方分割。除此之外，也有一些功能是线段树无法高效维护但是平方分割却可以做到的。
实践：求区间第k小的问题。即长度为n无序的数列，m次询问l到r之间第k小的数。
思想：
代码：
1 #include 2 #define il inline 3 #pragma GCC optimize(2) 4 #define debug printf("%d %s\n",__LINE__,__FUNCTION__) 5 using namespace std; 6 const int N=100005,M=1000; 7 il int gi() 8 { 9 int a=0;char x=getchar();bool f=0;10 while((x<'0'||x>'9')&&x!='-')x=getchar();11 if(x=='-')x=getchar(),f=1;12 while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();13 return f?-a:a;14 }15 int n,m,val[N],num[N];16 vector<int>kuai[N/M];17 il int muodui(int k,int l,int r)18 {19 int left=-1,right=n-1,mid;20 while(left+1<right){21 mid=left+right>>1;22 int x=num[mid],rel=l-1,rer=r,c=0;23 while(rel<rer&&rel%M){if(val[rel++]<=x)c++;}24 while(rel<rer&&rer%M){if(val[--rer]<=x)c++;}25 while(rel<rer){26 int p=rel/M;27 c+=upper_bound(kuai[p].begin(),kuai[p].end(),x)-kuai[p].begin();28 rel+=M;29 }30 if(c>=k)right=mid;31 else left=mid;32 }33 return num[right];34 }35 int main()36 {37 freopen("treasure.in","r",stdin);38 freopen("treasure.out","w",stdout);39 n=gi(),m=gi();40 for(int i=����,����0;i<n;i++)val[i]=gi(),num[i]=val[i],kuai[i/M].push_back(val[i]);41 sort(num,num+n);42 for(int i=0;i<n/M;i++)43 sort(kuai[i].begin(),kuai[i].end());44 int l,r,k;45 while(m--)46 {47 l=gi(),r=gi(),k=gi();48 printf("%d\n",muodui(k,l,r));49 }50 return 0;51 }