数据结构与算法_分块

    树状数组和线段数组最然非常方便，但维护的信息必须满足信息合并特性（如区间可加，可减），如果不满足此特性则不能使用树状数组和线段树。分快算法可以维护一些线段树维护不了的东西，分块算法就是优化过后的暴力。分块是一个很暴力的算法，它可以完成几乎所有区间更新和查询的问题，但效率相对于线段树等数据结构要差一些。

    分块算法是将数据分成若干个块，维护块内信息，使得块内的查询时O(1) 的时间，而总的询问就可以看作若干个块询问的总和。

    分块算法将长度为 n 的序列分成若干块，每一块有 k 个元素，最后一块可能少于 k 个元素。为了使时间复杂度均摊，通常将块的大小设为 k = n^(1/2), 用 pos[i] 表示第 i 个位置所属的块。对于每个块都进行信息维护。

1. 预处理

2. 区间修改

3. 区间查询