树状数组

树状数组运用了二进制分解原理

对于任意的整数x，都可以分解为：\(x=2^{i_1}+2^{i_2}+...+2^{i_m}\)
其中\(i_1>i_2>...>i_m\)
于是可以把\([1,x]\)分解成很多段
\([1,2^{i_1}]\)
\([2^{i_1}+1,2^{i_1}+2^{i_2}]\)
\([2^{i_1}+2^{i_2}+1,2^{i_1}+2^{i_2}+2^{i_3}]\)
. . .
\([2^{i_1}+2^{i_2}+...+2^{i_{m-1}}+1,2^{i_1}+2^{i_2}+...+2^{i_m}]\)

比如\(7=4+2+1\)
于是\([1,7]=[1,4]+[5,6]+[6,7]\)
定于 \(lowbit(x)\) 表示 \(x\) 在 \(2\) 分解下最小的幂
\(lowbit(7)=1,lowbit(6)=2,lowbit(4)=4\)
公式：\(lowbit(x)=x\&-x\)

树状数组：维护序列前缀和
\(c[x]\) 表示区间 \([x-lowbit(x)+1,x]\) 之间的数的和

如图

其中 \(c[x]\) 的父亲节点是 \(c[x+lowbit(x)]\)