树状数组，是一个用于在近似 $O(logn)$ 时间内动态修改以及查询前缀和的数据结构，以下我们先来看以下树关系表格
层 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 16 2 8 12 14 15 3 4 6 7 10 11 13 4 2 3 5 9 5 1 这里表达的是，16的子节点有8, 12, 14, 15
8的子节点有4, 6, 7
12的子节点有10, 11，即夹在12与它的同级节点8之间
我们把数值与它的二进制一起形象化画出下图
graph TD; 2,0010-->1,0001 4,0100-->3,0011 4,0100-->2,0010 6,0110-->5,0101 8,1000-->7,0111 8,1000-->6,0110 8,1000-->4,0100 10,1010-->9,1001 12,1100-->11,1011 12,1100-->10,1010 14,1110-->13,1101 16,10000-->8,1000 16,10000-->12,1100 16,10000-->14,1110 16,10000-->15,1111 这样构造的原理是运用到一个二进制运算技巧，假设一个节点x，那么它的父节点就是x + (x & -x)，其中，x & -x是去掉右起第一个1的左边的1，例如x如果是6，二进制是110，只保留最右边的1结果就是10了，所以6的父节点就是6+2=8，更多的可以参考这篇二进制技巧。