首页 > 代码库 > uestc 1073 秋实大哥与线段树 Label:线段树
uestc 1073 秋实大哥与线段树 Label:线段树
秋实大哥与线段树
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
“学习本无底,前进莫徬徨。” 秋实大哥对一旁玩手机的学弟说道。
秋实大哥是一个爱学习的人,今天他刚刚学习了线段树这个数据结构。
为了检验自己的掌握程度,秋实大哥给自己出了一个题,同时邀请大家一起来作。
秋实大哥的题目要求你维护一个序列,支持两种操作:一种是修改某一个元素的值;一种是询问一段区间的和。
Input
第一行包含一个整数nn,表示序列的长度。
接下来一行包含nn个整数aiai,表示序列初始的元素。
接下来一行包含一个整数mm,表示操作数。
接下来mm行,每行是以下两种操作之一:
1 x v : 表示将第x个元素的值改为v2 l r : 表示询问[l,r]这个区间的元素和
1≤n,m,v,ai≤1000001≤n,m,v,ai≤100000,1≤l≤r≤n1≤l≤r≤n。
Output
对于每一个22 ll rr操作,输出一个整数占一行,表示对应的答案。
Sample input and output
Sample Input | Sample Output |
---|---|
31 2 332 1 21 1 52 1 2 | 37 |
代码
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #define ll long long 6 using namespace std; 7 ll bit[500005],a[500005]; 8 ll n,m; 9 10 ll sum(ll i){//求元素1~i的和 11 ll s=0;12 while(i>0){13 s+=bit[i];14 i-=i&(-i);15 }16 return s;17 }18 19 void add(ll i,ll x){//将元素i加上x 20 while(i<=n){21 bit[i]+=x;22 i+=i&(-i);23 }24 }25 26 int main(){27 28 scanf("%lld",&n);29 for(int i=1;i<=n;i++){30 scanf("%d",&a[i]);31 add(i,a[i]);32 }33 34 scanf("%lld",&m);35 for(int i=1;i<=m;i++){36 ll x=0,b=0,c=0;37 scanf("%lld%lld%lld",&x,&b,&c);38 if(x==1){39 ll temp=c-a[b];//处理修改后的数与原数的差 40 a[b]=c; 41 add(b,temp);42 }43 else if(x==2){44 ll temp=sum(c)-sum(b-1);45 printf("%lld\n",temp);46 }47 }48 return 0;49 }用的树状数组,注意变量名要起好,像Line41我就直接写成了
add(x,temp);果断WA
还有Line40,没写,思考一下就知道,可能对一个值多次修改,然后Orz
代码
准备试试zkw线段树 Orz
uestc 1073 秋实大哥与线段树 Label:线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。