树状数组（Fenwick tree，又名binary indexed tree），是一种很实用的数据结构。它通过用节点i，记录数组下标在[ i 2^k + 1, i]这段区间的所有数的信息（其中，k为i的二进制表示中末尾0的个数，设lowbit(i) = 2^k），实现在O(lg n) 时间内对数组数据的查找和更新。 树状数组的传统解释图，不能很直观的看出其所能进行的更新和查询操作。其最主要的... [阅读全文]