本文共 3784 字,大约阅读时间需要 12 分钟。
树状数组可以解决什么样的问题:
这里通过一个简单的题目展开介绍,先输入一个长度为n的数组,然后我们有如下两种操作:
多次执行上述两种操作
寻常方法
对于一个的数组,如果需要求1~m的前缀和我们可以将其从下标1开始对m个数进行求和,对于n次操作,时间复杂度是O(n^2),对于值的修改,我们可以直接通过下标找到要修改的数,n次操作时间复杂度为O(n),在数组n开得比较大的时候,求前缀和的效率显得低了树状数组
那么是否有一种方法可以让查询和更新的时间复杂度都小一些呢,至少可以令人接受,这里将介绍树状数组如何处理前缀和查询和单点更新的问题,对于n次操作,时间复杂度都为O(nlogn)如图,对于一个长度为n的数组,A数组存放的是数组的初始值,引入一个辅助数组C(我们通过C数组建立树状数组)
C1 = A1
C2 = C1 + A2 = A1 + A2 C3 = A3 C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4 C5 = A5 C6 = C5 + A6 = A5 + A6 C7 = A7 C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8我们称C[i]的值为下标为i的数所管辖的数的和,C[8]存放的就是被编号8所管辖的那些数的和(有8个),而下标为i的数所管辖的元素的个数则为2^k个(k为i的二进制的末尾0的个数)举两个例子查询下标m==8和m==5所管辖的数的和
而对于输入的数m,我们要求编号为m的数的前缀和A1~Am(这里假设树状数组已经建立,即C1~C8的值已经求出,别着急,在本文的最下方会做出建立树状数组的过程讲解,因为现在是在求前缀和,就假设C数组已经可用了吧)举两个例子m==7和m==6(sum(i)表示求编号为i的前缀和)
这里要介绍一个高效的方法,lowbit(int m),这是一个函数,它的作用是求出m的二进制表示的末尾1的位置,对于要查询m的前缀和,m = m - lowbit(m)代表不断对二进制末尾1进行-1操作,不断执行直到m == 0结束,就能得到前缀和由哪几个Cm构成,十分巧妙,lowbit也是树状数组的核心
int lowbit(int m){ return m&(-m);}
关于m&(-m)很多童鞋可能感到困惑,那么就不得不提及一下负数在计算机内存中的存储形式,负数在计算机中是以补码的形式存储的,如13的二进制表示为1101,那么-13的二进制而将13二进制按位取反,然后末尾+1,即0010 + 0001 = 0011,那么1101 & 0011== 0001,很显然得到m == 13二进制末尾1的位置是2的0次方位,将13 - 0001 == 12,再对12执行lowbit操作,1100 & 0100 == 0100,也很轻易得到了m == 12时二进制末尾1的位置是2的2次方位,将12 - 0100 == 8,再对8执行lowbit操作,0100 & 1100 == 0100,得到m == 8时二进制位是2的2次方位,8 - 0100 == 0(结束操作),通过循环得到的13,12,8,则sum(13) == C13 + C12 + C8
求前缀和的代码
int ans = 0;int getSum(int m){ while(m > 0){ ans += C[m]; m -= lowbit(m); }}
对于n次前缀和的查询,时间复杂度为O(nlogn)
接下来讲解单点更新值 对于输入编号为x的值,要求为它的值附加一个value值,我们把图再一次拿下来假设x==2,value==5,那么我们先找到A[2]的位置,通过观察我们得知,如果修改了A[2]的值,那么管辖A[2]的C[2],C[4],C[8]的前缀和都要加上value(所有的祖先节点),那么和查询类似,我们如何得到C2的所有祖先节点呢(因为C2和A2的下标相同所以更新时查询从C[x]开始),依旧是上述的巧妙的方法,但是我们把它倒过来
对于要更新x位置的值,我们把x转换成二进制,不断对二进制最后一个1的位置+1,直到达到数组下标的最大值n结束给出代码
void update(int x, int value){ A[x] += value; //不能忘了对A数组进行维护,尽善尽美嘛 while(x <= n){ C[x] += value; x += lowbit(x); }}
对于n次更新操作,时间复杂度同样为O(nlogn)
这里有一个注意事项,我们对于求前缀和与单点更新时,树状数组C是拿来直接使用的,那么问题来了,树什么时候建立好的,我怎么不知道??
事实上,对于一个输入的数组A,我们一次读取的过程,就可以想成是一个不断更新值的过程(把A1~An从0更新成我们输入的A[i]),所以一边读入A[i],一边将C[i]涉及到的祖先节点值更新,完成输入后树状数组C也就建立成功了
#include#include int a[10005];int c[10005];int n;int lowbit(int x){ return x&(-x);}int getSum(int x){ int ans = 0; while(x > 0){ ans += c[x]; x -= lowbit(x); } return ans;}void update(int x, int value){ a[x] += value; while(x <= n){ c[x] += value; x += lowbit(x); }}int main(){ while(scanf("%d", &n)!=EOF){ //用于测试n == 8 memset(a, 0, sizeof(a)); memset(c, 0, sizeof(c)); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); //a[i]的值根据具体题目自己安排测试可以1,2,3,4,5,6,7,8 update(i, a[i]); //输入的过程就是更新的过程 } int ans = getSum(n-1); //用于测试输出n-1的前缀和 输出28 printf("%d\n", ans); } return 0;}
转载地址:http://fkgbi.baihongyu.com/