WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数据结构部分简介
栈
队列
链表
哈希表
并查集
堆简介
二叉堆
配对堆
左偏树
分块思想
块状数组
块状链表
树分块
Sqrt Tree
单调栈
单调队列
ST 表
树状数组
线段树
李超线段树
区间最值操作 & 区间历史最值
划分树
二叉搜索树简介
Treap
Splay
WBLT
Size Balanced Tree
AVL 树
替罪羊树
笛卡尔树
左偏红黑树
跳表
可持久化数据结构简介
可持久化线段树
可持久化块状数组
可持久化平衡树
可持久化字典树
可持久化可并堆
线段树套线段树
平衡树套线段树
线段树套平衡树
树状数组套主席树
分块套树状数组
K-D Tree
珂朵莉树
Link Cut Tree
Euler Tour Tree
Top Tree
析合树
50 objects
本站非官方,所收集资源均来源于网络。
块状链表 - 数据结构
author: HeRaNO, konnyakuxzy [![./images/kuaizhuanglianbiao.png](../images/kuaizhuanglianbiao.png "./images/kuaizhuanglianbiao.png")](../images/kuaizhuanglianbiao.png "./images/kuaizhuanglianbiao.png") 大概就长这样…… 不难发现块状链表就是一个链表,每个节点指向一个数组。 我们把原来长度为 n 的数组分为 $\sqrt{n}$ 个节点,每个节点对应的数组大小为 $\sqrt{n}$ 。 所以我们这么定义结构体,代码见下。 其中 `sqn` 表示 `sqrt(n)` 即 $\sqrt{n}$ , `pb` 表示 `push_back` ,即在这个 `node` 中加入一个元素。 ```cpp struct node { node* nxt; int size; char d[(sqn << 1) + 5]; node() { size = 0, nxt = NULL, memset(d, 0, sizeof(d)); } void pb(char c) { d[size++] = c; } }; ``` 块状链表应该至少支持:分裂、插入、查找。 什么是分裂?分裂就是分裂一个 `node` ,变成两个小的 `node` ,以保证每个 `node` 的大小都接近 $\sqrt{n}$ (否则可能退化成普通数组)。当一个 `node` 的大小超过 $2\times \sqrt{n}$ 时执行分裂操作。 分裂操作怎么做呢?先新建一个节点,再把被分裂的节点的后 $\sqrt{n}$ 个值 `copy` 到新节点,然后把被分裂的节点的后 $\sqrt{n}$ 个值删掉( `size--` ),最后把新节点插入到被分裂节点的后面即可。 块状链表的所有操作的复杂度都是 $\sqrt{n}$ 的。 还有一个要说的。 随着元素的插入(或删除), $n$ 会变, $\sqrt{n}$ 也会变。这样块的大小就会变化,我们难道还要每次维护块的大小? 其实不然,把 $\sqrt{n}$ 设置为一个定值即可。比如题目给的范围是 $10^6$ ,那么 $\sqrt{n}$ 就设置为大小为 $10^3$ 的常量,不用更改它。 ```cpp list
> orz_list; ``` ## 例题 Big String POJ - 2887 题解: 很简单的模板题。代码如下: ```cpp #include
#include
#include
using namespace std; static const int sqn = 1e3; struct node { node* nxt; int size; char d[(sqn << 1) + 5]; node() { size = 0, nxt = NULL; } void pb(char c) { d[size++] = c; } }* head = NULL; char inits[(int)1e6 + 5]; int llen, q; void readch(char& ch) { do ch = getchar(); while (!isalpha(ch)); } void check(node* p) { if (p->size >= (sqn << 1)) { node* q = new node; for (int i = sqn; i < p->size; i++) q->pb(p->d[i]); p->size = sqn, q->nxt = p->nxt, p->nxt = q; } } void insert(char c, int pos) { node* p = head; int tot, cnt; if (pos > llen++) { while (p->nxt != NULL) p = p->nxt; p->pb(c), check(p); return; } for (tot = head->size; p != NULL && tot < pos; p = p->nxt, tot += p->size) ; tot -= p->size, cnt = pos - tot - 1; for (int i = p->size - 1; i >= cnt; i--) p->d[i + 1] = p->d[i]; p->d[cnt] = c, p->size++; check(p); } char query(int pos) { node* p; int tot, cnt; for (p = head, tot = head->size; p != NULL && tot < pos; p = p->nxt, tot += p->size) ; tot -= p->size; return p->d[pos - tot - 1]; } int main() { scanf("%s %d", inits, &q), llen = strlen(inits); node* p = new node; head = p; for (int i = 0; i < llen; i++) { if (i % sqn == 0 && i) p->nxt = new node, p = p->nxt; p->pb(inits[i]); } char a; int k; while (q--) { readch(a); if (a == 'Q') scanf("%d", &k), printf("%c\n", query(k)); else readch(a), scanf("%d", &k), insert(a, k); } return 0; } ```