C++: 区间和 - 使用差分数组高效求解

题目描述\n\n假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。\n\n现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。\n\n接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和\n\n输入格式\n\n第一行包含两个整数 n 和 m。\n\n接下来 n 行，每行包含两个整数 x 和 c。\n\n再接下来 m 行，每行包含两个整数 l 和 r。\n\n输出格式\n\n共 m 行，每行输出一个询问中所求的区间内数字和。\n\n样例 #1\n\n### 样例输入 #1\n\n\n3 3\n1 2\n3 6\n7 5\n1 3\n4 6\n7 8\n\n\n### 样例输出 #1\n\n\n8\n0\n5\n\n\n提示\n\n$-10^9≤x≤10^9 ,$\n\n$1≤n,m≤10^5,$ \n\n$-10^9≤l≤r≤10^9,$ \n\n$-10000≤c≤10000$\n\n解题思路\n\n题目要求在区间[l, r]内求和，而每次操作是将某个位置x上的数加上c，可以使用差分数组来解决这个问题。\n\n首先，创建一个长度为n+1的数组diff，用来存储每个位置上的数的差值。初始时，所有位置上的数都是0，所以diff数组中的所有元素都是0。\n\n然后，对于每个操作，将x位置上的数加上c，可以通过diff[x] += c来实现。这样，diff数组中的元素就表示每个位置上的数的差值。\n\n接下来，需要对diff数组进行前缀和处理，即对于每个位置i，将diff[i]的值更新为diff[i] + diff[i-1]。这样，diff数组中的元素就表示每个位置上的数的前缀和。\n\n最后，对于每个询问，将区间[l, r]内的数求和，可以通过计算diff[r] - diff[l-1]来实现。注意，当l等于1时，l-1会越界，所以需要单独处理。\n\n时间复杂度分析\n\n对于n次操作，需要更新diff数组，时间复杂度为O(n)。\n\n对于m次询问，需要计算区间和，时间复杂度为O(m)。\n\n因此，总的时间复杂度为O(n+m)。