区间和
题目 区间和
思路分析
乍一看就是求前缀和嘛
但是数轴上基本是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大的数组
有 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]
这是整体的思路
应该很明了了
再考虑一些细节问题
在这过程中 我们要进行两个操作
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;
要读入n,m
int n,m; cin>>n>>m;
存入n条 x,c记录进入add中 以及把x（有意义的下标）存到alls中
for(int i=0;i<n;i++){//在x处插入c 这个x为数轴有值的下标 要放入alls中
int x,c; cin>>x>>c;
add.push_back({x,c});
alls.push_back(x);
}
然后是m次 构建query数组 这个l和r的下标也是要用的 所以也要加在alls中去
for(int i=0;i<m;i++)
{
int l,r;//这俩下标都是要用的 所以也要放在alls中
cin>>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<<s[r]-s[l-1]<<endl;
}
结束
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=300010;//插入：10万 l：10万 r：10万 最大可能30万
int a[N],s[N];//a存的all中对应下标映射到原数轴对应的值 s为a求前缀和的数组
//存储（所有与插入和查询有关的）坐标
vector<int> alls;
//要进行两种操作 添加、查询 这两种操作都有两个数据 某位置插几、左右区间
//所以可以把这些待操作数作为一对pair来存入vector
vector<PII> add,query;
int find(int x)
{
//find做的就是让a数组的下标与alls数组下标对应 但是alls存的是下标 而a是有意义的值
int l=0,r=alls.size()-1;
while(l<r)
{
int mid=l+r>>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<n;i++)
{
int x,c;//在x处插入c 这个x为数轴有值的下标 要放入alls中
cin>>x>>c;
add.push_back({x,c});
alls.push_back(x);
}
for(int i=0;i<m;i++)
{
int l,r;//这俩下标都是要用的 所以也要放在alls中
cin>>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<<s[r]-s[l-1]<<endl;
}
return 0;
}
同类题型
视频讲解
📹 配套视频讲解：区间和（acwing 视频课，原网址 Trilium 导出时未保留，待回填）
💬 评论