首页 > 代码库 > 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(树状数组直接修改)