数据结构-分块学习笔记

分块

我们以P3372 【模板】线段树 1 - 洛谷为模板讲一下
概览

首先，严格意义上将分块并不是一种数据结构，而是一种思路
顾名思义，就是把一个东西分成很多个块，一个块一个块遍历
所以分块就是一种优雅的暴力，只是把一个一个遍历变成了多个多个遍历
预处理操作

首先，要进行分块
块太多或者块太少都会影响时间，所以这里每个块有 \(\sqrt n\) 个元素
然后并不是每一个数都是完全平方数，所以最后多出来的一小部分单独成块
那么，我们需要记录一下每一个块的首尾节点
可以发现，右端点实际上就是 \(i\sqrt n\)，那么左端点就可以用上一个右端点加一得到
同时，最后一个要特殊处理，因为我们只有 \(n\) 个元素
[code]int len=sqrt(n);//每一块的数量int num=n/len;//块数if(n%len!=0){        num++;//不为完全平方数特殊判断}for(int i=1;i