802. 区间和

文章目录

• 题目描述
• • 输入格式：
  • 输出格式：
  • 数据范围
  • 输入样例
  • 输出样例
• 方法：离散化
• • 解题思路
  • 代码
  • 复杂度分析：

题目描述

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

输入格式：

第一行包含两个整数 n 和 m。

接下来 n 行，每行包含两个整数 x 和 c。

再接下来 m 行，每行包含两个整数 l 和 r。

输出格式：

共 m 行，每行输出一个询问中所求的区间内数字和。

数据范围

• −109≤x≤109,−10^9≤x≤10^9,−109≤x≤109,
• 1≤n,m≤105,1≤n,m≤10^5,1≤n,m≤105,
• −109≤l≤r≤109,−10^9≤l≤r≤10^9 ,−109≤l≤r≤109,
• −10000≤c≤10000−10000≤c≤10000−10000≤c≤10000

输入样例

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例

8
0
5

方法：离散化

解题思路

首先，我们看到题目要我们求一个区间 [l,r] 位置上的元素之和，心里不禁一喜，这不就用前缀和来做就可以了；
然后，一看数据范围就傻眼了，l 和 r 最大有 10910^9109，总不可能开这么大的数组吧，于是便引出了我们本题所要用到的算法：离散化；
离散化的本质：将数字本身 key 映射为它在数组中的索引 index(1 based). 通过二分求索引(value -> index)是离散化的本质。
由于用到的数字不止给出的这 n 个位置 x，还包括后面查询区间和所输入的 l 与 r. 把 x，l，r 全部存入容器 alls 中。
为什么存入容器中呢，而不用普通的数组来存放呢？
这是因为离散化首先要对这串数字排序再去重，而用 STL 函数可以直接实现。

sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());

然后后面要用到这串数字时，可以用二分来找到在 alls 中的位置。
最后定义两个整型数组，a 数组用来对应存放 alls 离散化后的值；s 数组用来存放 a 的前缀和。
某一区间和可以用 s[r] - s[l - 1] 求得。
小技巧：以后如果输入的数字，在后面的算法中，是要成对使用的，我们可以定义类型 pair，方便存取。

代码

#include 
#include 
#include using namespace std;typedef pair PII;const int N = 3e5 + 10;int n, m;
int a[N], s[N];vector alls;
vector add, query;int find(int x) {long long l = 0, r = alls.size() - 1, mid;while(l < r) {mid = (l + r) / 2;if(alls[mid] >= x)    r = mid;else    l = mid + 1;}return l + 1;
} int main() {cin >> n >> m;for(int i = 0; i < n; i++) {int x, c;cin >> x >> c;add.push_back({x, c});alls.push_back(x);}for(int i = 0; i < m; i++) {int l, r;cin >> l >> r;query.push_back({l, r});alls.push_back(l);alls.push_back(r);}// 使用库函数对 alls 去重sort(alls.begin(), alls.end());alls.erase(unique(alls.begin(), alls.end()), alls.end());// 处理插入for(auto item : add) {int x = find(item.first);a[x] += item.second;}// 预处理前缀和for(int i = 1; i <= alls.size(); i++)   s[i] = s[i - 1] + a[i];// 处理询问for(auto item : query) {int l = find(item.first), r = find(item.second);cout << s[r] - s[l - 1] << endl;}return 0;
}

复杂度分析：

• 时间复杂度：O(Nlog2N)O(Nlog_2N)O(Nlog2​N)
• 空间复杂度：O(N)O(N)O(N)