首页 > 代码库 > 【块状链表】AutSky_JadeK的块状链表模板+总结(STL版)
【块状链表】AutSky_JadeK的块状链表模板+总结(STL版)
Part 1、块状链表。
| 定位 | 插入 | 删除 | |
| 数组 | O(1) | O(n) | O(n) |
| 链表 | O(n) | O(1) | O(1) |
对于线性表的以上常见操作来说，数组和链表都无法有效地解决。但是，若我们将链表的每个节点存成一个数组，使得链表里每个节点的数据拼接起来就是原先的线性表中的内容(即块状链表)，并且数组的大小合适的话，以上的操作都能比较好地解决了。根据均值不等式，若每个块的大小定为sqrt(n)左右最优，此时块数也是sqrt(n)左右，易证。以下是块状链表的基础操作的思想、复杂度和代码。
一、声明。C++ STL中提供了list和vector两种数据结构，于是，若我们将它们嵌套起来，便是一个很方便的块状链表，免去指针之类的操作。这里的每个块仅仅存储了数据，没有存储额外的域，实际情况要予以添加。
next函数用于返回list的迭代器x的下一个迭代器。
1 #include<cstdio> 2 #include<vector> 3 #include<list> 4 using namespace std; 5 int sz;//块大小,一般为sqrt(n) 6 struct BLOCK{vector<int>data;BLOCK(){}}; 7 list<BLOCK>List; 8 typedef list<BLOCK>::iterator L_ITER; 9 typedef vector<int>::iterator V_ITER;10 inline L_ITER next(L_ITER x){x++; return x;}//返回x的下一个块
*下文中的curB指当前块,nextB指下一个块,newB指新块
二、定位。需要沿着链表顺序查找，假设查询线性表中第p(下标从1开始)个数，那么需要找到块Blockt，使得t*sz>=p，且(t-1)*sz<p。所以，查询的复杂度与块数同阶，即O(sqrt(n))。
1 inline L_ITER Find_Pos(const int &p)//返回整个块链中,下标p所在的块,下标默认从1开始 2 {3 int cnt=0;4 for(L_ITER it=List.begin();it!=List.end();it++)5 {6 cnt+=(*it).data.size();7 if(cnt>=p) return it;8 }9 }
三、维护块状链表的形态。我们一般保证块的大小在[sqrt(n)/2,sqrt(n)*2]之内，块链不会退化，因此，若相邻两块的大小之和不超过sqrt(n)，则将它们合并。我们在这里采取将相邻两块的大小加起来>sqrt(n)，且每块大小不超过sqrt(n)的写法。之所以采取这种写法，是因为我们不需要考虑将过大块分裂的情况。
(1)合并：目的是在相邻两块大小之和不超过sqrt(n)时进行合并。复杂度显然是O(sqrt(n))。
1 void Merge(L_ITER a,L_ITER b)//将b合并给a 2 {3 (*a).data.insert((*a).data.end(),(*b).data.begin(),(*b).data.end());4 List.erase(b);5 }
(2)扫一遍块链维护形态，这在很多操作之后都要进行。由于块链插入和删除的特点，使得每次要维护的块数相对较少，所以这个复杂度仍然是O(sqrt(n))。
1 void MaintainList()//维护块链的形态,保证每块的元素数恰当 2 { 3 L_ITER curB=List.begin();//将指针置于链表表头 4 while(curB!=List.end()) 5 { 6 L_ITER nextB=next(curB); 7 while(nextB!=List.end()&&(*curB).data.size()+(*nextB).data.size()<=sz) 8 { 9 Merge(curB,nextB);10 nextB=next(curB);11 }12 curB++;13 }14 }
四、分裂。主要用于插入和删除时对最左右两端的块的操作。复杂度显然是O(sqrt(n))。
1 void Split(L_ITER curB,int p)//在curB的p前分裂该块 2 {3 if(p==(*curB).data.size()) return;//分裂的位置在末尾，不需要分裂 4 L_ITER newB=List.insert(next(curB),BLOCK());//在curB的后面插入一个新的块5 (*newB).data.assign((*curB).data.begin()+p,(*curB).data.end());//将原来块的后半部分数据复制给新块 6 (*curB).data.erase((*curB).data.begin()+p,(*curB).data.end());//将原来块中的后半部分元素删除 7 }
五、插入。若是插入一段元素，这里的复杂度应该是O(length)(插入部分长度)，我们这里不予以考虑(有缩点等办法解决)。因此时间消耗主要来自分裂。
具体做法是：先定位，再将原块分裂，然后我们将待插入的数据组织成最紧凑的形式，即前面若干个大小为sqrt(n)的块、最后添上一个余块的形式，插入到原链表中。
1 void Insert(const int &p,const int &x,const int &v)//在p处插入x个数,待插入的权值均为v 2 { 3 L_ITER curB=Find_Pos(p); 4 Split(curB,p); 5 int cnt=0; 6 while(cnt+sz<=x) 7 { 8 L_ITER newB=List.insert(next(curB),BLOCK()); 9 (*newB).data.assign(sz,v);//设置新块的数据10 curB=newB;11 cnt+=sz;12 }13 if(x-cnt!=0)14 {15 L_ITER newB=List.insert(next(curB),BLOCK());16 (*newB).data.assign(sz,v);//设置新块的数据17 }18 MaintainList();19 }
六、删除。先定位，若整块删除，则为O(1)，若块被部分删除，则先分裂再删除。因此复杂度为O(sqrt(n))。
1 void Erase(const int &p,int x)//删除块链中从p位置开始的x个数 2 { 3 L_ITER curB=Find_Pos(p); 4 Split(curB,p); curB++; 5 L_ITER nextB=curB; 6 while(nextB!=List.end()&&x>(*nextB).data.size()) 7 { 8 x-=(*nextB).data.size(); 9 nextB++;10 }11 Split(nextB,x);12 List.erase(curB,next(nextB));//将[curB,nextB]全部删除 13 MaintainList();14 }
*至此，我们定义完了块状链表的基本操作。
Part 2、可持久化块状链表。
---------------------------------------------------------------未完待续----------------------------------------------------------------------------
参考资料: ①苏煜 《对块状链表的一点研究》;②《青少年信息学奥林匹克竞赛实战辅导丛书·高级数据结构》;③陈立杰 《可持久化数据结构研究》。
【块状链表】AutSky_JadeK的块状链表模板+总结(STL版)