树状数组

树状数组

树状数组树状数组其实是一种针对于前缀和的优化。可以将区间查询和修改的复杂度讲从 $O(n)$ 降到 $O(\log n)$。算法主要思路正常的前缀和数组如果显示为一个树的话是这样的：也就是 $f_i$ 维护的区间是 $[1, i…