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

Xorex's blog

纵然希望渺茫,也要做一条有梦想的咸鱼!

 
 
 
 
 

日志

 
 
关于我

本人倒是一直被吊着打啊……

文章分类

二叉索引树(树状数组)—讲解  

2017-05-11 17:28:22|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
追随树神的脚步!然而树神写的PPT还是很良心的,很快就看懂了,题解也不错。
然后树状数组是不需要建树的,它的树成分并没有线段树那么强,是通过一个特殊的Lowbit来建立起来的;
树状数组的实现方式是用一个c数组维护原来的数组a,
c[i]=sum(a[j]),i-lowbit(i)+1<=j<=i;
这里的lowbit(i)表示将i转换成二进制后的最右边的1。
例如lowbit(6)=lowbit(110)2=(10)2=2
所以 c[6]=a[5]+a[6];
lowbit(4)=lowbit(100)2=(100)2=4 
c[4]=a[1]+a[2]+a[3]+a[4]
lowbit[5]=lowbit(101) 2 =(1) 2=1;
c[5]=a[5]

下面是重点!!!
lowbit(i)=i&(-i);
上面这个公式是非常重要的,就是通过求出一个数的Lowbit将这些数据建立成一个树的,父子节点和线段树关系类似,都是通过某种固定的方式建立起来的。而lowbit的原理就是利用了计算机里面的反码和补码(这世界本来就是二进制的!)
我们都知道在计算机中数使用二进制存储的,int是4字节,例如我们把5换成二进制。 5=00000000 00000000 00000000 00000101 这同时也是5的原码。 原码:一个正数,按照值大小转换成的二进制数;一个负数按照绝对值大小转换成的二进制数,然后最高位补1,称为原码。
那么-5的原码就是 -5=10000000 00000000 00000000 00000101,其中,最高位的1是符号位。 在计算机中储存一个数用的是补码的形式,要了解补码需要先知道什么是反码。 反码:正数的反码与原码相同,负数的反码为对该数的原码除符号位外各位取反 -5的反码就是: 11111111 11111111 11111111 11111010
再说补码:正数的补码与原码相同,负数的补码是这个数的反码+1 -5:11111111 11111111 11111111 11111010+1 = 11111111 11111111 11111111 11111011
那么我们利用这个公式 x&(-x) 的意义:
6&(-6):
  6:    00000000 00000000 00000000 00000110
        -6:   11111111 11111111 11111111 11111010
        Ans: 00000000 00000000 00000000 00000010
所以说lowbit(6)的结果很明显就是2
节点i的父亲节点为i+lowbit(i) 若需改变a[i],则c[i]、c[i+lowbit(i)]、 c[i+lowbit(i)+lowbit(i+lowbit(i)]……一直加到上限,就是需要改变的c数组中的元素。 若需查询s[i],则c[i]、c[i-lowbit(i)]、c[i-lowbit(i)-lowbit(i-lowbit(i))]……就是需要累加的c数组中的元素。 这样我们就让复杂度优化到了O(logn)
  觉得不是太懂???
修改 code:

void Change(int x,int add)
{
while(x<=n)
{
c[x]+=add;
x+=Lowbit(x);
}
}

查询 code:

int Question(int x)
{
int ans=0;
while(x>0)
{
ans+=c[x];
x-=Lowbit(x);
}
return ans;
}

然后我再放上一张图QAQ
二叉索引树(树状数组)—讲解 - Xorex - Xorexs blog

这个
就是树状数组在记录的时候,c数组记录的东西,这个本身是一个数组,利用lowbit来建立一个像树一样的结构(上图),然后利用到就像是二分(二进制分)思想,然后不断分开,进行计算。
二进制真的是神奇啊!将十进制狠狠的踩到地上……
1 2 1 3 1 2 1 4 就像是树一样……
然后我们看一道模板题:

P1356求和
输入一个数列A1,A2….An(1<=N<=100000),在数列上进行M(1<=M<=100000)次操作,操作有以下两种:
(1) 格式为C I X,其中C为字符“C”,I和X(1<=I<=N,|X|<=10000)都是整数,表示把把a[I]改为X
(2) 格式为Q L R,其中Q为字符“Q”,L和R表示询问区间为[L,R](1<=L<=R<=N),表示询问A[L]+…+A[R]的值。
输入:
第一行输入N(1<=N<=100000),表述数列的长度; 接下来N行,每行一个整数(绝对值不超过10000)依次输入每个数; 接下来输入一个整数M(1<=M<=100000),表示操作数量,接下来M行,每行为C I X或者Q L R。
输出:
对于每个Q L R 的操作输出答案。
这道题就是一个模板题,我们进行查询,一个区间x到y的时候,我们就先查询y到1的累加和,然后减去x到1的累加和就好了,改变值的时候我们就按照树状数组的定义方法进行修改,所有覆盖到他的数组都需要修改的。
code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,a[400000],c[400000];
int b[400000],x,y;
char Question_or_Change;
inline int In_int()
{
int This=0,F=1; char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') F=-F;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
This=(This<<1)+(This<<3)+ch-'0';
ch=getchar();
}
return This*F;
}
inline char In_char()
{
char ch=getchar();
while(ch<'A'||ch>'z') ch=getchar();
return ch;
}
inline int Lowbit(int x)
{ return (x&(-x)); }
int Question(int x)
{
int ans=0;
while(x>0)
{
ans+=c[x];
x-=Lowbit(x);
}
return ans;
}
void Change(int x,int add)
{
while(x<=n)
{
c[x]+=add;
x+=Lowbit(x);
}
}
int main()
{
n=In_int();
for(int i=1;i<=n;i++)
{
b[i]=In_int();
a[i]=a[i-1]+b[i];
c[i]=a[i]-a[i-Lowbit(i)];
}
m=In_int();
for(int i=1;i<=m;i++)
{
Question_or_Change=In_char();
x=In_int(); y=In_int();
if(Question_or_Change=='Q')
{
int First=Question(x-1);
int Second=Question(y);
cout<<Second-First<<endl;
}
if(Question_or_Change=='C')
{
Change(x,y-b[x]);
b[x]=y;
}
}
return 0;
}


如果仅仅从能解决的问题范围上面考虑的话,明显是线段树数要强大很多,而且树状数组能解决的问题,线段树都可以解决的,刚刚我在看到这句话之后,去吧我以前写过的树状数组的题目全部都翻出来了,发现事实的确就是如此,那么学习树状数组的目的是什么呢?以后所有的题目全部都用线段树来解决不就可以了了吗。
但是作为高级数据结构,树状数组的代码非常简洁,有着极其巧妙的Lowbit操作,在空间复杂度上面优于线段树,更重要的是在解决多维度问题上面,树状数组的展开能力是非常强的,网上有一句话说:线段树擅长解决横向问题,树状数组擅长解决纵向问题。如果能用树状数组解决,就上树状数组。
最后树状数组和线段树的区别就是,树状数组是站着上厕所的,线段树是蹲着上厕所的……(来自知乎的一位朋友精辟的比喻)


  评论这张
 
阅读(75)| 评论(0)

历史上的今天

评论

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

页脚

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