初步认识分块算法
我实在太弱了,连分块算法都不知道,现在才学。
分块算法可以解决区间查询功能,可以替代线段树,代码量比线段树少。分块算法的思想是把原始数组分为多个大小相等的连续的块,每次对单个元素或整块操作,下面以求区间和为例。
初始化
分块一般需要以下变量:
1 | int v[MAXN]; //单个元素的值 |
根据某种数学公式可以得出分块每块的大小为sqrt(n)
时效率最高,不难写出以下代码:
1 | blo = sqrt(n); |
区间更新
分为三个步骤,单点更新l到下一个整块,更新中间的整块,单点更新最后剩下单点。箭头处代码处理l和r在同一块的特殊情况。
1 | void add(int64 l,int64 r,int64 x){ |
区间查询
类似区间更新,不要忘了lazy
1 | int64 query(int64 l,int64 r){ |
注意分块算法涉及for循环操作较多,经KING_LRL
提醒,i
使用register int
能有效提升速度。分块算法最坏情况时间复杂度为O(3*sqrt(n))。

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License
Permalink: https://duanyll.com/2018/10/22/Fenkuai-Algorithm/