树状数组 树状数组或二元索引树英語Binary Indexed Tree又以其发明者命名为芬威克樹英語Fenwick tree最早由彼得M芬威克Peter M Fenwick于年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE其初衷是解决数据压缩裡的累积频率Cumulative Frequency的计算问题现多用于高效计算数列的前缀和 区间和它可以以 O  log  n  displaystyle Olog n 的时间得到任意前缀和  i   j A  i     j  N displaystyle sum ijAijN 并同时支持在 O  log  n  displaystyle Olog n 时间内支持动态单点值的修改空间复杂度 O  n  displaystyle On