文章目录
前言
一、有关离散化
二、离散化例题，模板，代码详解
1.例题：AcWing 802. 区间和
2.例题分析：
遍历add数组：
find 函数:
处理前缀和数组：
3.例题模板
4.AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：离散化，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上.
一、有关离散化
什么时候我们会用离散化去解题：例如存在这么一条 x轴，这条 x轴十分的长，例如≥1e7级别，这条x轴上有一些数，但是这些数十分的分散，一个1e8长度的轴上可能只有1e3个数字，我们如果想求这条数轴上任意两点之间所有数字之和的话，如果把这条 x轴设成一个数组，然后利用for去遍历累加的话，那么我们需要开一个a[1e8]长度的数组，这样显然是不合理的。在这种情况下我们就可以采用离散化这一算法去解题。
离散化的本质就是映射，就是把那些散点（间隔很大的点），映射到一个数组中，比如一个a[100]的数组中，只有a[1] = 2, a[64] = 9，其余的点都是0，那么对于这么一个数组，我们可以通过离散化开一个新的数组b[3]，使得b[1] = 2, b[2] = 9，这样就省去了很多的空间，同时也省去了for循环遍历数组时的计算量，这里直接上例题去讲解
二、离散化例题，模板，代码详解
1.例题：AcWing 802. 区间和
本题链接：AcWing 802. 区间和
本博客给出例题截图：
2.例题分析：
本题的坐标轴为 [-1e-9, 1e9]，显然我们开个a[2e9]的数组是不合理的，而且这些坐标中最多也只有1e5个点，符合离散化算法的条件，本题的离散化利用了vector，关于有关vector的用法即介绍，见：STL—vector
首先来看要求[l, r]上的和，对于这一步的处理我们可以用前缀和去处理，前缀和的讲解在这篇博客：前缀和，所以我们需要一个前缀和数组s[N]，同时我们需要一个储存离散化后的点的数组a[N]，我们用vector去存储未离散化的坐标，往离散化前的坐标轴上加入一个值用pair类型的vector数组add去存储，关于pair的用法即介绍，见：STL—pair，同样用一个pair类型的vector数组query去存储要计算的[l, r]区间和的端点 l 和 r，然后把所有未离散化的坐标都存入到int类型的vector数组alls，那么alls里就是待离散化的所有坐标，全部处理结束后，我们需要对alls数组排序并去重，本题例子中的alls数组中存储的值为{1, 3, 7, 1, 3, 4, 6, 7, 8}，这个就是本题涉及的所有坐标（未离散化），排序后为{1, 1, 3, 3, 4, 6, 7, 7, 8}，显然我们对于一个坐标点只需要存储一次即可，故去重，关于本题排序并去重的代码如下图所示：（背过即可）
本代码板块来源：AcWing算法基础课
sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end());
处理完之后alls数组中的值为{1, 3, 4, 6, 7, 8}，时刻都要记住本vector数组alls存储的是未离散化后的值，接下来，处理离散化，例如:
遍历add数组：
for (auto it : add) { int x = find(it.first); //it.first存储的是add函数中的坐标 //find函数返回的是it.first离散化后的坐标 a[x] += it.second; }
find 函数:
查找一个数，我们可以利用之前说到的二分查找法，不懂的可以看这篇博客：二分法
本代码板块来自于AcWing算法基础课
// 二分求出x对应的离散化的值 int find(int x) // 找到第一个大于等于x的位置 { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; //因为是 r = mid 所以 mid = l + r >> 1; else l = mid + 1; } return r + 1; // 映射到1, 2, ...n //因为要利用前缀和数组，所以返回值从1开始 }
处理前缀和数组：
关于前缀和数组，可以看这篇博客：前缀和
for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];
3.例题模板
本代码模板来自于AcWing算法基础课，ACWing网站链接：AcWing
vector<int> alls; // 存储所有待离散化的值 sort(alls.begin(), alls.end()); // 将所有值排序 alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素 // 二分求出x对应的离散化的值 int find(int x) // 找到第一个大于等于x的位置 { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r >> 1; if (alls[mid] >= x) r = mid; //因为这里是r = mid，所以mid = l + r >> 1; else l = mid + 1; } return r + 1; // 映射到1, 2, ...n }
4.AC代码
这里解释一下为什么N = 300010，因为给 x轴上任意一个点加上一个值最多n次操作，所以在这一操作中最多用到1e5个坐标，之后有m次操作，每次操作要输入两个坐标 l 和 r，所以这一步操作中最多用到2e5个坐标，故一共要用到最多的坐标数量就是3e5，故开N = 300010;
#include <cstdio> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 300010; vector<int> alls; vector<PII> add, query; int a[N], s[N]; int find(int x) { int l = 0, r = alls.size() - 1; while (l < r) { int mid = l + r + 1 >> 1; if (alls[mid] <= x) l = mid; //这里是 l = mid，所以 mid = l + r + 1 >> 1; else r = mid - 1; } return l + 1; } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) { int x, c; scanf("%d%d", &x, &c); add.push_back({x, c}); alls.push_back(x); } for (int i = 0; i < m; i ++ ) { int l, r; scanf("%d%d", &l, &r); query.push_back({l, r}); alls.push_back(l); alls.push_back(r); } sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(), alls.end()), alls.end()); for (auto it : add) { int x = find(it.first); a[x] += it.second; } for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i]; for (auto it : query) { int l = find(it.first), r = find(it.second); printf("%d\n", s[r] - s[l - 1]); } return 0; }
三、时间复杂度
关于离散化的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
