跳至主要內容

01. 树状数组知识

ITCharge大约 1 分钟

树状数组知识

1. 树状数组简介

1.1 树状数组的定义

树状数组(Binary Indexed Tree):也因其发明者命名为 Fenwick 树,最早 Peter M. Fenwick 于 1994 年以 A New Data Structure for Cumulative Frequency Tables 为题发表在 SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率(Cumulative Frequency)的计算问题,现多用于高效计算数列的前缀和,区间和。它可以以 O(logn)O(\log n) 的时间得到任意前缀 i=1jA[i],1jn\sum_{i=1}^{j}A[i], 1 \le j \le n,并同时支持在 O(logn)O(\log n) 时间内支持动态单点值的修改。空间复杂度为 O(n)O(n)

1.2 树状数组的原理

2. 树状数组的基本操作

2.1 树状数组的建立

2.2 树状数组的修改

2.3 树状数组的求和

4. 树状数组的常见题型

4.1 单点更新 + 区间求值

4.2 区间更新 + 单点求值

4.3 求逆序对数

参考资料