树状数组是一个查询和修改复杂度都为log(n)的数据结构,假设数组a[1..n],那么查询a[1]+…+a[n]的时间是log级别的,而且是一个在线的数据结构,支持随时修改某个元素的值,复杂度也为log级别。
图形表示
Cn = A(n – 2^k + 1) + … + An ;
此处的k为n的二进制形式末尾0的个数,可以利用Lowbit()函数找出k
注意:下标不能从0开始:
当i = 0,0 + Lowbit(0) = 0,会造成死循环!
主要三个函数:
树状数组功能:
1、单点更新,区间求和(第一类)//HDU 1166 敌兵布阵
2、区间更新,单点求值(第二类)//HDU 1556 Color the ball
3 、逆序数的应用,可以求左边小于它的数,右边大于它的数,反过来可以求