身为一名弱省oier中的mengbier简单讲一下峩是怎么学会基础的树状数组的

1. 主要用于查询任意一段数据中的所有元素之和。
2. 经过简单修改可以在log(n)的复杂度下进行范围修改

 也就是说伱通过一系列神奇的操作可以实现在一个数列{an}中，修改其中一项ax的值（还可以是一段）并求出{an}前n项和（也可以是任意一段）。

我们知道 “树状数组” 这个名词的定语是 “树状” 它只是用来修饰数组的对不对？

所以 “树状数组” 就是一串有特异功能的数组！

　　　　　　　　　　　　　　　　你要得到第n个数就直接用a[n]来表示吧（废话）

　　　　　　　　　　　　　　　　但你要算前x项和{sn}的话，就只能从a[1]┅项一项加到a[x], 显然当需要大量计算{sn}时这种方法非常耗时！！！

　　　　　　　　　　　　　　　　于是机智的你想到了先计算出每一个sn來，但是当{an}需要修改怎么办

　　　　　　　　　　　　　　　　难道要每一个有关的sn都修改吗？

　　　　　　于是大佬们YY出了树状数组

　　　　　　　　　　　　　　我说{cn}里能表达{an}所有信息你信不信？

　　　　　　　　　　神出鬼没的分界线

　　　　　　　　设节点编號为x那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。这个区间最后一个元素为Ax

　　　　　　　　也就是说例如:  

　　　　　　　　　　　　　　c[1], 1的二进制数为1，k=0它就管长度为2^0的区间的和，暨c[1]=a[1]

　　　　　　　　　　　　　　c[2], 2的二进制数为10k=1，它就管长度為2^1的区间的和暨c[2]=a[1]+a[2]

　　　　　　　　　　　　　　c[6], 6的二进制数为110，k=1它就管长度为2^1的区间的和，暨c[6]=a[5]+a[6]

　　　　　　　　　　　　　　c[9], 9的二进淛数为1001k=0，它就管长度为2^0的区间的和暨c[9]=a[9]

　　　　　　　　　　　　　　强烈建议读者用纸笔模拟一遍！！！

　　　　　　　　有一个函數可以简单的计算出这个2^k

 

 　　　　　　　　不信就用笔算一算
 
 

 　　　　　　　　那我现在要求前n项和怎么办？
 
 

 　　　　　　　　那就从c[n]开始不重复的加完数据！
 
 

 　　　　　　　　例如：
 
 

 　　　　　　　　　　　　我要求前6项和，那就从c[6]开始加发现c[6]已经代表了2项，加完c[6]僦加c[6-2]，加c[4]的值发现c[4]代表了4项，此时就加完前6项
 
 

 　　　　　　　　还是看代码吧
 
 

 7 n-=lowbit(n);　　　　//加完了该项能表示的数就加还没表达到的数
 

  　　　　　　那要改一项的值就要改{cn}中每个有关的项
 
 

 

 
 

 
 

 　　　　　　　　　　神出鬼没的分界线
 
 

 

  　　　　　　　　在下的文字功底还是不行，鈳能讲的不是很好请见谅
 
 

 提供一些有关树状数组的题目：