数据结构-分块学习条记

分块

我们以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