我觉得第二张图的index可以优化一下
alls[]数组的index还是从0开始，而a[]数组和s[]数组的index从1开始。
不过作者写的已经特别详细啦，感谢分享！

谢谢你~要不然我还蒙在鼓里(//̀Д/́/)

orz, 贴一个不用find 的， 用哈希表记录下标

// 思路 ： 因为范围太大， 所以不能开一个大数组
//开一个小数组 : 范围就是 add(index) + question(index) ， 两者的范围， 排序去重
//我们在index + c, 就是要在新数组的新下标下标操作

#include<bits/stdc++.h>
using namespace std;

const int N = 1000010;
int a[N], s[N]; 
typedef pair<int, int> pii;
int main() {
    int n, m;
    cin >> n >> m;
    vector<pii> add, query;
    vector<int> all;
    for(int i = 0; i < n; i++) {
        int l , r;
        cin >> l >> r;
        add.push_back({l, r}); // 存储单独一个 
        all.push_back(l); 
    }

    for(int i = 0; i < m; i++) {
        int l , r;
        cin >> l >> r;
        all.push_back(l);
        all.push_back(r);
        query.push_back({l, r});
    }

    sort(all.begin(), all.end());
    all.erase(unique(all.begin(), all.end()), all.end()); // 去重

    unordered_map<int, int> get_index;
    //获取新下标
    for(int i = 1; i <= all.size(); i++)  get_index[all[i - 1]] = i; // 注意这里 all[i - 1] , 不是i 

    for(int i = 0; i < add.size(); i ++){
        int old_index = add[i].first;
        int c = add[i].second;
        int new_index = get_index[old_index];

        a[new_index] += c;

    }

    for(int i = 1; i <= all.size(); i++){
        a[i] += a[i - 1];
    }

    for(auto p : query) {
        int l = p.first, r = p.second;
        int l2 = get_index[l], r2 = get_index[r];
        cout << (a[r2] - a[l2 - 1]) << endl;
    }

} 

写的不错，我也觉得用unordered_map比find()更直观。
不过输入n组数据时，我觉得用x和c比l和r更好，后者看起来像坐标…
另外，定义的前缀和数组s[N]似乎没用到，你直接用了a[N]覆盖掉充当前缀和数组，感觉用s[N]更清楚些。

为什么要去重啊，我没有去重也能过得？

 //处理插入
    for(auto item:add)
    {
        int x=get_index.at(item.first);//通过一个元素找到哈希表的另一个元素
        a[x]+=item.second;
    }
    //处理前缀和
    for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];
    //处理询问
    for(auto item:query)
    {
        int l=get_index.at(item.first);
        int r=get_index.at(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }

贴一个用上s[N]数组的代码

废话（doge）
去没去重不影响最后的答案，事实上如果不选择去重，最后的运行时间还会少一些
测了一下，去重的版本跑了610+ms，没去重的反而只跑了580+ms

分析
以答主给出的代码为例
对于每个询问中给定的x和c，查找到的结果都是alls数组中x的左端点xl(例如，序列：1、1、2中元素1的左端点为0)
且每次都只会a[xl]上的元素操作，这意味着若alls中有一些下标：a1、a2、a3…ak，满足alls[a1] = alls[a2] = .... = alls[ak]
最后所有的操作都必定只会影响a[a1]，因为a[a1]是左端点元素
因而，对于s中满足：alls[k1] = alls[k2] = .... = alls[kn]的连续下标:k1、k2…kn，只有a[k1]不等于0，其他下标的元素都为0

所以这种情况下，没有去重和去重之后每次询问得到的结果是一样的

再举个栗子

假设排序之后的alls是：1、1、3、3、4

去重之后是：1、3、4

执行操作“将x=1的元素加上2”后a数组是：2、0、0（索引从1开始计数）

前缀和数组应为：0、3、6、10（最开始的数值0代表没有元素被考虑累加的情况）

这时如果给出一个询问——l = 1， r = 3

那么find(l) = 1, find(r) = 2

所以结果为s[2] - s[1 - 1] = s[2] - s[0] = 6

而如果不去重呢？

此时alls是：1、1、3、3、4
执行操作“将x=1的元素加上2”后a是：2、0、0、0、0

前缀和数组应为：0、3、3、6、6、10

这时如果给出一个询问——l = 1， r = 3

那么find(l) = 1, find(r) = 2

所以结果为s[2] - s[1 - 1] = s[2] - s[0] = 6

前后结果保持不变

find(r)应该等于3吧

对，当时写错了O.O

没去重的话，那么重复的alls里面的数值会多次映射到数组a里面。但是我们二分分出来的是最左边的值，也就是说诸多重复的数值，只有最左边的数值的坐标映射到数组a里面，其余重复的数值映射的值都为0（显然会增加数组a的长度，占用空间）。仅仅是增加了数组a的长度，那自然不会影响前缀和的值

清晰易懂 我认为比前两个题解更好 tql

+1

确实，这篇画图讲解太清晰了

雀氏

yyds

+1

为什么alls要存储l与r呢？
答：我们最终要对[l, r]求和，自然就不能使用原来的数组求和(数据太大，过于离散)。
所以我们把l和r也映射到alls数组(l,r的值若没有add的操作，即插入不会在l或r的位置，值就为0(全局变量的默认值为0))。这样数轴就会变短很多(最大到3*10^5)，我们就可以使用前缀和求和达到O(1)。

图解太棒了呀，赞

太棒了这个图。清晰易懂，大佬我可以搬一个到我打卡里面吗！！？

感谢哥，爱你

为什么要将所需要使用的坐标进行排序和去重呢

我是这样理解的 all数组存放的是下标 既然是下标 那每一个下标都是唯一的 所以去重 排序是因为要使用二分查找 所以需要排序 不知道对不对😂

楼上看了一个帖子 可以不用去重

去重之后二分比较方便。（类似地，把查询操作里的 l 和 r 也一起维护进去，同样是方便写二分）
上述两点分别确保了我们查询的值 唯一 & 存在。这样在写二分时就可以统一按照 <x 和 >=x 划分区间，找右侧分界点，此时该分界点一定就是那个值。假设没有唯一或者存在的前提，二分查找时就要额外考虑一些问题了。

排序的话，是因为我们需要维护下标的全序关系。以这个题为例，它涉及到区间操作，所以我们要确保下标映射之后的顺序还是一样的。所以这里的因果关系是，进行了排序 -> 可以用二分查找。如果这里用 map 而不是二分的话，也是一样需要排序的。

讲的太透彻了，我想搬到我自己的博客可以么？？追加链接嘿嘿

这道题解写的最好

真厉害啊大佬，我测，我看了五天，看到你这一篇题解，真的突然明白了，太感谢了啊
，

这个是什么意思啊for (auto item : query) {

从头遍历query里面的所有元素，简单来说item=query[i]

这个为啥要排序去重啊

大佬牛p!!!

niubi

写的太棒了，二刷我原本也打算写个题解，一看你的觉得完全没有写的必要了。

请问这个alls代表哪个英文单词啊，百思不得其解。

all+s,全部的

这图太清晰了吧 谢谢

恩比，画图确实清晰多了

我爱你