简述什么是树状数组呢，顾名思义就是树一样的数组，本质就是用数组模拟树形结构。　　树状数组有什么用呢，树状数组可以实现单点更新，单点查询，区间查询和区间更新，维护的东西和线段树可以类比的，就是满足区间加法性质的属性，例如最值，和，gcd等。树状数组可以干的东西线段树也能干，但线段树干的东西树状数组不一定能干。树状数组的复杂度和线段树同级，但常数更低且代码量更为简答，所以我们能用树状数组就用树状数组，这样就不容易TLE了。lowbit操作首先我们来了解一个操作，lowbit(x)，这个操作取出x二进制最低位的1，例：lowbit(10100)=100lllowbit(llx){returnx&(-

简述什么是树状数组呢，顾名思义就是树一样的数组，本质就是用数组模拟树形结构。　　树状数组有什么用呢，树状数组可以实现单点更新，单点查询，区间查询和区间更新，维护的东西和线段树可以类比的，就是满足区间加法性质的属性，例如最值，和，gcd等。树状数组可以干的东西线段树也能干，但线段树干的东西树状数组不一定能干。树状数组的复杂度和线段树同级，但常数更低且代码量更为简答，所以我们能用树状数组就用树状数组，这样就不容易TLE了。lowbit操作首先我们来了解一个操作，lowbit(x)，这个操作取出x二进制最低位的1，例：lowbit(10100)=100lllowbit(llx){returnx&(-

lowbit()lowbit(x)是x的二进制表达式中最低位的1所对应的值（即返回x二进制为一的最低位数值）。lowbit(0)=0常用写法：intlowbit(intx){ returnx&(-x);}//利用了负整数的补码特性用法维护区间设节点编号为x，那么该节点维护的区间和是$(x-lowbit(x),x]$。树状数组基本操作复杂度：$O(logn)$树状数组利用了lowbit()来进行区间维护。令父节点储存其子节点之和，则不难发现：$C[i]=A[i-2k+1]+A[i-2k+2]+......A[i]$（k为i的二进制中从最低位到高位连续零的长度）lowbit(x)就是取出x的最低位

lowbit()lowbit(x)是x的二进制表达式中最低位的1所对应的值（即返回x二进制为一的最低位数值）。lowbit(0)=0常用写法：intlowbit(intx){ returnx&(-x);}//利用了负整数的补码特性用法维护区间设节点编号为x，那么该节点维护的区间和是$(x-lowbit(x),x]$。树状数组基本操作复杂度：$O(logn)$树状数组利用了lowbit()来进行区间维护。令父节点储存其子节点之和，则不难发现：$C[i]=A[i-2k+1]+A[i-2k+2]+......A[i]$（k为i的二进制中从最低位到高位连续零的长度）lowbit(x)就是取出x的最低位