首页 > 代码库 > 初识树状数组
初识树状数组
描述 Description
输入一个数列A1,A2….An(1<=N<=100000),在数列上进行M(1<=M<=100000)次操作,操作有以下两种: (1) 格式为C I X,其中C为字符“C”,I和X(1<=I<=N,|X|<=10000)都是整数,表示把把a[I]改为X (2) 格式为Q L R,其中Q为字符“Q”,L和R表示询问区间为[L,R](1<=L<=R<=N),表示询问A[L]+…+A[R]的值。
输入格式 Input Format
第一行输入N(1<=N<=100000),表述数列的长度; 接下来N行,每行一个整数(绝对值不超过10000)依次输入每个数; 接下来输入一个整数M(1<=M<=100000),表示操作数量,接下来M行,每行为C I X或者Q L R。
输出格式 Output Format
对于每个Q L R 的操作输出答案。
样例输入 Sample Input
5
1 2 3 4 5
3
Q 2 3
C 3 9
Q 1 4
样例输出 Sample Output
5 16
时间限制 Time Limitation
1s
首先感谢ysc为我们带来的树状数组ppt,闲话也不多说了,树状数组的定义百科上也有,我也不在描述;
本来看到点修改的我其实很懵,因为代码是这样写的
void build(int i,int val){ while(i<=n){ c[i]+=val; i+=lowbit(i); } }
这是一步步向上修改根节点,然而我们看到题目描述是修改某点的值为什么,而不是加;
其实很容易,只要将要修改的值减去原来的值,赋给val就能实现。
代码很简单,要注意的是刚开始要建立c数组。
#include<cstring> #include<cstdio> #include<algorithm> #include<iostream> #define lowbit(i) i&(-i) using namespace std; int n,m; int a[100100]; int c[100100]; int ans; void build(int i,int val){ while(i<=n){ c[i]+=val; i+=lowbit(i); } } int sum(int x){ int temp=0; while(x>0){ temp+=c[x]; x-=lowbit(x); } return temp; } int main(){ //freopen("a.txt","r",stdin); //freopen("b.txt","w",stdout); cin>>n; for(int i=1;i<=n;++i){ scanf("%d",&a[i]); build(i,a[i]); } //cout<<sum(4)<<endl; cin>>m; for(int i=1;i<=m;++i){ char c; int x,y; cin>>c; if(c==‘C‘){ scanf("%d%d",&x,&y); build(x,y-a[x]); a[x]=y; } else if(c==‘Q‘){ scanf("%d%d",&x,&y); ans=sum(y)-sum(x-1); printf("%d\n",ans); } } //cout<<sum(4)<<endl; return 0; }
初识树状数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。