首页 > 代码库 > 10:Challenge 3(树状数组直接修改)
10:Challenge 3(树状数组直接修改)
- 总时间限制:
- 10000ms
- 单个测试点时间限制:
- 1000ms
- 内存限制:
- 262144kB
- 描述
给一个长为N的数列,有M次操作,每次操作是以下两种之一:
(1)修改数列中的一个数
(2)求数列中某连续一段的和
- 输入
- 第一行两个正整数N和M。
第二行N个整数表示这个数列。
接下来M行,每行开头是一个字符,若该字符为‘M‘,则表示一个修改操作,接下来两个整数x和y,表示把x位置的值修改为y;若该字符为‘Q‘,则表示一个询问操作,接下来两个整数x和y,表示求[x,y]这段区间的和。 - 输出
- 对每一个询问操作单独输出一行,表示答案。
- 样例输入
5 31 2 3 4 5Q 1 5M 2 7Q 1 5
- 样例输出
1520
- 提示
- 1<=N<=10^5,1<=M<=10^5,输入保证合法,且所有整数及答案可用带符号32位整型存储。
- 考虑树状数组肯定是没有什么疑问的,
- 但是这里不是加减,而是直接修改,
- 然而直接修改会爆零,原因自己yy一下就知道。
- 所以说,我们每次改的时候,去加上要加的数和当前的数的差,然后再把当前的数改成将要改的数
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int MAXN=100001; 6 int a[MAXN]; 7 int tree[MAXN]; 8 int n,m; 9 void read(int &n)10 {11 char c=‘+‘;int x=0;bool flag=0;12 while(c<‘0‘||c>‘9‘){c=getchar();if(c==‘-‘)flag=1;}13 while(c>=‘0‘&&c<=‘9‘)14 x=(x<<1)+(x<<3)+c-48,c=getchar();15 flag==1?n=-x:n=x;16 }17 int lb(int p)18 {19 return (p)&(-p);20 }21 void add(int pos,int v)22 {23 int p=pos;24 while(p<=n)25 {26 tree[p]+=v;27 p+=lb(p);28 }29 }30 int sum(int pos)31 {32 int ans=0;33 int p=pos;34 while(p)35 {36 ans+=tree[p];37 p-=lb(p);38 }39 return ans;40 }41 int main() 42 {43 read(n);read(m);44 for(int i=1;i<=n;i++)45 {46 int p;47 read(p);48 a[i]=p;49 add(i,p);50 }51 for(int i=1;i<=m;i++)52 {53 char c;int x,y;54 cin>>c;read(x);read(y);55 if(c==‘Q‘)56 printf("%d\n",sum(y)-sum(x-1));57 else58 {59 add(x,y-a[x]);60 a[x]=y;61 }62 63 }64 return 0;65 }
10:Challenge 3(树状数组直接修改)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。