11 条题解
-
1
蒟蒻刚学的线段树,话不多说,上线段树做法:
#include<iostream> using namespace std; long long a[50],segt[50]; void build(int l,int r,int num){ //递归建线段树 if(l==r) segt[num]=a[l]; else{ int mid=(l+r)/2; build(l,mid,num*2); build(mid+1,r,num*2+1); segt[num]=segt[num*2]+segt[num*2+1]; } } long long query(int l,int r,int lnow,int rnow,int num){ if(l<=lnow&&rnow<=r) return segt[num]; else{ long long ans=0; int mid=(l+r)/2; if(l<=mid) ans+=query(l,r,lnow,mid,num*2); if(r>=mid+1) ans+=query(l,r,mid+1,rnow,num*2+1); return ans; } } int main(){ cin>>a[1]>>a[2]; build(1,2,1); //建树 cout<<query(1,2,1,2,1); //查询区间[1,2]的和 }
整体思想就是把 看成一个区间,最后可以便利地进行查询。
信息
- ID
- 4451
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 1
- 标签
- 递交数
- 1632
- 已通过
- 551
- 上传者