分块

这是第一篇博客。嘿嘿嘿！话不多说，直接开始。
首先来说一下什么是分块：
       分块，顾名思义，即将数据切分成块。那么，这有什么意义呢？其实，分块是一种优雅的暴力。
这里给出一道例题：洛谷P2801。https://www.luogu.org/problemnew/show/P2801
       以此题为例：
       有一组数据，共有n项，我们通常以根号n作为划分标准，即每一块有根号n项数据（为保持原有数据，需要开设新的数组）。以下是分块的初始化：

int n,  a[maxn]；//n为数据的规模，a数组存储原始数据
int b[maxn]；
int  l[maxn], r[maxn], belong[maxn],  block, num;
//b数组是进行分块操作的数组，初始时是a数组的一个副本

void bulid(void) {
	block = int (sqrt(n));		//block为每一块所包含的元素个数
	num = n / block;		//num为数组最终被分块之后的块数
	if (n%block) {
		num++;
	}
	for (int i = 1; i < num; i++) {		//默认下标从1开始，第num块单独处理，因为第num块数组元素无法确定
		l[i] = (i - 1) * block + 1;		//l数组存储每一块数据的起始点下标
		r[i] = i * block;				//r数组存储每一块数据的结束下标
		sort(b+l[i], b+r[i]+1);
	}
	l[num] = (num - 1)*block + 1;
	r[num] = n;
	sort(b+l[num], b+r[num]+1);		//对块进行分类

	for (int i = 1; i <= n; i++) {
		belong[i] = (i-1) / block+1;	//belong数组存储每一个元素所属的下标
	}
}

       此题如果使用暴力，必然超时，那分块又是如何来达到这优雅的暴力的呢？
       此题的关键在于频繁地对某一区间的数据进行访问。众所周知，对有序数据的访问在很多时候比对无序数据的访问更为高效，比如搜索（有序数组的二分搜索必然比无序数组的遍历更为高效）。因此，我们对每一块都进行排序。（此步预处理，虽会消耗时间和空间，但在数据量大，且对区间操作频繁的时候，会在不久的将来比暴力省下不少时间，可谓是未雨绸缪啊！）
       首先请看对数据的更新操作：
       大致分为如下两种情况:
       1：需要更新的区间包含多个块
       2：需要更新的区间同属于一个块

       对于第一种情况，区间之间的完整块可直接利用数组来记录区间的变化情况（此处利用add数组来记录整一块数据的变化情况），而对于非完整块，则只需对原数组进行跟新即可，同时更新之后需要对非完整块所属的块进行排序，以维持其有序性。

void reset(int x) {	//对非完整区间进行数据跟新之后，需要保持其有序性
	for (int i = l[x]; i <= r[x]; i++) {
		b[i] = a[i];
	}
	sort(b + l[x], b + r[x] + 1);
}

void update(int left,int right,int val) {
	if (belong[left] == belong[right]) {	//第二种情况
		for (int i = left; i <= right; i++) {
			a[i] += val;
		}
		reset(belong[left]);
		return;
	}
	//第一种情况
	for (int i = left; i <= r[belong[left]]; i++) {	//左端非完整块
		a[i] += val;
	}
	reset(belong[left]);	//保持有序性
	
	for (int i = belong[left] + 1; i < belong[right]; i++) {	//中间区块
		add[i] += val;	//此处的add数组记录了此块区域的数据至此为止的变化量，add数组是分块优雅的一处体现
	}					

	for (int i = l[belong[right]]; i <= right; i++) {	右端非完整块
		a[i] += val;
	}
	reset(belong[right]);	//保持有序性
}

       接下来是访问数据：由于每一块都是有序的，因此对块内的更新可以利用二分来缩短时间。对于第一种情况，区间之间的完整块利用b数组来完成访问，而非完整块，则利用原数组进行访问，可见非完整块最多只会有两块。对于第二种情况，只需对原数组访问即可。（以下给出此题的访问操作）

int ask(int left, int right, int val) {
	int sum = 0;
	if (belong[left] == belong[right]) {		//第二种情况
		for (int i = left; i <= right; i++) {
			if (a[i] + add[belong[i]] >= val) {	//原数据加上变动量才是此时的数据值，注意！
				sum++;
			}
		}
		return sum;
	}
	//第一种情况
	for (int i = left; i <= r[belong[left]]; i++) {	//左端非完整区块
		if (a[i] + add[belong[i]] >= val) {
			sum++;
		}
	}
	//中间完整块
	for (int i = belong[left] + 1; i < belong[right]; i++) {	//此处以块进行遍历
		sum +=fin(i, val-add[i]);		//在块内配合以二分
	}									//速度远大于普通暴力
	
	for (int i = l[belong[right]]; i <= right; i++) {	//右端非完整区块
		if (a[i] + add[belong[i]] >= val) {
			sum++;
		}
	}
	return sum;
}

       至此，此题讲解完毕。分块的核心思想应该阐述清楚。

       总结：之所以要分块，是为了能在区间进行更为高效的操作， 同时也要注意不能让他上升到整个区间，不然就没有意义了。
终于写完第一篇了，好累。。。。。。虽然写的不太美观，也没什么样式，以后再慢慢改善吧。