树状数组

时间：2021-06-06 16:35:04 阅读：10 评论：0 收藏：0 [点我收藏+]

时间复杂度：o(logn)

支持：

1.单点修改

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

对 $技术分享图片$ 进行区间查询只需查询 $技术分享图片$ 和 $技术分享图片$ 然后相减即可（前缀和就是这样进行区间查询的），所以我们可以把区间查询问题转化为求前n项和的问题。

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