（算法笔记）分块的思想，在线查询

第一次写csdn哈哈哈，大二菜鸡，现在开始在csdn记录我变强的过程吧！
今天在算法笔记上面学了一个分块查询，觉得很有意思，其思想简练但是又极大的加快了查询速度，并且自动排序。是一种以空间换时间的算法。
分块查询，故名思意，就是把需要查询的数据分成一块一块的。
比如：0~1e5个数，需要在线查询第k大的数是多少，当查询次数很大时，是无法承受的。
用分块的思想可以把其查询时间复杂度的降低到O(N^-1)
1.把1e5个数分为根号1e5个数，即316个为一组，分317组，组是按线性分组的，从1~1e5依次数316个元素为一组
2.用table[100001]来存对应元素x的个数，用block[317]来存0~316块分别含有的元素。

在上面的基础上，完成插入与删除就很方便了
delete(x): block[x/316]-- table[x]–;

void  Delete(int x) {
	block[x / group]--;
	table[x]--;
}

insert(x): block[x/316]++ table[x]++;

	void insert(int x) { //插入
	block[x / group]++;
	table[x]++;
} 

删除，与差插入都是O(1)

下面是最关键的查找第K大的元素：
如查找第K大
从0~316由低到高依次枚举block块中的元素个数，并记录总数，如果当前块+之前块的总数>=K,则第K大的元素就在当前块中，枚举当前块中的元素当元素总个数累计到K时，这个元素就是第K大的.
代码实现较为简单：

int find_k_th(int k) { //查找
	int sum = 0; 
	for(int i = 0;i < 317; i++) {
		if(sum + block[i] >= k) { //说明第k大的元素在其中 
			for(int j = i * group; j < i * group+group; j++) { // 从这个块开始枚举`在这里插入代码片`
				if(table[j] > 0) sum++;//判断一下是否存在元素j，
												//这里也有分块的思想，把table[j]当一整块
				if(sum == k) return j; 
			}
		}
		sum += block[i];
	}
	return -1;
}

这个算法给我了启发，主要是分块的想法，找一个东西不一定需要一个个的找，可以先模糊一点，一块块的找，如果确定这个东西在这个块里面，我能再仔细的在这个块里面找，当然必须要有一个媒介能够让我们在遍历块的时候知道我们找的东西在不在块里面，比如这个分块查询的媒介就是通过每块的元素和来判断的。这是一种思想可以运用到任何地方，我觉得这正是算法的学习的乐趣所在，也是算法更深层次的意义所在，我会好好学习算法，虽然我现在还很菜，但是我相信总有一天，我达到一个高度的，加油！
谢谢观看，不足请指出。