注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

qus的博客

 
 
 

日志

 
 

树状数组  

2009-08-10 08:41:53|  分类: 资料 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

关于树状数组,最想说地就是代码简单,在区间统计有奇效,在二维,乃至更高维比线段树更好。(线段树我只会一维的)。

用与快速统计 A到B 之间的数组和
3个关键函数
int lowbit(int x)
{
return x&(x^(x-1));
}
void data(int x,int y,int  add)//二维
{
int i,j;
for(i=x;i<=n;i+=lowbit(i))
for(j=y;j<=n;j+=lowbit(j))
c[i][j]+=add;
}
void find(int x,int y)
{
int i,re=0;
for(i=x;i>=1;i-=lowbit(i))
for(j=y;j>=1;j-=lowbit(j))
re+=c[i][j];
return re;
}

一般将问题转化为求一段区间的和
如poj3321 通过dfs 求出该子树的起点与终点 从而知道所求的总区间

  评论这张
 
阅读(54)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017