树状数组入门讲解

平常我们会遇到一些对数组进行维护查询的操作，比较常见的，修改某点的值、求某个区间的和。

即给定一个n个元素的数组$A_1、A_2、..., A_n$，你的任务是设计一个数据结构，支持以下两种操作：

1. $Add(x,d)$操作：让$A_x$增加$d$。
2. $Query(L,R)$：计算$A_L+A_{L+1}+...+A_R$。

如果按简单的前缀和处理，修改操作是$O(1)$，区间查询操作是$O(n)$，当操作次数为m时，最坏的时间复杂度是$O(mn)$，n很大时显然无法接受。如何让Query和Add都能快速完成呢？有一种称为二叉搜索树(Binary Indexed Tree, BIT)的数据结构（俗称树状数组），可以很好地解决这个问题。为此，我们需要先介绍lowbit。

lowbit

树状数组入门讲解

原文：https://www.cnblogs.com/lfri/p/10655077.html