C语言树状数组的实例详解
C语言树状数组的实例详解
最近学了树状数组,给我的感觉就是这个数据结构好神奇啊^_^
首先她的常数比线段树小,其次她的实现复杂度也远低于线段树(并没有黑线段树的意思=-=)
所以熟练掌握她是非常有必要的。。
关于树状数组的基础知识与原理网上一搜一大堆,我就不赘述了,就谈一些树状数组的应用好了
1,单点修改,求区间和
#definelowbit(x)(x&-x)//设x的末尾零的个数为y,则lowbit(x)==2^y voidUpdate(inti,intv)//初始化与单点修改 { while(i<=n) { c[i]+=v; i+=lowbit(i); } } inlineintSum(inti)//区间求和 { intres=0; while(i>0) { res+=c[i]; i-=lowbit(i); } returnres; }
2,区间修改,单点查询
这里要用到差分的思想
创建一个差分数组c[],令c[i]=a[i]-a[i-1](a[i]表示原本的第i个数)
则a[i]=(a[i]-a[i-1])+(a[i-1]-a[i-2])+......+(a[2]-a[1])+a[1]
=c[i]+c[i-1]+......+c[2]+c[1]
所以单点查询变成了区间求和
那么区间修改怎么办呢?
我们看这样一个例子:
a1345710
c121123
若我们令区间[2,4]加2,则
a1567910
c141121
我们可以发现只有c[2]和c[5]的数值改变了,其实原理也很好想,区间内的前后元素差是不变的,只有(区间第一个元素与前一个元素的差)和(区间后第一个元素与区间末尾元素的差)改变了。所以区间修改问题变成了单点修改问题。
for(inti=1;i<=n;i++) { a[i]=read(); Update(i,a[i]-a[i-1]); } /*intx=0,y=0;//注释掉的内容是空间上的优化(初学者建议先跳过) for(inti=1;i<=n;i++) { if(i%2) { x=read(); Update(i,x-y); } else { y=read(); Update(i,y-x); } }*/ intii; intk,x,y; for(inti=1;i<=m;i++) { ii=read(); if(ii==1) { x=read();y=read();k=read(); Update(x,k); Update(y+1,-k); } if(ii==2) { x=read(); printf("%d\n",Sum(x)); } }
(洛谷有对应的模板题P3374与P3368)
上述就是树状数组最基础的两个应用,日后更深入的学习后再来更新。
如有疑问请留言或到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。