华师一附中OI组

标题: 块状数组块状链表 [打印本页]

作者: admin 时间: 2020-2-20 10:35
标题: 块状数组块状链表
问题

给出一个长串，然后给出n个操作，操作有两种，在某个位置插入一个字符，或者查询第x个位置上的字符是什么

对于这个问题，我们有两种解决方案。

1：数组

查询 O(1) 但是插入最坏可以达到 O(len)

2：链表

插入 O(1) 但是查询最坏也可以达到O(len)

所以如何优化这个问题。

这里介绍一种数据结构——块状数组。

普通的数组，每个节点都是连续的。

而块状数组是把一个大块分为若干个小块，然后连接起来，因此得名块状数组。

数组块数*每个块的最大长度>=总的元素+操作个数，即分块以后，每个块都有个增大的空间（让其大于操作个数即可）

分块，就是优美的暴力~

如何查询与插入？

sum(i)为第1块到第i块字符的总个数。

再插入时我们可以利用二分快速寻找位置所对应的块号。

而在查询时，也是利用二分来查询块号输出。

在最坏情况下=sqrt(str)+n;

在平均情况下=sqrt(str+n);

block_num,块数：

准确讲，=(str+n)/block_len

结合平均情况来讲，block_num=block_len=sqrt(str+n)

作者: admin 时间: 2020-2-20 10:36
http://poj.org/problem?id=2887

作者: admin 时间: 2020-2-20 10:43
基本概念：
设一个长度为N的序列，块的大小为S，从序列的第一个元素起，每S个元素被分为一块，若最终剩余的元素不足S个，令他们组成一块。一般来说存在两种操作，区间求和、区间加法。

当然在很多问题中使用传统数据结构会更加优秀，但是当所需要的信息无法快速合并，就只能使用分块。比如询问一个区间的众数。

加速原理：把数组分成若干个块，通过预处理的方式获得块的某些信息，在对块进行操作的时候直接查询即可无需遍历

但是要注意的是：树状数组>线段树>块状数组(分块)

树状数组：代码简单、常数小(有些时候真的会卡常)
线段树：代码复杂、功能强大、常数大
块状数组：代码复杂、常数大、能维护一些很难快速合并的数据

1.区间求和：
假设询问的区间是 [l,r] ，l所在的块为 bl ,r所在的块为 br

a.当给定区间在同一个块内，即bl=br时

直接枚举 [l,r] 的答案时间 O(S)

b.当给定区间不在同一个块里，即bl<br

那么区间就可以被分为三个部分

(1)[l,块bl的右端点]

(2)块[bl+1~br-1] 显然，当bl和br相邻时，这个部分将不存在

(3)[块br的右端点,r]

对于(1)(3)还是直接枚举计算,对于(2)每个块的预处理块内元素和sum，枚举计算。时间复杂度 O(N/S)

2.区间加法：
a.给定区间在同一个块内

直接枚举修改每个元素值，同时更新块bl的sum，时间复杂度O(S)

b.给定区间不在同一个块内

同上，区间被分为3个部分，且在同一个区间内(1)(3)直接枚举修改

对于(2)每个块不采取遍历的方式，而是维护两个值add(块内每个元素共同累加的数字)和sum。时间复杂度 O(N/S+S) ,显然当S=sqrt(N)时时间复杂度为最小 O(sqrt(N))

例题与代码实现：
基本概念中所阐述的逻辑是较为简单的，但是依旧是太菜无法用代码来实现。在学习很多算法的时候都是这样的，其背后的原因就是没有讲具体实现方法，即预处理如何处理。

例题：给定序列an,编号1~n,求a{j}-a{i}的最大值(1<=i<=j<=n)

作者：爱的魔力转圈圈
链接：https://www.acwing.com/blog/content/142/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者: admin 时间: 2020-2-20 10:44
题解：静态查询区间第k小问题，此处使用块状数组(平面分割)解决

附上代码：

作者: admin 时间: 2020-2-20 10:45
As we all known.数组定位的复杂度为O(1),插入删除的复杂度是O(n)

链表定位的复杂度是O(n),插入删除的复杂度是O(1)

块状数组结合了链表和数组的优点，使得所有操作的复杂度均为O（√n）

那么什么是块状数组呢？块状链表从宏观上看是链表，而链表中的每个节点又是一个数组。对于块状数组来说就是整个数据先分成若干个大数组，而这些大数组中又有小数组。再对其进行操作

典型范例：http://poj.org/problem?id=2887

题意：先给一行字符串。m次操作，Q表示查询第i（从1开始）个位置上的字符，I表示在第k个字母之前插入字母c

分析：显然暴力会超时，用线段树，树状数组，都要考虑新加入字母的问题。利用块状链表完美解决

代码：
————————————————
版权声明：本文为CSDN博主「我爱AI_AI爱我」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_30241305/article/details/52072546

作者: admin 时间: 2020-2-20 10:49
数组+链表 = [骗分]块状链表
前言
众所周知，对于一个一维的数组，或是一个字符串，我们可以使用两种办法：数组或链表两种方法来储存。但是，看了国家集训队2008年苏煜的论文之后，就知道了一种神奇的骗分方式：数组+链表形成的块状链表。
先来看看块状链表和两种方式的对比

方式修改查询
链表 O(N)O(N) O(1)O(1)
数组 O(1)O(1) O(N)O(N)
块状链表 O(N−−√)O(N) O(N−−√)O(N)
显而易见，块状链表对于处理综合修改和查询的速度比单一的数组或链表都要快，当数据量很大的时候，就可以考虑用块状链表来骗分。

原理
块状链表的原理其实很简单。既然链表或是数组都不够快，就把它们拼在一起吧……
将一个链表中的每一个元素都换成一个数组，或者说将多个元素压缩在一起，变成一个数组。
如下图所示

但是，这并不是这么简单的，在操作的过程中需要进行几种的操作。

1.定位
定位也就是直接找点，找到点所在的块，再在这个块中寻找

2.分裂
将一个分块以指定的位置为中心，分成两个分块

3.合并
将两个分块合并为一个分块

4.插入
先将插入的位置分裂，然后将要插入的元素(分块)插入

5.删除
在删除部分的左右两端分裂，把这个部分分裂出来，再删除掉。

分析
先来分析一下为什么要做分裂和删除。
分裂是插入和删除必不可少的一部分。但在有些情况也需要分裂，避免让块状数组退化成一般的数组。也就是所有的分块都在一起，成为了一个数组。
合并则正好相反，如果执行插入和删除过多，就会出现大量的分块，就可能退化为一般的链表。
综合这几步，就可以实现块状链表了。
如果还不明白，可以看看下面的两幅图：

1.插入

2.删除

总结
其实块状链表就是一种暴力的优化，属于骗分的范畴……
不过对于一部分的题目来说，块状链表可能是正解，或者正解太麻烦而块状链表刚好能够解决。
虽然看上去很简单，理解起来也简单，但实际实现却有些麻烦
————————————————
版权声明：本文为CSDN博主「Evolution__」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/baidu_35009437/article/details/54564154

作者: admin 时间: 2020-2-20 10:52
数据结构：块状链表
iteye_4389 最后发布于2012-12-15 21:32:00 阅读数 41 收藏
已转到：http://www.wypblog.com/archives/166
一、概述
有时候我们需要设计这样一种数据结构：它能快速在要求位置插入或者删除一段数据。先考虑两种简单的数据结构：数组和链表。数组的优点是能够在O(1)的时间内找到所要执行操作的位置，但其缺点是无论是插入或删除都要移动之后的所有数据，复杂度是O(n)的。链表优点是能够在O(1)的时间内插入和删除一段数据，但缺点是在寻找操作位置时，却要遍历整个链表，复杂度同样时O(n)的。这两种数据结构各有优缺点，我们可以把数组和链表的优点结合来，这就构成了一个新的数据结构：块状链表，结合数组和链表的优缺点的块状链表其各种操作的时间复杂度均为O(sqrt(n))。

二、块状链表的各种操作
块状链表是结合了数组和链表的优缺点，块状链表本身是一个链表，但是链表储存的并不是一般的数据，而是由这些数据组成的顺序表。每一个块状链表的节点，也就是顺序表，可以被叫做一个块。块状链表通过使用可变的顺序表的长度和特殊的插入、删除方式，可以在达到的复杂度。块状链表另一个特点是相对于普通链表来说节省内存，因为不用保存指向每一个数据节点的指针。

1、定位操作
定位操作其实可以当作是查找，我们当然是先要定位到元素所在的节点，然后在该节点里面的数组里面寻找我们要的节点；

2、分裂节点
将某个节点分裂成两个节点；

3、插入操作
首先定位要插入的位置，然后将所在节点分裂成两个节点，并将数据放到第一个节点的末尾。如果要插入的是一大块数据，首先要将数据切成多个块其中、每个块对应一个块状链表的一个节点，并将这些块链起来，然后将它们插入那两个节点之间。插入的操作图类似下面：

4、删除操作
首先定位删除元素的位置，然后按照数组删除元素的方法删除该数据。如果删除一大块数据，首先要定位数据块首元素和末元素所在的位置，然后分别将它们所在的节点分裂成两个节点，最后删除首元素和末元素之间的节点即可。

三、关键技术
从总体上来看，维护一个链表，链表中的每个单元中包含一段数组，以及这个数组中的数据个数。每个链表中的数据连起来就是整个数据。设链表长度为a，每个单元中的数组长度是b。无论是插入或删除，在寻址时要遍历整个链表，复杂度是O(a)；对于插入操作，直接在链表中加入一个新单元，复杂度是O(1)；对于删除操作，会涉及多个连续的单元，如果一个单元中的所有数据均要删除，直接删除这个单元，复杂度是O(1)，如果只删除部分数据，则要移动数组中的数据，复杂度是O(b)。总的复杂度是O(a+b)。因为ab=n，取a=b=√n，则总的复杂度是O(√n)。

问题是如何维护a和b大致等于√n？

在执行插入操作后，如果当前单元中的数据个数>2√n，则将当前单元分割成两个新单元，每个单元中的数据个数保持为2√n。在执行删除操作后，如果当前单元和当前单元的下一个单元的数据个数和<√n，则将两个单元合并成一个新单元。执行上述维护操作需要移动数组中的数据，复杂度是O(b)，对于单元的分割和合并均是O(1)的，总的复杂度是O(b)的。这样，维护操作并不会使总复杂度增加。最终得到一个复杂度是O(√n)的数据结构。

四、应用
1、文本编辑器：http://download.noi.cn/T/noi/noi2003A.pdf

另一种实现：http://www.byvoid.com/blog/noi-2003-editor/

2、维护数列：http://download.noi.cn/T/noi/noi2005A.pdf

另一种实现：http://www.byvoid.com/blog/noi-2005-sequence/

作者: admin 时间: 2020-2-20 11:02
https://blog.csdn.net/weixin_342 ... _relevant.none-task

欢迎光临华师一附中OI组 (http://hsyit.cn/)