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

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

树状数组(BIT)  

2016-08-04 22:03:44|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在log(n)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值。——by百度百科
=====================================
        树状数组被许多人称作最优美的数据结构,优美在于它的简洁高效,屈指可数的代码量却有log级的效率。它可以修改序列中的一个值,log级的维护,log级的查找1~n的数的和(和部分和差不多,可以求一段的和),这是它最大的优点,然而空间也是数组般的简洁(就是数组)。
        附上一幅图,大致了解它的原理:
树状数组(BIT) - 杨鸿飞 - 一个叫杨鸿飞的人的博客
大概表达了一个树状数组每一位的“管辖范围”,然而这一切都是有规律,一个简洁的规律,二进制!所以我们要用到一个简单的位运算,lowbit(x)=x & (~(x-1))=x & -x(下面简称lb),就是计算一个二进制数可以取出一个数二进制中的最后一个1,比如lb(10010110100_二进制)=100_二进制=4_十进制。
======================================
        例子总是更有说服力。
        先从增加开始,它有个维护,虽然它是数组,但你会发现它的包含关系(就是要维护了),第5位就是一个很好的例子,在这一部分的树状数组中,如果第5位增加了x,那么6要加,8也要加。把它们变成二进制看看:
        101------110------1000------1000……!规律触手可及了,很多人会想到,是把离0位最近的0变成1然后0后面的1都变成0,也就是加上一个lb。附上yhf写的规范代码:

void Add(int p,int d) //第p位加一个d
{
for ( ; p<=n; p+=lb(p)) bi[p]+=d;
}

        再说求和,求1~7的和,就是要把4(1~4),6(5~6),7(7~7)加起来变成二进制看看:
        0<--------100<------110<-------111!是把离0位最近的1变成0,每次都减去一个lb。附上yhf写的规范代码:

int Sum(int p) //求1~p的和
{
int sum=0;
for ( ; p>0; p-=lb(p)) sum+=bi[p];
return sum;
}

       好简洁啊!
      这就讲完了。
=====================================
献上模版:

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdio>

#define lb(x) (x & (-x)) //lowbit

using namespace std;

const int MLn=100010;

int bi[MLn],n; //bi(bit)

int Sum(int p)
{
int sum=0;
for ( ; p>0; p-=lb(p)) sum+=bi[p];
return sum;
}

void Add(int p,int d)
{
for ( ; p<=n; p+=lb(p)) bi[p]+=d;
}

int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);

int m; scanf("%d%d",&n,&m);

for ( ; m>0; m--)
{
char ch; scanf("%c",&ch);

if (ch=='A')
{
int pp,xx; scanf("%d%d",&pp,&xx);
Add(pp,xx);
}
if (ch=='S')
{
int ll,rr; scanf("%d%d",&ll,&rr);
cout<<Sum(rr)-Sum(ll-1)<<endl;
}
}

return 0;
}



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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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