首页 > 代码库 > uestc 1073 秋实大哥与线段树 Label：线段树

uestc 1073 秋实大哥与线段树 Label：线段树

2024-08-11 09:33:21   222人阅读

秋实大哥与线段树

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 InputSample 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：线段树


联系
我们