树状数组确实是个好东西啊，以前搞比赛的时候了解过它，会套用模版，但确没有深入理解这个东西，先学会用轮子，然后再学造轮子嘛，这段时间再回头研究了一下，发现二进制在算法中真的是的好东西，它可以使算法的时间复杂度降到的二进制表示中的相关，大家都知道，求一个二进制中的的个数，这个时间复杂度为。
有时候觉得树状数组难以理解，我觉得根本原因是：你还在用十进制的视角来看待树状数组，下面的讲解我会时刻提醒你转换到二进制的视角，而且我也不会先给你上图，因为你的视角在二进制，你就会发现树状数组就是一个普通的东西，不需要图你就能理解。
首先我们搞明白树状数组是用来干嘛的，现在有一个这样的问题：有一个数组，下标从到，现在给你次修改，次查询，修改的话是修改数组中某一个元素的值；查询的话是查询数组中任意一个区间的和，。
这个问题很常见，首先分析下朴素做法的时间复杂度，修改是的时间复杂度，而查询的话是的复杂度，总体时间复杂度为；可能你会想到前缀和来优化这个查询，我们也来分析下，查询的话是的复杂度，而修改的时候修改一个点，那么在之后的所有前缀和都要更新，所以修改的时间复杂度是，总体时间复杂度还是。
可以发现，两种做法中，要么查询是，修改是；要么修改是，查询是。那么就有没有一种做法可以综合一下这两种朴素做法，然后整体时间复杂度可以降一个数量级呢？有的，对，就是树状数组。
这里我们先不管树状数组这种数据结构到底是什么，先来了解下这个函数，你也先不要问这个函数到底在树状数组中有什么用；
顾名思义，这个函数的功能就是求某一个数的二进制表示中最低的一位，举个例子，，它的二进制为，那么就返回，因为最后一位表示。
那么怎么求呢？
- 还记得 剑指Offer66题之每日6题 - 第二天中的第五题中讲过的如何消掉最后一位吗？我们就是先消掉最后一位，然后再用原数减去消掉最后一位后的数，答案就是的结果；
- 第二种方法就是计算机组成原理课上老师教过我们求负数的补码的简便方法：把这个数的二进制写出来，然后从右向左找到第一个(这个就是我们要求的结果，但是现在表示不出来，后来的操作就是让这个能表示出来)，这个不要动和这个右边的二进制不变，左边的二进制依次取反，这样就求出的一个数的补码，说这个方法主要是让我们理解一个负数的补码在二进制上的特征，然后我们把这个负数对应的正数与该负数与运算一下，由于这个的左边的二进制与正数的原码对应的部分是相反的，所以相与一定都为0,；由于这个和这个右边的二进制都是不变的，因此，相与后还是原来的样子，故，这样搞出来的结果就是的结果。
两种方法对应的代码依次如下：
在树状数组的问题模型中已经有所提及了，就是那两种不同做法的一个综合；
先定义一些东西：是原数组，是新开的一个数组，这个数组代表后缀和(问题模型中是用的前缀和，这里要用后缀和，具体原因马上就知道了)；
二进制的视角：一个数，假设，它的二进制为，我们把它表示成累加的形式，这样是可以的，那么我们要求前项的和是不是可以这样求：
注意括号中的元素个数，是不是个加个，和是不是很像，不知你们发现了吗，就是的结果，是的结果。求和的时候我们总是把拆分成这样的几段区间和来计算，而如何去确定这些区间的起点和长度呢？就是根据的二进制来的(不懂的可以再看下上面举的例子)，二进制怎么拆的，你就怎么拆分，而拆分二进制就要用到上面说的函数了。这里也可以顺理成章得给出数组的表示了。
这里也可以顺理成章得给出数组的表示了，表示从第个元素向前数个元素，这一段的和，这就是上面说的区间和，只不过这个区间是靠右端点的；你可能又会想，不是说区间是靠右端点的吗，是后缀和啊，那中间的这些区间怎么定义？其实递归定义就好了，比如说，你把去掉，不就是，这个区间不就靠右端点了吗，。
其实你把所有的数字都看成二进制，很好理解的。
设计一种数据结构，需要的操作无非就是”增删改查“，这里只讨论查询和修改操作具体是怎么实现的；
这里说的查询是查询任一区间的和，由于区间和具有可加减性，故转化为求前缀和；
查询前缀和刚刚在树状数组的思想中已经说过了，就是把大区间分成几段长度不等的小区间，然后求和。区间的个数为，所以查询的时间复杂度为。
修改某一位置上的元素的时间复杂度为，但是要更新数组，不然查询的时间复杂度就会变高。更新的方法就要提一下树状数组的性质了和树状数组那张经典的图片了。
这张图片中已经把数组的后缀和这个含义已经表达得很清楚了。这个时候你再把查询操作对应到这张图上，然后看着二进制来操作，是不是就可以很直白地理解上面所说的查询操作了！
我们从这张图中可以得到树状数组的如下性质：
- 后缀和的长度是2的幂；
- 上一层后缀和的长度是下一层后缀和长度的两倍；
- 下一层后缀和只要补上自己后缀和的长度就可以得到上面层的后缀和(图中的虚框框)，注意，是上面的后缀和，而不是上一层的后缀和，这个性质就是更新操作的依据；
- 最后一位右边有多少个(可以用表示)就表示这一层有多少个直系子层(子层的意思就是这一层的和包含下面某一层的和)。
我暂时就写这么多吧，这个时候我们再来说更新操作；
更新的时候只要更新修改这个点会影响到的那些后缀和(数组)，假设现在修改这个点，依据树状数组的性质三，它影响的直系父层就是，但是它肯定不是只影响直系父层，上面所有包含这一层和的层都要更新，但是我们把这个更新传递给直系父层,这个点的直系父层是，依次类推地更新就行了。
这里我留一个问题给大家，如何寻找某一层的所有直系子层，大家可以看这个图思考一下，想一想。
先给一个题目背景，然后运用树状数组来高效解决这个问题。
题目：
输入一个数组，然后给你一些操作，操作有查询和修改两种。具体见输入格式。
输入格式：
第一行输入，表示数组长度；
第二行输入个整数；
第三行输入，表示操作的次数；
接下来行，每行输入三个东西，字符，，。表示查询到这段区间和；表示修改第个元素为。
输出格式：
对于每个查询，输出结果。
Code:
之前好多同学和我说看不懂C++的代码，主要还是STL那块，所以我用C来写了这个代码。
C++代码
看很多人想看C++如何实现，其实把上面的代码用G++编译，一点问题。
用现代C++写代码方面会很简洁，尤其是引入了很多机制，例如表达式，模板的增强等等。随着C++20的到来，代码会更优雅，但是思想永远是最重要的，有时候代码好看与简洁并不代表好用易懂，下面的代码我是为了Modern C++ 而 ModernC++的，看起来很晦涩，实际的开发中是绝对不会这么用的。
查询区间和以前的做法要么就是查询很慢，修改很快，那怎么办呢，那就存储前缀和来提高查询速度，但这样一来修改了之后要更新这些前缀和，更新又很慢；
数组数组就完美地综合了这两种做法，存储后缀和，更新后缀和，通过来限定后缀和的长度，利用二进制使得查询、更新的时间复杂度都在。
我已经把我所理解的树状数组尽可能详细地写出来了，之中可能有些表述不清楚的地方，大家可以在评论区留言。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/9871.html