简述

　　二分索引树是一种树状数组，其全名为Binary Indexed Tree。二分索引树可以用作统计作用，用于计某段连续区间中的总和，并且允许我们动态变更区间中存储的值。二分索引树和线段树非常相似，二者都享有相同的O(log2(n))时间复杂度的更新操作和O(log2(n))时间复杂度的查询操作，区别在于二分索引树更加简洁高效，而线段树则较冗杂低效，原因在于对二分索引树的操作中是使用了计算机中整数存储的特性来进行加速，而线段树中由于使用的是比较操作，因此性能不及二分索引树。那么为什么我们不抛弃线段树呢？原因在于所有二分索引树能解决的问题，线段树也都可以解决，但是线段树还能解决许多二分索引树无法解决的问题。下面将先后讨论二分索引树和线段树。　　二分索引树是一种树状数组，其全名为Binary Indexed Tree。二分索