树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。它可以以的时间得到任意前缀和，并同时支持在时间内支持动态单点值的修改。空间复杂度。摘自维基百科文章先介绍低位运算（lowbit）的基本知识，再提及如何将一个整数划分为个区间的运算过程，进而延展到如何将线性序列以树行结构进行存取，接着介绍了高级数据结构——树状数组的两个基本操作——查询前缀和与单点增加，最后介绍了树状数组的一个应用——求解逆序对数。lowbit（低位）运算定义为非负整数在二进制表示下“最低位的1及其后边所有的0”构成的数值。比如：，其二进制表示为 ，则其低位。公式如何计算一个整数中二进制表示下所有位是1的数值？比如，则其二进制表示下所有位是1的数值有：，。... Read More