树状数组详解（重拾笔记）

朴灿烈づ我的快乐病毒、 2024-04-20 11:11 76阅读 0赞

还是考试的时候想起来的。。。虽然没考。。。

上次考kmp那道模板题9分给我干慌了生怕考的时候不会，所以就来复习一波;

先知其目的，再懂其思想原理，再学其实现;

目的：维护区间和（前缀），区间信息，支持区间修改。。。。也就是维护动态区间信息。。。。

算法中的大思想无非优化思想，转换思想，简化思想，利用思想，贡献思想。（胡扯中。。。个人认为），细分的话就太多了。。。。

树状基于二进制和前缀和的思想，这是一种优化思想。

来个很\*\*2的问题（大佬自动跳过）：为什么有树状数组这个东西，就是说为什么它优秀？它比前缀和优秀在哪里呢？

这大概是一个有关树状数组产生的问题吧？（yy中）  其实树状数组大概算是一种利用均摊思想的高级算法，想一下如果只有查询操作，直接前缀和O1得不比log优秀吗？

然而一旦状态成了动态（th也就是有修改操作），前缀和就几乎萎了，on修改。。。树状数组均摊修改Ologn，这大概就是它优秀的地方了。。。。

原理的话，结合目的，我们要的是动态区间信息，和数组脱不了关系，而前缀和之所以O1查ON改就是因为下标的原因，，，一个接一个。。。

我们考虑均摊的话也得在下标上做文章，如何均摊？既然一个挨一个是1和n，那么我们把下标变成一块一块的（有点分块思想）每次查询修改就跳着来，就大概能实现均摊。

可是怎么才能使既分成了块，效率又得高，还得知道我们维护的下一个块的数组下标是什么呢。。。。。

二进制，，非常强。

既然在下标上做文章那么也就是在这个数上搞事情，和数，区间，Log，优化,,,,联系最大的，除了二进制还有什么？？？

看一下二进制的特点，对于一个数换成二进制的话，有1的位置表示对这个数的大小有贡献，，，，我们和不利用这个特点数组下标也这么干查询修改只对和它的贡献或答案有关的区间数组下标进行操作呢？而用1，0下标一定不行，所以二进制还有位数这个东西。  那如何使我们的效率较高呢??？

我们可以再进一步，既然要分区间我们每个下标有有定值有二进制对应的1和其位数，那么划分对其有贡献的区间就可以把其按照有1的位数来干出长度，，，有点胡扯了说的不是很清楚。。。。已7为例

二进制是00111，4  2   1 （2^0,2^1,2^2）  ，   我们把1-7分成长度分别为1，2，4的区间，这样利用了二进制的信息有了长度和下标，，那1，2，4长度的区间怎么划分呢？？？

是1-1 2-3 4-7还是1-4 5-6  7-7呢？？考虑哪个可以借助二进制来实现。。。。

从二进制的角度想，用到了每一位的一，有一就是有贡献就要加上这个位数的1代表的区间信息。。。。那和Lowbit有关系了lowbit可以找出整数在二进制下所有等于1的位对于7，7-lowbit(7)->6  6->lowbit()=2  ->4->lowbit=4,这就比较清晰了显然是第二种。。。

既然分好了区间那我们当然考虑对c\[x\]维护某个区间的信息，，，，这时用到了yy的那棵树，树的特点很显然每个点维护自己的信息。。。

那么我们就让c\[x\]存储\[x-lowbit(x)+1,x\]的信息保证自己有自己的管辖范围，找信息的时候相互补充利用就得到完整区间信息  （利用思想有点玄但能这么干的算法都很强，比如CDQ分治，比如莫队。。。。）说的不对别在意...

树状数组的性质：（摘）  
每个内部节点c\[x\]保存以它为根的子树中所有叶节点的和。。。

c\[x\]的子节点个数等于lowbit(x)的位数。。。

除树根外每个内部节点的父节点是c\[x+lowbit(x)\];

树的深度为log(n);

需要注意：8：1000，所以c\[8\]=sum\[8\],但是c\[8\]子节点有c\[1\]->c\[7\],我们的c是存的\[x-lowbit(x)+1,x\],这是一段区间为的就是求sum,  sum\[3\]=c\[2\]+c\[3\](c\[2\]=a\[1\]+a\[2\],其子节点有c\[1\]),所有的c构成一个候选集合而一些有父子关系。。一些没有直接关系，，，我们查询就需要它们之间互相补充，而树状数组的更改之所以优秀就是因为有了父子节点我们可以根据儿子的修改直接修改父亲，，，，注意访问到父节点的话父节点已经含有子节点的信息所以无需继续扫其子节点，父子关系主要是为了维护动态修改。。

代码实现：

int ask(int x)

for(int i=x;i;i-=lowbit(i))

ans+=c\[x\];//对每一个1维护的区间信息都加上。

return ans;  
\}

void add(int x,int y)\{

for(x=x;x<=n;x+=lowbit(x))  c\[x\]+=y;

//想一下那棵树，对于x的变动我们改和其有关的节点信息，c\[x\]存\[x-lowbit\[x\]+1,x\],所以c\[x\]子节点中的信息不变，而c\[x\],及其父亲都　　需更改因为访问父亲时就不访问儿子了。。。  
\}

初始化可以直接用add操作，也可以直接对x扫lowbit像ask里操作一样，后者每条边只访问了一次效率更高一些。ON,前者Onlogn,一个不重不漏，一个只做到了不漏。。。

知识理解透才能考试不慌心态不炸，现推也能搞出来。

每一次重拾都是一次更深的理解........

转载于:https://www.cnblogs.com/three-D/p/11257966.html