C++# 区间和## 题目描述假定有一个无限长的数轴数轴上每个坐标上的数都是 0。现在我们首先进行 n 次操作每次操作将某一位置 x 上的数加 c。接下来进行 m 次询问每个询问包含两个整数 l 和 r你需要求出在区间 lr 之间的所有数的和## 输入格式第一行包含两个整数 n 和 m。接下来 n 行每行包含两个整数 x 和 c。再接下来 m 行每行包含两个整数 l 和 r。## 输出格式共 m

解题思路

题目要求在区间[l, r]内求和，而每次操作是将某个位置x上的数加上c，可以使用差分数组来解决这个问题。

首先，创建一个长度为n+1的数组diff，用来存储每个位置上的数的差值。初始时，所有位置上的数都是0，所以diff数组中的所有元素都是0。

然后，对于每个操作，将x位置上的数加上c，可以通过diff[x] += c来实现。这样，diff数组中的元素就表示每个位置上的数的差值。

接下来，需要对diff数组进行前缀和处理，即对于每个位置i，将diff[i]的值更新为diff[i] + diff[i-1]。这样，diff数组中的元素就表示每个位置上的数的前缀和。

最后，对于每个询问，将区间[l, r]内的数求和，可以通过计算diff[r] - diff[l-1]来实现。注意，当l等于1时，l-1会越界，所以需要单独处理。

时间复杂度分析

对于n次操作，需要更新diff数组，时间复杂度为O(n)。

对于m次询问，需要计算区间和，时间复杂度为O(m)。

因此，总的时间复杂度为O(n+m)。