区间和 - 离散化

比如有序列:

假如下标从1开始,让你计算区间$[a[2], a[3]]$的和。这时候数组无法简单做到,因为第二第三的数字远远超过了$10^5$,数组超过了最大的界,因此我们要做离散化。

简单来讲,比如你要有n个插入操作,每次插入提供两个值,一个是插入的位置,一个是插入的值为多少。但插入的位置可能超过$10^5$,这个时候用数组就不能统计区间和了,我们需要对这个数组进行离散化处理:

image-20221101235307493

这里就是在位置1插入2,在位置3插入6,在位置7插入5。然后有三次查询,第一次查询是统计位置1到3的区间和,第二次是4到6,第三次是7到8。

为了创建一个离散化的数组,我们需要先讲插入操作和查询操作用两个数组先保存起来。然后我们定义alls数组,存储这两个操作所涉及到的位置。为了防止alls数组混乱,这个数组不能有重复,而且从小到大排序。为了在之后的操作中,能够找到alls内的位置,我们可以采用二分查找。

alls数组初始化之后,我们可以开始离散化处理了。创建离散化后的数组a,然后:

遍历插入操作的数组,每次寻找插入操作中真实下标的离散化后下标(二分查找得到),然后将离散化下标对应的离散化后数组加上对应的数字。以此类推。

最后查询也是同理,然后利用前缀和就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PAIR;
const int MAXN = 300010;
int n, m; //n次插入,m次查询

// 加入队列、查询队列
vector<PAIR> add_query, search_query;
// 离散化时要用到的辅助数组,alls存储着真实下标,alls的自身下标就是离散化后的下标
vector<int> alls;
int a[MAXN], s[MAXN]; //离散化后的数组和对应的前缀和

//寻找x所在的离散化后位置,并返回下标+1,加1是因为我们的下标从1开始(这里是映射过程)
int find(int x) {
int l = 0, r = alls.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}

int main() {
cin >> n >> m;
//n次插入
for(int i = 0; i < n; i++) {
int x, c;
cin >> x >> c;
// x是真实下标,c是加上的数字
add_query.emplace_back(x, c);
alls.push_back(x);
}
//m次查询
for(int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
search_query.emplace_back(l, r);
//查找的下标也要push进去,不然的话计算前缀和的时候就找不到下标了
alls.push_back(l);
alls.push_back(r);
}
//去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
//处理插入,寻找离散化后的下标
for(auto item : add_query) {
int x = find(item.first);
a[x] += item.second;
}
//计算前缀和,注意离散化后的数组大小就是alls的,因为alls存储的是真实下标,所以这个数组的大小就是a的数组大小
for(int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
//处理询问,前缀和的做法
for(auto item : search_query) {
int l = find(item.first), r = find(item.second);
cout << s[r] - s[l - 1] << endl;
}
}
Author

InverseDa

Posted on

2021-03-18

Updated on

2023-03-30

Licensed under

Comments

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×