分块

参考资料

• 分块思想 - OI Wiki

例题

洛谷 P3372 【模板】线段树 1

如题，已知一个数列 $\{a_i\}$，你需要进行下面两种操作：

1. 将某区间每一个数加上 $k$。
2. 求出某区间每一个数的和。

洛谷 P2801 教主的魔法

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给 XMYZ 信息组每个英雄看。于是 $N$ 个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为 $1, 2, \dots, N$。

每个人的身高一开始都是不超过 $1000$ 的正整数。教主的魔法每次可以把闭区间 $[L, R]$（$1≤L≤R≤N$）内的英雄的身高全部加上一个整数 $W$。（虽然 $L=R$ 时并不符合区间的书写规范，但我们可以认为是单独增加第 $L(R)$ 个英雄的身高）

CYZ、光哥和 ZJQ 等人不信教主的邪，于是他们有时候会问 WD 闭区间 $[L, R]$ 内有多少英雄身高大于等于 $C$，以验证教主的魔法是否真的有效。

WD 巨懒，于是他把这个回答的任务交给了你。