C语言树状数组的实例详解
发布时间：2020-12-15 03:35:12 所属栏目：C语言 来源：网络整理
导读：C语言树状数组的实例详解 最近学了树状数组，给我的感觉就是 这个数据结构好神奇啊^_^ 首先她的常数比线段树小，其次她的实现复杂度也远低于线段树 （并没有黑线段树的意思=-=） 所以熟练掌握她是非常有必要的。。 关于树状数组的基础知识与原理网上一搜一大
|
C语言树状数组的实例详解 最近学了树状数组，给我的感觉就是 这个数据结构好神奇啊^_^ 首先她的常数比线段树小，其次她的实现复杂度也远低于线段树 （并没有黑线段树的意思=-=） 所以熟练掌握她是非常有必要的。。 关于树状数组的基础知识与原理网上一搜一大堆，我就不赘述了，就谈一些树状数组的应用好了 1，单点修改，求区间和
#define lowbit(x) (x&-x) // 设 x 的末尾零的个数为 y,则 lowbit(x) == 2^y
void Update(int i,int v) // 初始化与单点修改
{
while(i <= n)
{
c[i] += v ;
i += lowbit(i) ;
}
}
inline int Sum(int i) // 区间求和
{
int res = 0 ;
while(i > 0)
{
res += c[i] ;
i -= lowbit(i) ;
}
return res ;
}
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] 所以单点查询变成了区间求和 那么区间修改怎么办呢 ？ 我们看这样一个例子： a 1 3 4 5 7 10 c 1 2 1 1 2 3 若我们令区间[2,4]加2，则 a 1 5 6 7 9 10 c 1 4 1 1 2 1 我们可以发现只有c[2]和c[5]的数值改变了，其实原理也很好想，区间内的前后元素差是不变的，只有（区间第一个元素与前一个元素的差） 和 （区间后第一个元素与区间末尾元素的差） 改变了。所以区间修改问题变成了单点修改问题。
for(int i=1;i<=n;i++)
{
a[i] = read() ;
Update(i,a[i]-a[i-1]);
}
/* int x=0,y=0; // 注释掉的内容是空间上的优化（初学者建议先跳过）
for(int i=1;i<=n;i++)
{
if(i%2)
{
x = read() ;
Update(i,x-y);
}
else
{
y = read() ;
Update(i,y-x) ;
}
} */
int ii ;
int k,x,y;
for(int i=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("%dn",Sum(x));
}
}
（洛谷有对应的模板题 P3374 与 P3368） 上述就是树状数组最基础的两个应用，日后更深入的学习后再来更新。 如有疑问请留言或到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！ （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |