#3709. 例2-区间更新与查询-差分2

例2-区间更新与查询-差分2

题目描述:
给定一个长度为 n 的数组(下标从 1 到 n,初始元素均为 0)。现在进行 m 次区间更新操作,每次操作对区间 [l, r] 的所有元素增加一个常数 v。操作完成后,再给出 q 个查询,每个查询要求输出区间 [a, b] 的所有元素之和。请你利用差分数组实现快速的区间更新和区间查询。

输入格式:

  • 第一行包含三个整数 nmq,分别表示数组的长度、操作次数和查询次数。
  • 接下来 m 行,每行包含三个整数 l r v,表示一次区间更新操作,将数组中下标在 [l, r] 范围内的所有元素加上 v
  • 接下来 q 行,每行包含两个整数 a b,表示一个查询,要求输出区间 [a, b] 的元素之和。

输出格式:

  • 对于每个查询,输出一行结果,表示对应区间的和。

样例输入:

5 3 2
1 3 2
2 5 3
3 3 1
1 5
2 3

样例输出:

19
11

样例说明:
初始数组:0 0 0 0 0

  • 操作 1:对区间 [1,3] 加 2 → 数组变为:2 2 2 0 0
  • 操作 2:对区间 [2,5] 加 3 → 数组变为:2 5 5 3 3
  • 操作 3:对区间 [3,3] 加 1 → 数组变为:2 5 6 3 3

查询:

  • 查询 1:区间 [1,5] 的和 = 2 + 5 + 6 + 3 + 3 = 19
  • 查询 2:区间 [2,3] 的和 = 5 + 6 = 11