本文共 2223 字，大约阅读时间需要 7 分钟。
身为一名弱省oier中的mengbier，简单讲一下我是怎么学会基础的树状数组的
不算华丽的分割线
也就是说你通过一系列神奇的操作可以实现在一个数列{an}中，修改其中一项ax的值（还可以是一段），并求出{an}前n项和（也可以是任意一段）。
额妹子！！！对不对？
我们知道 “树状数组” 这个名词的定语是 “树状” ，它只是用来修饰数组的对不对？
所以 “树状数组” 就是一串有特异功能的数组！
举个例子：
正常的一个数组{an}：a[1]=1, a[2]=2, a[3]=3, a[4]=4, a[5]=5, a[6]=6 ,a[7]=7, a[8]=8, a[9]=9
你要得到第n个数，就直接用a[n]来表示吧（废话）
但你要算前x项和{sn}的话，就只能从a[1]一项一项加到a[x], 显然当需要大量计算{sn}时，这种方法非常耗时！！！
于是机智的你想到了先计算出每一个sn来，但是当{an}需要修改怎么办？
难道要每一个有关的sn都修改吗？
于是大佬们YY出了树状数组
神奇的数组{cn}： c[1]=1, c[2]=3, c[3]=3, c[4]=10, c[5]=5, c[6]=11, c[7]=7, c[8]=36, c[9]=9
我说{cn}里能表达{an}所有信息，你信不信？
神出鬼没的分界线
设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。这个区间最后一个元素为Ax，
所以很明显：Cn = A(n – 2^k + 1) + ... + An
也就是说例如:
c[1], 1的二进制数为1，k=0，它就管长度为2^0的区间的和，暨c[1]=a[1]
c[2], 2的二进制数为10，k=1，它就管长度为2^1的区间的和，暨c[2]=a[1]+a[2]
c[4], 4的二进制数为100，k=2，它就管长度为2^2的区间的和，暨c[4]=a[1]+a[2]+a[3]+a[4]
c[6], 6的二进制数为110，k=1，它就管长度为2^1的区间的和，暨c[6]=a[5]+a[6]
c[9], 9的二进制数为1001，k=0，它就管长度为2^0的区间的和，暨c[9]=a[9]
强烈建议读者用纸笔模拟一遍！！！
有一个函数可以简单的计算出这个2^k
1 int lowbit(int x)2 {3 return x&-x;4 } 不信就用笔算一算
那我现在要求前n项和怎么办？
那就从c[n]开始，不重复的加完数据！
例如：
我要求前6项和，那就从c[6]开始加，发现c[6]已经代表了2项，加完c[6]，就加c[6-2]，加c[4]的值，发现c[4]代表了4项，此时就加完前6项
还是看代码吧
1 int sum(int n) 2 { 3 int ans=0; 4 while(n>0) 5 { 6 ans+=c[n]; 7 n-=lowbit(n); //加完了该项能表示的数，就加还没表达到的数 8 } 9 10 return ans; 11 }
那要改一项的值就要改{cn}中每个有关的项
1 void add(int x,int v) //x位置加v2 {3 while(x<=n) //n为边界，一共有多少个数4 {5 c[x]+=v;6 x+=lowbit(x); //下一个可以管辖该点的数组下标7 }8 }
那从a[x]+a[x+1]+a[x+2]+……+a[y-1]+a[y]，就可以表示为sum（y）-sum（x-1）；
就是任意连续数列和了
神出鬼没的分界线
在下的文字功底还是不行，可能讲的不是很好，请见谅
提供一些有关树状数组的题目：
转载地址：http://mqhof.baihongyu.com/