分块感觉也没必要讲多了,人家hzwer讲得多好……%%hzw%%orz。
传送门

再贴个我写的分块区间增减、区间求和。
题目:洛谷P3372【模板】线段树 1 传送门

思想:把大小为n的数组分成√n块,每块含√n个元素。(因为把大小为n的数组分成√n块是最好的分法,具体怎么证我不知道~= ̄ω ̄=)然后对于每次修改区间[l,r],先单独处理l~l所在的块的末尾元素和r所在的块的开始元素~r,最坏情况复杂度使2×√n,然后中间的都是整块整块的块了,所以我们把每个块都做上懒惰标记就行了。(懒惰标记不知道的去看我的那篇线段树入门!)中间最多有√n块,所以整个操作的复杂度不会超过3×√n。查询也是一个套路,只不过要每次加上懒惰标记值。

代码: