C++ 代码

/*
 * @Brief: 802 区间和 + 离散化
 * @Author: 
 * @Date: 2020-09-02 
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

const int N = 1e5 + 5;

typedef long long ll;

ll q[3*N]; // 树状数组  最多有这么多点  因为n次操作 每次 有一个坐标，最多N个点，m次查询，每次2个坐标，最多2N个点， 所以共3*N个点
int n, m, nodeNum; // 节点数量 操作次数
unordered_map<int, int> mp; // 映射关系

int lowbit(int x){
    return x & -x;
}

void update(int i, int k){
    while(i <= nodeNum){
        q[i] += k;
        i += lowbit(i);
    }
}

ll getSum(int i){
    ll res = 0;
    while(i > 0){
        res += q[i];
        i -= lowbit(i);
    }
    return res;
}

ll getRange(int l, int r){
    return getSum(r) - getSum(l - 1);
}

void solve(){
    // code
    // 用树状数组 因为要操作某个位置
    // 先把点都存起来 然后做离散化  再做插入和查询等操作
    cin >> n >> m;
    vector<int> node;  // 离散化后的点
    vector<pair<int, int> > querys, add;  // 存储操作

    // 保存n次op
    for(int i = 0; i < n; i++){
        int x, c;
        cin >> x >> c;
        node.push_back(x);
        add.push_back({x, c});
    }

    // 保存m次询问
    for(int i = 0; i < m; i++){
        int l, r;
        cin >> l >> r;
        node.push_back(l);
        node.push_back(r);
        querys.push_back({l, r});
        //cout << getRange(mp[l], mp[r]) << endl;
    }

    // 排序
    sort(node.begin(), node.end());
    //去重
    node.erase(unique(node.begin(), node.end()), node.end());
    // 离散化结束
    nodeNum = node.size();   // 总共离散的点数

    // 建立映射关系
    for(int i = 0; i < node.size(); i++){
        mp[node[i]] = i + 1;  // 从1开始映射
    }

    // n次op
    for(int i = 0; i < add.size(); i++){
        update(mp[ add[i].first ],  add[i].second );
    }

    // m次query
    for(auto tmp : querys){
        cout << getRange(mp[tmp.first], mp[tmp.second]) << endl;
    }

}

int main(int argc, char const *argv[]){

    solve();
    return 0;
}