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（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。