树状数组详细解析
本文中或许会引进部分图片来自网络，但大多数内容均为原创qwq。
树状数组或者二叉索引树也称作Binary Indexed Tree，又叫做Fenwick树。
它的查询和修改的时间复杂度都是log(n)，空间复杂度则为O(n).
(这也是我们为什么使用树状数组的原因)
树状数组可以将线性结构转化成树状结构，从而进行跳跃式扫描，通常使用在高效的计算数列的前缀和，区间和，同时，我们在运用线段树的时应先考虑是不是可以使用树状数组来解决问题。
也就是说，在解题思路中，树状数组的优先度是大于线段树的(当然对于神仙们是除外的)
这同样适用于我们针对于排名rank的排序，不过这个时候就需要建立结构体式的树状数组了(我是这么叫的qwq)
下面开始从0入门了：
1.单点查询
我们先从数组讲起(这个就不需要普及了吧)；
A数组是我们传入数据的数组
C数组使我们建立起来的树状数组
我们通过这里可以显而易见地发现这样一个规律：
C1 = A1 C2 = A1+A2 C3 = A3 C4 = A1+A2+A3+A4 C5 = A5 C6 = A5+A6 C7 = A7 C8 = A1+A2+A3+A4+A5+A6+A7+A8
请大家好好理解上述代码，这是树状数组的基础
接下来我们引入lowbit这个概念：(这个地方有一点需要注意：lowbit(0)会陷入死循环 )
inline int lowbit(int x) { return x & (-x); }
这返回的是这个数字最高位的1;
在这之前，又要引入一个补码的概念：
补码的表示方法是:
正数的补码就是其本身
负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)
[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补
请注意，这里的第一位是指的是符号位，而不是数字位(这是1，因此数字位只有1)
对于负数, 补码表示方式也是人脑无法直观看出其数值的. 通常也需要转换成原码在计算其数值.
因此，&是求与的一个符号，意思是 a 和 b 同时为 1 的时候返回这个最高位(不包括符号位)
在刚刚的找规律过程中，我们通过规律总结出了以下性质(lowbit是为了帮助程序代码的实现)
我们可以得到树状数组的一些性质：对于c[i]，他的儿子节点取决于i的所有因子中最多有2^j次幂，则向前取2^j个数作为儿子，即[i-2^j+1,i]。(这个时候就需要lowbit来帮助实现)
举一个栗子：
6的最大2次方因子为2，即2^1，则向前取2个数，则c[6]=a[5]+a[6]；
8的最大2次方因子为8，即2^3，则向前取8个数，则c[8]=a[1]+a[2]+…+a[8]。
2.单点修改
当我们要对最底层的值进行更新时，那么它相应的父亲节点存储的和也需要进行更新，
我们建立的树状数组结构是一个完整的结构，因此修改一个点也会需要所有相应的其父亲节点的点来修改，这样我们就实现了树状数组的修改。
代码如下：
void modify(int x,int k) //将 x 增加 k { if(x < 1) return ; while(x <= n) { c[i] += k; x += lowbit(x); //去寻找它的父亲 } }
3.单点查询
单点查询由于我们向前统计，因此需要向前查找，这个就不需要讲了吧(没弄明白请看上面)
int query(int pos)
{
int sum=0;
for(int i=pos;i;i-=lowbit(i))
sum += c[pos];
/*两种写法
while(pos > 0)
{
sum += c[pos];
pos -= lowbit(pos);
}
*/
return sum;
}
至此为止，我们已经讲完了树状数组的基础内容。
请确保在以上内容均熟练掌握的情况下再学习以下知识点。
未完待续~~~