树状数组

2021-06-07 03:05

阅读：519

标签：查询 for splay data- com nbsp 包含更新 pac

时间复杂度：o(logn)

支持：

1.单点修改

2.区间查询：查询一个区间内所有元素的和

对 $[a,b]$ 进行区间查询只需查询 $[1,b]$ 和 $[1,a)$ 然后相减即可（前缀和就是这样进行区间查询的），所以我们可以把区间查询问题转化为求前n项和的问题。

可以用一个数组 $C$ 维护若干个小区间，单点修改时，只更新包含这一元素的区间；求前n项和时，通过将区间进行组合，得到从1到n的区间，然后对所有用到的区间求和。实际上，设原数组是 $A$ ，如果 $C_i$ 维护的区间是 $[A_i, A_i]$ ，此结构就相当于普通数组（还浪费了一倍内存）；如果 $C_i$ 维护的区间就是 $[1,A_i]$ ，此结构就相当于前缀和。