当前位置：首页 > news >正文

AcWing 802. 区间和

news 2025/8/13 14:59:53

在这里插入图片描述

var	说明
add	存储了插入操作，在指定 $x$ 下标所在位置 $a [x] + = c$
query	是求 $[L, R]$ 区间和用到的数组,最后才用到
alls	$\\ ，会把x和[L,R]都丢到alls里面，不同的[L,R]有可能会重复输入，\\ 比如询问[4,6],[4,9]的区间和,因此有必要去重，调用alls.erase$
find	$在alls里面二分查找\\返回r+1是想要做前缀和，下标要从1开始算，直接return \,\,\,\, r会把下标从0开始算\\return \,\,\,r+1就是r\ge0,find返回值是\ge1,返回值从1开始算$

思路：
把不同的 $\forall i\in [0,m-1]把[L,R]_i$ 区间输入到 $q u ery$

把不同的 $\forall i\in [0,n-1]把\{x,c\}_i$ 输入到 $a dd$

把不同的 $\forall i\in [-\inf,\inf]把会访问到的坐标轴的下标位置idx_i$ 输入到 $a ll s$ ,
$idx_i来自于[L,R]_i的L和R还有\{x,c\}_i里面的x$ ，就这三个来源

1.应用离散化的方法初始化query，add和alls
2. $a 在 x 位置加上 c ，先把 x 位置通过 f in d 函数得到离散化之后的坐标 i d x ，然后 a [i d x] + = c, 完成 + = c$
3. $对 a 求前缀和存到 b 里面$
4. $遍历query，\\对于每个pair<int,int> 类型的[L,R]_i,我们也是要先分别通过find函数分别获取L，R在离散化之后的下标\\然后根据离散化之后建立的前缀和数组b，来直接求区间和！$
总结：
题目要求区间和，然后可以用前缀和解决问题，但是这个问题是如果直接开辟一个巨大的数组然后在许多是0的位置反复计算+=0会很费劲，然后可以用离散化的方法减少计算量，只在需要访问的下标位置+=c，减少计算量，降低时间复杂度。
时间复杂度分析：
vector.erase的复杂度是 $O (k) ， k 是重复的元素$
二分查找是 $O (l o g n)$
排序是 $O (n l o g n)$
然后求前缀和是 $O (n)$
总得来说是 $O (n l o g n) + O (k) = O (n l o g n)$

#include<algorithm>
#include<iostream>
#define N 300086
using namespace std;
int n,m,x,a[N],b[N];
typedef pair<int,int> PII;
vector<PII> add,query;
vector<int> alls;
//在alls里面二分查找
//返回r+1是想要做前缀和，下标要从1开始算，直接return r会把下标从0开始算
//return r+1就是r≥0,find返回值是≥1,返回值从1开始算
int find(int x){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;}return r+1;
}
int main(){cin>>n>>m;for(int i=0;i<n;++i){int x,c;cin>>x>>c;add.push_back({x,c});alls.push_back(x);}for(int i=0;i<m;++i){int l,r,c;cin>>l>>r;query.push_back({l,r});alls.push_back(l);alls.push_back(r);}sort(alls.begin(),alls.end());alls.erase(unique(alls.begin(),alls.end()),alls.end());for(auto item:add){int idx=find(item.first);a[idx]+=item.second;}for(int i=1;i<=alls.size();++i){b[i]=b[i-1]+a[i];}for(const auto& item:query){int l=find(item.first),r=find(item.second);cout<<b[r]-b[l-1]<<endl;}return 0;
}