分块入门的9道题目

分块的9题是参考黄学长的博客完成的，这大概可以算作真正的入门了。
例题1：给定一个长度为n的数列，以及n个操作，操作包括对区间进行加法运算，以及查询单个点的值。
题解By hzwer：
这道题目是可以通过多种数据结构进行优化的经典问题，适合用来训练不同种类的数据结构。分块处理的基本思想是将数列中的每个m个元素打包成一组，从而提升算法效率。以本题为例，若将每m个元素划分为一块，则总共有n/m块。每次执行区间加法操作时，会涉及O(n/m)个完整的块和两个不完整的块中最多2m个元素。我们为每个块设置一个加法标记（即记录该块内所有元素被整体增加的数值），在每次操作中对每个完整块直接进行O(1)时间复杂度的操作添加标记；而对于不完整的块，则由于其中元素数量较少，直接暴力修改每个元素的值即可。当需要查询某个点的值时，则将其原始值与其所在块的加法标记相加得出结果。这样每次操作的时间复杂度为O(n/m)+O(m)，根据均值不等式可知，当m取√n时总的时间复杂度最低。为了方便起见，在后续内容中默认分块大小为√n。
作为第一道题，理解了分块的基本思路与基础处理方式。
分块的方式主要有两种：

1. 块大小固定（所有区块大小一致），通常选择一个接近sqrt(maxn)的数值；
2. 块大小不固定（针对每个区块单独计算sqrt(n)）。

目前尚未尝试过第二种写法，