分块
分块
由于我在网上找不到定义，只好编一个。
分块 是一种将问题分解成若干个子问题，逐项解决子问题后得到原问题答案的思想。
块
考虑这样一个问题。
你有一个序列 \(a[1…N]\)，你需要写一个数据结构维护它，支持以下操作：
- 修改 \(a[x]\) 的值；
- 查询 \(a[L…R]\) 的最大值、和、按位与和、或和、异或和、与非和、或非和、异或非和。
事实上，这道题可以加上很多很多个操作，这样 线段树 也无能为力了。
我们不妨想想如何优化朴素程序。
以求和为例，朴素程序写法如下：
for(int i=L;i<=R;++i)
ans+=a[i]; //flagflag 行一共被执行了 \(R-L+1\) 次，这不是我们希望看到的。
如果是这样写呢？
for(int i=L;i<=R;i+=2)
ans+=a[i]+a[i+1]; //flag
if((R-L+1)&1) ans-=a[R+1];不难想到，flag 行只被执行了原来次数的一半。
设 flag 行将连续的 \(d\) 个 \(a\) 累加给 \(ans\)，则一共需要执行 flag 行 \(\frac{R-L+1}{d}\) 次。
如果我们用一个变量维护这 \(d\) 个数，那么我们查询的时间复杂度就是 \(O(\frac{R-L+1}{d})\)，修改操作的时间复杂度是 \(O(d)\)。
不妨令两操作次数相同，则程序有最低复杂度时，\[\frac{R-L+1}{d}=d\]即\[d=\sqrt{R-L+1}\]
换言之，当 \(d\) 的值等于操作区间（一般是 \([1,N]\)）的 \(\frac12\) 次方时，该程序的时间复杂度最低，是 \(O(N^\frac12)\)（单次执行）。
我们不妨将被一并处理的 \(d\) 个数视作一块，那么原区间就被分成了 \(\sqrt N\) 块。
至此， 分块 已经介绍完毕了。下面我们看几道例题。
例题 1 您需要设计一种数据结构，维护一个序列 \(a[1…N]\)，支持以下操作：
- 将 \(a[x]\) 的值加 \(d\)；
- 查询 \(a[L…R]\) 中小于等于 \(d\) 的数的个数。
例题 2 您需要设计一种数据结构，维护一个序列 \(a[1…N]\)，支持以下操作：
- 将 \(a[L…R]\) 的值加 \(d\)；
- 查询 \(a[L…R]\) 中小于 \(a[x]\) 的最大的数。
例题 3 您需要设计一种数据结构，维护一个序列 \(a[1…N]\)，支持以下操作：
- 将 \(a[L…R]\) 的值加 \(d\)；
- 查询 \(a[L…R]\) 的数的和。
例题 4 您需要设计一种数据结构，维护一个序列 \(a[1…N]\)，支持以下操作：
- 将 \(a[L…R]\) 的值开方（向下取整）；
- 查询 \(a[L…R]\) 的数的和。
例题 5 您需要设计一种数据结构，维护一个序列 \(a[1…N]\)，支持以下操作：
- 将 \(a[L…R]\) 的值加 \(d\)；
- 将 \(a[L…R]\) 的值乘 \(d\)；
- 查询 \(a[L…R]\) 的数的和。
例题 6 您需要设计一种数据结构，维护一个序列 \(a[1…N]\)，支持以下操作：
- 查询 \(a[L…R]\) 的数有多少个与 \(d\) 相等。将 \(a[L…R]\) 的每个数改成 \(d\)。
例题 7 您需要写一种数据结构，维护一个有序数列，支持以下操作：
- 查询 \(k\) 在区间内的排名；
- 查询区间内排名为 \(k\) 的值；
- 修改某一位值上的数值；
- 查询 \(k\) 在区间内的前驱(前驱定义为严格小于 \(x\)，且最大的数)；
- 查询 \(k\) 在区间内的后继(后继定义为严格大于 \(x\)，且最小的数)。