--- title: "区间和" created: 2025-11-28 tags: - 算法 --- # 区间和 ## 题目 [区间和](https://www.acwing.com/problem/content/804/) ![[image-954a21c1.png]] ## 思路分析 乍一看就是求前缀和嘛 ![[image-2c947462.png]] 但是数轴上基本是0 而且长度为20^9 想直接构建前缀和数组不现实 所以得先将这个数轴离散化成一个较小的数组 然后再对这个数组进行求前缀和操作 根据前面的思路 就是要把有意义的值所对应的下标记录在这个alls数组里面呗 但是还不够吧 它后面还要找区间 这个l和r又不一定是在有意义的值上 比如 00010004 01234567 要找1~5怎么办 如果没记录1下标和5下标就没法找了 所以这里还需要记录l和r进入alls数组里面去 小捋一下——记录有意义的值所在的下标以及l的下标r的下标 嗯 看到题目 n（有意义的值的范围） m（l，r的范围）都在10万内 所以最坏的情况就是全要记录 那应该是10万+10万+10万=30万 所以要开一个300010大的数组 ![[image-92a01f6f.png]] 有 1 3 7 0 3 4 6 7 8 这里就需要排序去重了 （前面的例子不需要 所以吧 为了统一 是吧 直接记得这个步骤就行了 只有好处没有坏处） 那么得到alls数组： 值 0 1 3 4 6 7 8 下标 0 1 2 3 4 5 6 接下来就是 映射 变成有意义的数组 find做的事情就是构建一个数组a使得a的下标与alls的下标能进行对应 然后a中存储的是alls值所对应的原区间的相应下标内的值 注意的是 这里说的是a的下标与alls的下标对应 不一定要完全一样（前面的例子是完全一样 但是可以根据需求做一些修改） 比如这里我们要把01234 映射到12345 因为我们的目的是求前缀和 而前缀和问题我们知道 如果0号位置不用的话 就可以使用同样的s[r]-s[l-1]去求到0~n的区间和 而不需要考虑特殊情况 所以 出于这种需求 我们将alls的下标映射成a中以1开始的下标 a数组为 值 0 2 6 0 0 5 0 下标 0 1 2 3 4 5 6 7 那么就可以对这个a数组很容易地求到前缀合数组s s数组 值 0 2 8 8 8 13 13 下标 0 1 2 3 4 5 6 7 这样求区间和就很容易了 直接s[r]-s[l-1] ![[image-e1535e7d.png]] 这是整体的思路 应该很明了了 再考虑一些细节问题 在这过程中 我们要进行两个操作 add和query add呢 是在x位置插入c emm 先在原数轴上插入吗？然后我还得把它提出来 多此一举 我甚至可以不需要构建这个数轴 本来要做的就是把有意义值的下标记录在alls中 而数轴一开始的数据都是0 都是没意义的 而x就是有意义的值的位置 我直接把x存在alls里不就行了 然后add应该是有两个操作数的 x是要放在alls里面 c是有意义的值 要放在a里面 a是alls的下一步操作 先不着急 把add的操作数先存起来 到时候构造a的时候 find(x)找到映射的位置 再在该位置存入c就行了（准确来说是加上c 因为不排除同一位置加多次的情况 不应该是覆盖） 嗯 要把add的两个操作数做一个储存 再看query 它也是两个操作数 一个是l 一个是r 这个数据是在最后s[]才要用的 也先存起来 可以发现 add和query的操作数都是两个int 完全可以使用pair去进行保存 然后再存在vector中去 到这里问题基本解决了 再整理一下 要开几个30万+1的数组 存放所有要用的下标alls 、映射后的有意义的数组a[]、a[]的前缀和数组s[] 还要开两个pair类型的容器 存放add和query操作数 const int N=300010;//插入：10万 l：10万 r：10万 最大可能30万 int a[N],s[N];//a存的all中对应下标映射到原数轴对应的值 s为a求前缀和的数组 //存储（所有与插入和查询有关的）坐标 vector alls; //要进行两种操作 添加、查询 这两种操作都有两个数据 某位置插几、左右区间 //所以可以把这些待操作数作为一对pair来存入vector vector add,query; ![[image-82822ce8.png]] 要读入n,m int n,m; cin>>n>>m; 存入n条 x,c记录进入add中 以及把x（有意义的下标）存到alls中 for(int i=0;i>x>>c; add.push\_back({x,c}); alls.push\_back(x); } 然后是m次 构建query数组 这个l和r的下标也是要用的 所以也要加在alls中去 for(int i=0;i>l>>r; query.push\_back({l,r}); alls.push\_back(l); alls.push\_back(r); } alls中已经有了所有要用的下标了 但是这里面可能存在重复情况 所以 进行排序去重 //此时 alls数组中已经有了所有要用的下标 对它进行去重排序 sort(alls.begin(),alls.end()); //unique把不重复的放前面 重复了的放后面 返回不重复区间的末尾 //那么直接把unique返回的迭代器作为起始 把alls.end()为结束 //删除这部分 就实现了去重 alls.erase(unique(alls.begin(),alls.end()),alls.end()); alls数组构建好了 现在把它映射成a数组 在找到alls相应下标的同时 将add中的c放进去 没放的地方就默认是0了呗 其实就是对add进行一个遍历 //处理添加操作 for(auto item:add) { int x=find(item.first); a[x]+=item.second; } a[]构建完成了 然后就是构建前缀和数组s[] //把a[]做前缀和 得到s[] for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i]; 接下来就是处理查询操作 要查询的左右区间下标都放在query里面了 遍历query就行了 找到l、r的位置 去进行一个相减即可 //处理询问操作 for(auto item:query) { int l=find(item.first),r=find(item.second); cout< using namespace std; typedef pair PII; const int N=300010;//插入：10万 l：10万 r：10万 最大可能30万 int a[N],s[N];//a存的all中对应下标映射到原数轴对应的值 s为a求前缀和的数组 //存储（所有与插入和查询有关的）坐标 vector alls; //要进行两种操作 添加、查询 这两种操作都有两个数据 某位置插几、左右区间 //所以可以把这些待操作数作为一对pair来存入vector vector add,query; int find(int x) { //find做的就是让a数组的下标与alls数组下标对应 但是alls存的是下标 而a是有意义的值 int l=0,r=alls.size()-1; while(l>1; if(alls[mid]>=x) r=mid; else l=mid+1; } //这里映射为1完全是为了后面做前缀和操作 如果没这需求就直接一一对应就完事了 return r+1; } int main() { int n,m; cin>>n>>m; for(int i=0;i>x>>c; add.push_back({x,c}); alls.push_back(x); } for(int i=0;i>l>>r; query.push_back({l,r}); alls.push_back(l); alls.push_back(r); } //此时 alls数组中已经有了所有要用的下标 对它进行去重排序 sort(alls.begin(),alls.end()); //unique把不重复的放前面 重复了的放后面 返回不重复区间的末尾 //那么直接把unique返回的迭代器作为起始 把alls.end()为结束 删除这部分 就实现了去重 alls.erase(unique(alls.begin(),alls.end()),alls.end()); //处理添加操作 for(auto item:add) { int x=find(item.first); a[x]+=item.second; //注意这里 错两次了 他可能在同一个位置插入几次 所以是+= } //把a[]做前缀和 得到s[] for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i]; //处理询问操作 for(auto item:query) { int l=find(item.first),r=find(item.second); cout<