树状数组（ Binary Indexed Tree）

树状数组（Fenwick Tree / Binary Indexed Tree）这个东西。这玩意儿听起来挺唬人，但本质上就是个用数组模拟树形结构的工具，专门用来解决一类问题：频繁的单点更新和区间查询。如果我们用普通数组，更新是 O(1)，但查区间和就是 O(N)；用前缀和数组，查区间和是 O(1)，但你更新一个点，后面所有的前缀和都得改，又是 O(N)。两边都不讨好。树状数组就把这两个操作都干到了 O(logN)，一下就平衡了。 废话不多说，咱们从题入手，看看这东西到底怎么用，思路是怎么一步步升...