[算法笔记] 分块 数列分块入门1

给你一个数组，长度为n，你现在有两种操作，1.你需要查询区间[l,r]的一些性质(比如区间和一类的)，2.你还有可能去修改区间[l,r]，这两个操作要进行m次。

对于这样区间询问和修改问题，我们一般都需要借助数据结构来进行解决，树状数组和线段树都可以解决区间查询和修改问题，而且具有很优秀的复杂度。但是在这之上是有代价的，以log的复杂度查询是因为我们再处理问题时把信息以2的幂进行压缩了，但是我们同时有丧失了数组的原本信息(纯字面意思，因为我们把信息转化成了区间和或者其他可以进行差分和前缀和的信息的区间信息，丧失每个独立个体信息，如果这里表达不清楚，接着看，下面就有例子)。而且线段树和树状数组都是有一定的思维量的，你要进行建立对应数据结构来维护信息。而且万一想要我们保存原本的数据信息，我们该怎么办?分块是一个很好的选择，因为它有更高的灵活性，它不是数据结构，所以它可以最大程度保存原本的数据信息。

那什么是分块呢?首先它是一种思想，如果暴力求解一个[l,r]的区间，我们一般都是直接for循环遍历去找，而分块是你把原本数组分成好多块，预处理出每一块，查询时候两端有可能不是整块，那我们只要去暴力处理两端散块，然后按整块处理中间的区间。为了让不让我们处理某一个区间速度不确定，我们尽量让每一个块差不多大，这样无论哪个区间，我们不会出现某一个区间特别快，另一个区间特别慢的这样的情况。所以我们设长度为n，分x个块，每一个块大小差不多，因为暴力处理两端散块，所以两端最复杂的情况是2倍的n/x，然后处理整区间，因为整区间是我们处理好的，所以每一块可以O(1)获得，所以复杂度大概式子是(我们忽视一下常数)，根据高中的基本不等式可得，我们复杂度最小得，当x等于 时等号成立，所以我们解出来x等于时有最高的效率(还是看题目情况，有时候不用取到根n的复杂度就够了，或者以其他做管理区间更方便，都可以，这里只是论证为什么有时候默认选取根n比较优秀)。所以取个区间，每个区间长，我们可以获得查询区间[l,r]以O()的复杂度。如果n在1E5，查询次数在1E5，时间复杂度足够用了。

我们可以试一下解决线段树模板题 洛谷的线段树模板题

首先我们需要分块，对数组按进行分块，如果不能被整分，我们把最后剩下的区间归到最后一个(也可以再开一个不满的区间)。

int s=sqrt(n)
for(int i=1;i<=s;i++){
    st[i]=s*(i-1)+1;
	en[i]=s*i; 
}
en[s]=n;

然后我们要对每个位置让它找到它归哪一个区间

for(int i=1;i<=s;i++){
	for(int j=st[i];j<=en[i];j++){
		bel[j]=i;//bel数组是英文belong的缩写
        sum[i]+=arr[j];//sum存储每个块的和
	}
}

现在我们初始化做完了，现在对于任意一个区间，我们可以找到它两端散块的区间，同时也可以找到中间的整块区间了。

对于处理修改问题，我们可以和查询一样的解决方法，暴力处理两端散块，然后借助mark数组去记录整块的修改

void update(int l,int r,int k){
	if(bel[l]==bel[r]){//如果l,r在一个块里面，直接暴力改一下
		for(int i=l;i<=r;i++){
			arr[i]+=k;
			sum[bel[i]]+=k;
		}
	}
	else{//不在就处理散块，然后再处理整块，对于整块中间的数我们别先更新，用mark数组记录一下
		for(int i=l;i<=en[bel[l]];i++){
			arr[i]+=k;
			sum[bel[i]]+=k;
		}
		for(int i=st[bel[r]];i<=r;i++){
			arr[i]+=k;
			sum[bel[i]]+=k;
		}
		for(int i=bel[l]+1;i<bel[r];i++){
			mark[i]+=k;
            sum[i]+=k*(en[i]-st[i]);//对于整个块来说，增加了长度*k的大小
		}
	}
}

对于查询来说，原理和修改是一样的。

int query(int l,int r){
	int ans=0;
	if(bel[l]==bel[r]){
		for(int i=l;i<=r;i++){
			ans+=arr[i]+mark[bel[i]];
		}
	}
	else{
		for(int i=l;i<=en[bel[l]];i++){
			ans+=arr[i]+mark[bel[i]];
		}
		for(int i=st[bel[r]];i<=r;i++){
			ans+=arr[i]+mark[bel[i]];
		}
		for(int i=bel[l]+1;i<bel[r];i++){
			ans+=sum[i];
		}
	}
	return ans;
}

现在，你已经解决了这个问题，在别人还在改线段树懒标记的时候你都已经过了这道题了，纯暴力，真的是不带脑子都能写的代码，而且出问题特别好改出来，非常非常暴力，但是优雅。

不过在不是这个方法的魅力之处，它能处理的问题要比这多，而且它能解决线段树，树状数组没法解决的问题。比如说解决区间[l,r]小于c有多少个数，如果线段树来写，对每一个c来说，都得建立一个线段树？那怎么修改？即使能解也比较麻烦，但是分块可以不带脑子的解决。我打算以hzwer分块九讲更新一下博客，下一篇我更新如何解决这个问题。

本人分块入门是看知乎的一个博主入门的，他的算法博客真的很全也很好，本文也很受他影响，推荐一下他的博客