树状数组

树状数组

前言

树状数组：用数组来描述树结构，但并非满二叉树
如图所示，树C与数组A有如下关系：

C[1] = A[1]
C[2] = A[1] + A[2]
C[3] = A[3]
C[4] = A[1] + A[2] + A[3] + A[4]
C[5] = A[5]
C[6] = A[5] + A[6]
C[7] = A[7]
C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8]

可以归纳为

比如6=110，从低位到第一个非0是2，c[6]= A[6]+A[5]
利用负数存储的性质 可以得到

这是一个专门的函数，名为lowbit，即取2^k。

//待续。。。。