把一个大范围的稀疏数据映射到一个下标连续的数组上，需要解决一个关键问题：高效查到原数组中的a[i]被映射到新数组b中的那个位置

有两种高效的方式：
时间复杂度为O(1)，空间复杂度为O(N)的哈希
时间复杂度为O(logN)，空间复杂度为O(1)的二分

二分 lower_bound

#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
int a[N], s[N];
vector<pair<int,int>>add, query;
vector<int> alls;
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    while(n--) {
        int x, c;
        scanf("%d%d", &x, &c);
        alls.push_back(x);
        add.push_back({x, c});
    }
    while(m--) {
        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 pir : add) {
        int i = lower_bound(alls.begin(), alls.end(), pir.first) - alls.begin() + 1;
        a[i] += pir.second;
    }

    // 求前缀和
    for (int i = 1; i <= alls.size(); i ++)
        s[i] = s[i-1] + a[i];
    for (auto pir : query) {
        int l = lower_bound(alls.begin(), alls.end(), pir.first) - alls.begin() + 1; 
        int r = lower_bound(alls.begin(), alls.end(), pir.second) - alls.begin() + 1; 
        printf("%d\n", s[r] - s[l-1]);
    } 
    return 0;
}

哈希

#include <bits/stdc++.h>

using namespace std;
const int N = 300010;
int a[N], s[N];
vector<pair<int,int>>add, query;
vector<int> alls;
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    while(n--) {
        int x, c;
        scanf("%d%d", &x, &c);
        alls.push_back(x);
        add.push_back({x, c});
    }
    while(m--) {
        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()); // 去重

    unordered_map<int, int > mp;
    for (int i = 0; i < alls.size(); i ++) {
        mp[alls[i]] = i + 1;
    }

    for (auto item : add) {
        // x.first 是下标， x.second 是值 
        int i = mp[item.first];
        a[i] += item.second;
    }

    // 求前缀和
    for (int i = 1; i <= alls.size(); i ++)
        s[i] = s[i-1] + a[i];
    for (auto item : query) {
        int l = mp[item.first]; 
        int r = mp[item.second];
        printf("%d\n", s[r] - s[l-1]);
    } 
    return 0;
}