区间和（离散和）

blablabla

样例

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

算法1

离散化 $O(n)$

离散化，把无限长的数组缩小到有限的范围里，关键是把有用的坐标先放到一个vector里，再映射到一个数组a里。
例如：样例中
1 2
3 6
7 5
1 3
4 6
7 8
插入得坐标分别是 1 3 7 ，插入的查询坐标分别是 1 3 4 6 7 8， 插入到res vector里面。vector: 1 3 7 1 3 4 6 7 8
sort 后 1 1 3 3 4 6 7 7 8

通过find 二分查找的方法，返回值 >= x的下标,又因为要查询的值都已经插入进了vector里，所以肯定会存在x。

find(1) -> 1, find(3) -> 2 , find(7) -> 3.... 返回的坐标存放到a[]里

这样就相当于把无限长的数组有用的值映射到了a[]里。

时间复杂度

参考文献

基础算法模板

C++ 代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef pair<int, int> PII;
/*要用到的数组最长度最大时n + 2m*/
const int N = 3e5 + 10;
vector<PII> add;
vector<PII> query;
vector<int> res;//储存所有待离散化的值的下标。
int a[N], s[N];
/*返回第一个比》= x 的下标*/
int find(int x){
    int l = 0, r = res.size() - 1;
    while(l < r){
        int mid = r + l >> 1;
     if(res[mid] >= x)r = mid;
     else l = mid + 1;
    }
    return r + 1;//把原来值得坐标映射到了1,2,3.....
}
int main(){
    int n, m;
    cin >> n >> m;
    while(n--){
        int x, c;
        cin >>x >> c;
        /*每次插入查询的坐标，和值*/
        add.push_back({x, c});

        res.push_back(x);
    }
    while(m--){
        int l ,r;
        cin >> l >> r;
        query.push_back({l ,r});
        res.push_back(l);
        res.push_back(r);
    }
    /*把插入和查询的坐标放到数组res里面。*/
    /*插入操作,find操作返回在res数组中值为item.first的映射下标（1,2,3...）.*/

    sort(res.begin(), res.end());//排序，便于二分查找。
   /* res.erase(unique(res.begin(), res.end()), res.end());*/
    for(auto item : add){
        int x = find(item.first);
        a[x] += item.second;
    }
    /*a[]存放了原数组，s[]存放前缀和，通过s[r] - s[l - 1] 就是某一区间数字和。*/
    for(int i = 1; i <= res.size(); ++i){
        s[i] = s[i - 1] + a[i];
    }
    //查询操作
    for(auto item: query){
        int l = find(item.first);
        int r= find(item.second);
        cout << s[r] - s[l - 1]<< endl;
    }
    return 0;
}