【算法基础】1.8离散化

当数据范围的跨度很大但是数据很稀疏时可以使用离散化。

离散化

如何离散

数据范围很大但是并不是每个数字都会出现就可以将原始数据按照顺序映射到一个小的数据范围。

确定映射方式

按照顺序一对一的方式比如
原数据1, 3, 7, 8, 12, 1000, 99999
就可以映射成0123456
其中1->0, 3->1, 7->2, 8->3, 12->4, 1000->5, 99999->6。

如果原始数据有重复需要排序去重。

如何确定一个数字排在哪个位置呢可以使用二分。

区间和

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

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

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

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n, m;
int a[N], s[N];

vector<int> alls;
vector<PII> add, query;

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 l;
}

int main()
{
    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 (PII 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 - 1];
    
    // 处理询问
    for (PII item: query) {
        int l = find(item.first), r = find(item.second);
        printf("%d\n", s[r + 1] - s[l]);
    }
    return 0;
}

可能有读者会有疑问为什么需要二分呢直接排序好按顺序分配下标就好了呀。

这里是因为有 add 操作的存在在操作 add 时需要根据原数据直接得到其映射的下标位置。