共计 811 个字符，预计需要花费 3 分钟才能阅读完成。
刚刚做 A1057 Stack 题的时候遇到超时问题，查阅了相关的资料，发现这道题最优的两种做法分别是分块思想和树状数组；
这章先介绍一下分块思想：首先分块思想针对的是在线队列，也就是会对队列进行修改和操作，包括树状数组针对的也是这个问题；
其实分块思想下的一个典型问题就是实时查询序列元素第 K 大的问题。分块思想的本质就是将序列按照索引划分为不同的块，所以每个元素就有隶属的块；在每一块中，为每一个元素建立 hash 数组，用来存储每个元素的重复个数。当我们需要查询第 k 大问题的时候，就可以先通过每一块的元素个数，计算它在那一块，再通过块中的每一个元素的 hash 值，从而判断需要查询的第 k 个元素是哪一个元素；
使用分块思想的优势就是可以通过分块来计算相应的值，省去了排序的步骤；例如对于我们 A1057 题，最蠢最笨的思路就是把序列提出来，排序，然后找第 k 个值，这样就徒劳的增加了时间复杂度；
具体的分块计算策略如下所示：1. 当我们的序列长度为 n，出最后的一块，剩下的每块中的元素应该为√n(向下取整)，并且块数应该为√n(向上取整)。之所以对块数向上取整的目的是将最后不满的块独立划分为一块；2. 同时，我们建立两个数组，一个为 block 数组，一个为 table 数组；其中，block[i] 代表的第 i 个块中所含有的元素个数，table[i] 代表的是所有序列中第 i 个元素所现在存在的重复个数；
例如，我们当前分了 316 块，我们可以添加和查询以及删除元素；当我们添加元素的时候，应该先寻找在那一块，例如 304/316=0，代表 304 号元素在第 0 块，block[0]++,table[304]++；当我们需要查询第 k 个元素的时候，我们需要对比每一个块，也就是 block[i]，看看在第几块中，找到在第几块的的时候，逐个枚举属于该块的 table[i]，看看是第 k 个元素是否是 i; 删除元素同理，寻找在第几块，相应的 block[i]–，table[j]++;