早上看了一下七中王迪大神写的一篇论文，学习了一下分块思想，只看了一点点，基本上是看着代码，再自己脑补的。

所谓分块就是把规模为n的问题分割成k块，每块规模为s，为了使对块内和整个范围的操作的复杂度平均些，令k = s = √n。利用这个思想就能把O(n)的复杂度降到O(√n),从而达到优化算法的目的。论文中如是说。

只看了一个简单的问题，如有一长度为n的正整数数列，完成m次操作（1≤n，m≤10 ˆ5），M x y:把第x个数字修改为y；Q x y：询问区间 [x,y] 中的最大值Max。

这个问题相当经典，有多种算法可解，因为在学分块，自然采用块状解决之。
Continue reading