Binary Indexed Tree
又名 Fenwick Tree

基本原理

树状数组.pdf

能解决的问题

  • 前缀 + 修改某个数

举例

  1. 遍历数组，动态统计大于当前数组元素的数的个数，统计完后将当前数组元素也纳入考虑范围。也就是说树状数组维护了元素个数的前缀和

a[x] += c, 求a[l, r]，单点修改区间求和
AcWing 241. 楼兰图腾

  1. 树状数组维护差分，即前缀和是数组的某个元素，1的对称问题：区间修改单点求和

这样做的好处是当把数组某一段的元素加上d时，只需修改树状数组tr[l]和tr[r + 1]即可
修改时间复杂度为O(logn)，查询前缀和时间复杂度也为O(logn)
AcWing 242. 一个简单的整数问题

  1. 树状数组维护差分 + 公式，区间修改区间求和

Acwing 243. 一个简单的整数问题2
差分及公式推导.pdf

  1. 树状数组维护一个队伍的长度

AcWing 244. 谜一样的牛

  1. 维护一段区间的最小值
  • 维护[1, u]（即从开头开始的一段区间）的最值

Leetcode 962. 最大宽度坡
Leetcode 673. 最长递增673子序列的个数

  • 维护任意一段区间的最值

见RMQ

  1. 二维树状数组

308. 二维区域和检索 - 可变
顾名思义，二维的树状数组，行和列都用树状数组的思路去维护，先维护列，再维护行
如果说树状数组是前缀和的扩展的话，二维树状数组就是二维前缀和的扩展
类似的还能推广到用二维树状数组维护二维差分