下载掌阅APP，畅读海量书库
立即打开
题目描述（POJ3648）： 有 N 个整数 A 1, A 2, …, AN ，需要对其进行两种操作，一种操作是对给定区间中的每个数都添加一个给定的数，另一种操作是查询给定区间中数的总和。
输入： 第1行包含两个数 N 和 Q （1≤ N ， Q ≤10 5 ）；第2行包含 N 个数，为 A 1 , A 2 , …, A N 的初始值（-10 9 ≤ A i ≤10 9 ）；接下来的 Q 行，每行都表示一种操作，“C a b c ”表示将 A a , A a +1 , …, A b 中的每一个数都加 c （-10 4 ≤ c ≤10 4 ），“Q a b ”表示查询 A a , A a +1 , …, A b 的总和。
输出： 对每个查询，都单行输出区间和的值。
提示： 总和可能超过32位整数的范围。
题解： 本题有区间更新和区间查询两种操作。
（1）创建线段树，每个节点都存储区间信息[ l , r ]及区间和val 。
（2）区间查询，在查询区间和的过程中若有懒标记则下传。
（3）区间更新，先查找区间，再更新区间和并打懒标记，在查找过程中若有懒标记则下传。
