那个世界其实是联系在一起的，所以就算是分开大家也都不是孤身一人，和重要的人一直都是联系在一起的。——《请问您今天要来点兔子吗？》

分块

这篇文章里不会出现量词爆炸。

分块是一种思想，把一个整体切为若干个小坨，对整块整体处理，零散块单独处理，在划分后的每个块上预处理部分信息。用较一般的暴力算法取得更优的时间复杂度，其取决于分块的块长。分块其通用性更强，可以维护很多线段草和草状数组无法维护的信息。

块状数组

块状数组把一个长度为 的数组划分成 坨，每坨长度为 。对于一次区间操作，对区间内部的整坨进行整坨整坨地操作，对区间边缘的零散块单独暴力处理。

这里块数的个数既不能太多，也不能太少。如果太少，区间中的整块的数量会很少，我们要花费大量的时间处理零散块；如果太多，又会让块的长度太短，失去整体处理的意义。一般来说，取块数为 为佳，这样在最坏情况下，我们要处理接近 个整块，还要对长度为 的零散整块单独处理，总时间复杂度为 。这是一种根号算法。

显然，分块的时间复杂度太暴力了，完全比不上线段树和树状数组这种对数级算法。但由此换来的，是更高的机动性，与线段草不同，块状数组没有那么多乱七八糟的要求，它不要求所维护信息满足结合律，也不需要一层层传递标记。线段草是一棵高为 的草，而块状数组是一棵高为三的草：

我是块状数组！

预处理

具体地使用块状数组，我们要先划定每个块所占据的位置：

1
2
3
4
5
6
int sq = sqrt (n);
for (int i = 1; i <= sq; i ++)
{
	st[i] = n / sq * (n - 1) + 1; // st[i] 表示第 i 坨的第一个元素的下标
	ed[i] = n / sq * i; // ed[i] 表示第 i 坨的最后一个元素的下标 
}

但是数组的长度可能不是一个完全平方数，这样会漏一小坨，我们将其纳入最后一坨：

1
ed[sq] = n;

然后，为每一个元素确定它们属于的块。

1
2
3
for (int i = 1; i <= sq; i ++) // 遍历 sq 坨 
	for (int j = st[i]; j <= ed[i]; j ++) // 遍历刚刚记好的下标  
		bel[j] = i;

最后，如果必要，我们还要求一下每一坨的大小：

1
2
for (int i = 1; i <= sq; i ++)
	size[i] = ed[i] - st[i] + 1;

好了，到这里准备工作就好了，可以开始抛光了。

读入和预处理数据

输入以后，用 来保存每一个块的和。

1
2
3
4
5
6
for (int i = 1; i <= n; i ++)
	scanf ("%d", &a[i]);
for (int i = 1; i <= sq; i ++)
	for (int j = st[i]; j <= ed[i]; j ++)
		sum[i] += a[i];

区间修改

首先是区间修改，分为两种策略，当左右端点在同一块内时，直接暴力修改原数组和 数组：

1
2
3
4
5
6
if (bel[x] == bel[y])
	for (int i = x; i <= y; i ++)
	{
		a[i] += k;
		sum[bel[i]] += k;
	}

否则，先暴力修改左右两边零散区间：

1
2
3
4
5
6
7
8
9
10
for (int i = x; i <= ed[bel[x]]; i ++) // 从 x 到它属于的块的尾部
{
	a[i] += k;
	sum[bel[i]] += k; 
}
for (int i = st[bel[y]]; i <= y; i ++) // 从 y 属于的块开始到 y 
{
	a[i] += k;
	sum[bel[i]] += k;
}

然后在中间的整坨打上标记：

1
2
for (int i = bel[x] + 1; y < bel[y]; i ++) // 注意这里是按块遍历  
	mark[i] += k;

区间查询

同样地，如果左右两边在同一坨，直接暴力计算区间和。

1
2
3
if (bel[x] == bel[y])
	for (int i = x; i <= y; i ++)
		s += a[i] + mark[bel[i]]; // 注意要加上标记

否则，暴力计算零碎块：

1
2
3
4
for (int i = x; i <= ed[bel[x]]; i ++)
	s += a[i] + mark[bel[i]];
for (int i = st[bel[y]]; i <= y; i ++)
	s += a[i] + mark[bel[i]];

再处理整块：

1
2
for (int i = bel[x] + 1; i < bel[y]; i ++)
	s += sum[i] + mark[i] * size[i]; // 标记也要乘上块长

块状链表

所谓块状链表，就是链表配上块状数组，它结合了数组和链表的优缺点，块状链表本身是一个链表，每个块状链表的节点，也就是顺序表，可以被叫做一个块。块状链表有着优秀的复杂度，但是码量巨大。

做这张图真的好累啊

动态回收和分配节点

这个实则和块状链表没什么关系，可以将其看做一个垃圾桶，然后刚开始这个垃圾桶里堆满了垃圾（即节点编号，栈顶是 号节点，栈底是 号节点）。有需要的时候将其取出（此时会返回一个栈顶存的编号，告诉你分配的是哪个节点编号），回收的时候就放回去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int pool[N], tot;
inline int new_node () // 分配节点 
{
	return pool[tot --]; // 栈内元素减一（拿走） 
}
inline void del (int x) // 回收节点 
{
	pool[++ tot] = x; // 回收的这个节点成为栈顶元素 
}
inline void init () // 刚开始所有节点编号都存在垃圾桶里  
{
	for (int i = 1; i < N; i ++)
		pool[++ tot] = N - i; // 注意这里栈顶元素是 1 
}

链表节点

这个写个结构体就好，非常简单，记录每个节点所代表的数组长度和链表中下个节点：

1
2
3
4
struct node {
	int sz, nxt; // 该节点对应数组长度和下一个节点
	int s[N]; // 数组
} a[N];

查询位置

我们一次一次用大位置减去块代表数组的长度，当不够减了或者已经是链表结尾就结束：

1
2
3
4
5
6
7
8
9
10
11
inline int pos (int &p) // 返回原数组中下标为 p 的元素所在的块的编号，并将传入的引用（原数组下标）改为块内下标  
{
	// 这一段有点像珂朵莉树里暴力查询的代码，如果不能理解建议溜去那边看看  
	int x = 0; // 这里的 x 是指第 x 块，即节点编号  
	while (x != -1 && a[x].sz < p) // 当这个光标能够减去的长度小于这个块长时，就说明属于该块，要不就是最后一块   
	{
		p -= a[x].sz; // 用 p 减去这个节点中数组长度  
		x = a[x].nxt; // 直接传送到下一个节点去  
	}
	return x; // 返回属于块的编号  
}

暴力插入

在 后面插入一个 节点，那么 的指针（即后面的节点）会继承 的指针，而 的指针就指向 ：

1
2
3
4
5
6
7
8
9
10
11
inline void add (int x, int y, int len, int l, int r) // 暴力插点  
{
	if (y != -1) // 当它不是重新开的那个节点  
	{
		a[y].sz = len; 
		a[y].nxt = a[x].nxt; // y 的指针就是 x 的指针，即指向原来 x 的后面的节点 
		for (int i = 1, j = l; i <= len, j <= r; i ++, j ++)
			a[y].num[i] = s[j];
	}
	a[x].nxt = y; // x 的指针重新调到 y 身上 
}

节点合并

同化，蚕食，生存的方式。

合并 和 节点：

1
2
3
4
5
6
7
8
inline void merge (int x, int y) // 节点合并  
{
	for (int i = a[x].sz + 1, j = 1; i <= a[x].sz + a[y].sz, j <= a[y].sz; i ++)
		a[x].num[i] = a[y].num[j]; 
	a[x].sz += a[y].sz; // 复制信息 
	a[x].nxt = a[y].nxt; // x 继承了 y 的指针 
	del (y); // 删除 y 
}

节点分裂

你，只要有一刻认同我的想法，

你，就会成为我，成为我的影子。

把第 从 位置分裂成两个节点：

1
2
3
4
5
6
7
8
inline void split (int x, int pos) // 节点分裂  
{
	if (x == -1 || pos == a[x].sz) // 如果不存在或者不需要分裂  
		return ;
	int t = new_node (); // 创造一个新节点 
	add (x, t, a[x].sz - pos, pos + 1, a[x].sz); // 把分离出来的后半部分放在后面（好像是句废话） 
	a[x].sz = pos; // 这里没有删去，而是直接调整长度光标（等于删去） 
}

插入

从这里，才是开始。

暴力插入会导致链表失衡，我们原本的链表是基本平衡的，也就是能保证一次操作复杂度在 级别的。但是现在有一个很长的串要插入到 后面，如果直接插入，就会导致中间的节点长度巨大，使得一次操作复杂度退化近似 。

那么为了不出现这种请况，我们可以先把插入的串进行分块（同样以 作为块的长度），构建链表，插入到原链表中即可。

但是如果这个串的长度不是一个完全平方数，可能在最后会留下一个小块，这样也会使时间复杂度退化到 。

那么这个时候就要用到之前准备的合并操作了，因为我们插入使中间的块长度一定是 ，所以我们只考虑插入串的左右端点，如果两端的块长度和小于 ，就直接合并。

还有一件事，不一定是在完整的块后插入，也可能是某个块中的某个元素后面插入，那么我们就通过查询和分裂的配合，把插入位置强行变成一个完整块的结尾，再进行插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
inline void insert (int x, int len) // 在位置 x 后面插入长度为 len 的序列 
{
	int now = pos (x), nxt = now, tot = 0, t, l = 1, r = sq;
	split (now, x); // 先分裂节点
	while (tot + sq <= len) // 把已经分好块的长为 sq 的一坨坨放入链表，最后会剩下一个 len - tot 的一个串 
	{
		t = new_code ();
		add (nxt, t, sq, l, r);
		l += sq; // 推动左端点  
		r += sq; // 推动右端点  
		nxt = t; // 转移指针 
		tot += sq; // 叠加长度 
	}
	r = len;
	if (tot < len) // 把剩下的一点处理掉  
	{
		t = new_node ();
		add (nxt, t, len - tot, l, r)
	}
	if (t != -1 && a[nxt].sz + a[t].sz < sq) // 如果前后的块加起来小于标准长度就合并
		merge (nxt, t);
	if (a[now].nxt != -1 && a[now].sz + a[a[now].nxt].sz < sq) // 同上
		merge (now, a[now].nxt);
}

删除

要删除 到 元素，先把两端的节点断开，然后直接删除，同时维护两个端点的信息。最后留下的两个小块（如果有的话）直接合并即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
inline void remove (int x, int len) // 删除一段区间  
{
	int now = pos (x);
	split (now, x); // 在左端点分割  
	int nxt = a[now].nxt; 
	while (nxt != -1 && len >= a[nxt].sz) // 尽量删一整块 
	{
		len -= a[nxt].sz; 
		nxt = a[nxt].nxt;
	}
	if (nxt != -1) // 特判节点为空 
	{
		spilt (nxt, len); // 就在右端点分割 
		nxt = a[nxt].nxt; // 定位删除后的右边部分 
	}
	for (int i = a[now].nxt; i != nxt; i = a[now].nxt)
	{
		a[now].nxt = a[i].nxt; // 继承指针  
		del (i); 
	}
	while (nxt != -1 && a[now].sz + a[nxt].sz < sq) // 暴力合并剩下的两个小块块 
	{
		merge (now, nxt); // 直接暴力合并  
		nxt = a[nxt].nxt;
	}
}

查询

从第 个元素，找一条 的条条，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void get (int x, int len) // 从第 x 个元素开始（大体上看的 x ） 
{
	int now = pos (x), tot = min (a[now].sz - x, len), cur = 0; // 先处理左边不完整的部分  
	for (int i = a[now].sz - tot + 1; i <= a[now].sz; i ++) // 左边块处理  
		ans[++ cur] = a[now].num[i];
	int nxt = a[now].nxt; // 转移指针  
	while (nxt != -1 && len >= a[nxt].sz + tot) // 整块整块的弄起来 
	{
		for (int i = 1; i <= a[nxt].sz; i ++)
			ans[++ cur] = a[nxt].num[i];
		tot += a[nxt].sz;
		nxt = a[nxt].nxt;
	}
	if (nxt != -1 && tot < len) // 右侧如果还有剩余就再搞 
		for (int i = 1; i <= len - tot; i ++)
			ans[++ cur] = a[nxt].num[i];
	for (int i = 1; i <= cur; i ++)
		printf ("%d ", ans[i]);
}

网上大多数都是写 文本编辑器的题解的， 真的比循环好写不知道多少……