CSDN博客链接：http://t.csdn.cn/f4OaS

树状数组问题

树状数组一般用于解决：给定一个数组，修改其中某些元素的值，求该数组某个区间的和的问题。如果我们用暴力方法来解决，那么每次查询的时间复杂度都是   ，以这种方法一旦数值过大，就会时间超限。于是我们就要用到树状数组的思路，它每次查询的时间复杂度就是，这样就可以解决数值比较大的问题了。

那么我们来看一道模板例题：https://www.luogu.com.cn/problem/P3374，题干如下：

题目描述

如题，已知一个数列，你需要进行下面两种操作：

• 将某一个数加上

• 求出某区间每一个数的和

输入格式

第一行包含两个正整数 ，分别表示该数列数字的个数和操作的总个数。  

第二行包含 个用空格分隔的整数，其中第 个数字表示数列第 项的初始值。

接下来 行每行包含 个整数，表示一个操作，具体如下：

• 1 x k  含义：将第 个数加上

• 2 x y  含义：输出区间 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 的结果。

样例 #1

样例输入 #1

样例输出 #1

提示

【数据范围】

对于 的数据，，；  

对于 的数据，；  

对于  的数据，。

数据保证对于任意时刻， 的任意子区间（包括长度为和 的子区间）和均在  范围内。

样例说明：

故输出结果14、16

解决方法

 I  暴力（70 pts）

当然，我们也可以用前缀和的方法使查询的时间复杂度降到 $O(1)$ ，但是对于每次修改数组中的数据，复杂度就会变高，所以说整体的时间复杂度基本没有变化。

II 树状数组

树状数组的本质还是一个数组，但是我们可以用以下方法将其看作一个二叉树，数组 $a$ 指的就是原数组， 指的是树状数组：

这个时候我们要用到 函数来计算 的值：

也可以这样写：

然后得出区间和：

向树状数组中添加元素：

这样我们就写好了树状数组的模板。

完整代码如下：

总结

• 树状数组利用二进制更新数组，将时间复杂度降低到 $O(log n)$

• 树状数组每个节点的值就是它的前缀和