分块

• 问题引入：

对一个非负整数序列A，在有可能随时添加或删除元素的情况下，实时查询序列元素第K大，即把序列元素从小到大排序后从左到右的第K个元素

直接查询，在添加跟删除元素的时候O(N)时间复杂度来移动序列元素。

• 分块：

对于一个有N个元素的有序序列来说，除最后一块外，其余每块中元素的个数都应当为根号N向下取整，于是块数为根号N向上取整

1.int table[MAX],表示当前整数x的当前存在个数
2.int block[SQR],表示第i块中存在的元素个数

添加或删除：对应的table和block都++或都--

查询：先用找第K大的元素在哪一块，然后在块内找这个元素，因此单次查询的总时间复杂度为O(根号N)。