点击上方蓝字，关注并星标，和我一起学技术。
大家好，今天给大家介绍一种新的非常非常实用的数据结构。大家学会了之后，应对各大公司的面试题以及LeetCode等网站的刷题都会用得到，也是广大acmer的入门数据结构之一。
这个数据结构就是树状数组，它的实现非常简单，可以很方便地在的时间内实现各种查询。它有很多种变体，今天我们介绍它最简单最基础的原理。
经典例题
树状数组最基础的用途是单点更新，区间查询。也就是我们更新的时候只更新一个位置，查询的时候查询的是某一个区间。
我们用HDU1166这道经典的题目来举例，假设我们现在检测敌方军队的N个兵营。兵营当中的士兵数量是实时变动的，比如某一时刻，第3个兵营增加了100个士兵，某一时刻第5个兵营减少了30个士兵。上司随时可能会对我们进行询问，询问我们当下[x, y]区间内的兵营一共有多少士兵。
很显然我们可以用一个数组来记录所有兵营的士兵数量，但是这里的查询是一个区间和，这个会比较麻烦。如果不采用任何数据结构的话，我们需要使用循环来进行求和，但是循环的开销是，如果查询的次数很多，性能就扛不住了。而使用树状数组我们可以在的时间内求到这个区间和。
原理推导
接下来，我们推导一下这个数据结构的原理。
首先对于求区间和的问题，我们可以简单做一个转化，我们可以把求[x, y]区间和的问题转化成求[0, y]，[0, x]区间和的问题，这两个区间和一减就是答案。所以问题就转化成了快速求[0, x]区间和的问题，这个问题有一个经典的解法是通过线段树来实现。线段树每一个节点代表一个区间，这样我们只需要沿着树结构选择少量的节点就可以获取到我们想要的区间结果了。
线段树
我们来看一张示例图。
这是一张经典的线段图的图，从图中我们可以基本理解线段树的思想。简而言之就是通过构建二叉树，来管理一个区间。二叉树当中的每一个节点都对应一段区间，这样的话我们可以通过若干节点的组合拼出我们想要的区间的结果。举个例子来说，假设我们想要查询[1-6]这个区间的区间和，那么我们只需要访问下图当中的两个节点就可以了，而不再需要通过一重循环来计算了。
对于含有N个节点的区间来说，我们构建的线段树的树深是层，我们需要查询的节点数量也是常数个，所以总的查询复杂度是，要比使用循环的复杂度小得多。
关于线段树的原理，我们曾经也在文章当中介绍过，感兴趣的小伙伴可以通过下方传送门回顾一下。
原创 | ACMer不得不会的线段树，究竟是种怎样的数据结构？
树状数组的由来
我们刚刚说了这么多都是线段树，它和我们今天要讲的树状数组有什么关系呢？
当然是有关系的，不然“树状”两个字是如何来的？树状数组本质上就是把上述的线段树通过某种方式存储在数组当中，先考考大家一个问题，对于N个节点的区间构建的线段树，它一共需要多少个节点？
答案是2N-1个，我们想要用长度为N的数组来存储肯定是存不下的，为了能够存下，我们需要删除一些节点，对它的计算方式进行一个小小的调整，让它更加节省空间。调整之后的结果如下：
大家有没有看出不同来？我们删去了N-1个节点，使得剩下的节点数量刚好是N个。树状数组的核心原理就是通过这N个节点来压缩树结构。其他的原理大同小异，每个节点依旧保存对应的线段的区间和，比如2这个节点存储的就是[1, 2]的和，而4就是存储的[1, 4]的和。
查询
我们根据这张图来推导一下树状数组的运行原理，这样会比较直观。假设我们要求[1, 7]区间的和，我们应该怎么操作？很明显，[1, 7]可以分解成[1, 4], [5, 6]和7这三个区间的和，对应到4、6和7这三个节点。这个我想大家都能看得明白，但是有一点估计会觉得很疑惑，就是4、6、7这三个数是怎么来的呢？
7还好，我们都知道就是查找的边界本身，但是4和6呢？
其实很简单，我们把7转化成二进制是。我们去掉7二进制末尾最后一个1的结果是6，再去掉6末尾最后一个1的结果是4，再去掉4的末尾就得到了0，0不再包含二进制位，所以计算结束。
对于我们要查询的K而言，我们只需要把K转化成二进制，然后从末尾开始一个一个移除为1的二进制位，这样得到的就是覆盖[1, K]区间的关键节点。我们只需要把这些节点的结果相加，就得到了[1, K]的区间和。
更新
以上是查询的过程，我们都理解了之后，接下来再看看更新。
更新其实是查询的反向操作，比如我们要更新3这个位置，这个操作会影响3右侧所有的节点。所以我们需要从3开始一层一层向上（右）更新，一直更新到N。我在下图当中用红笔画了一下它的更新过程。
其实很好理解，也就是沿着树向右的方向更新，一直更新到根节点。我们把它更新的路径写出来看看，从3，到4，再到8，再到16……
这个序列看起来好像也没什么规律，不要急，我们还是要从二进制入手。其中3的二进制表达是，它的末位是1，而3+1=4。对于4而言它的二进制是，它的末位是4，4+4=8。发现规律了吗？其实更新的操作就是和查询相反，每一次加上末位的二进制位。
如果不相信，我们还可以继续做实验，比如我们要更新位置5。它的更新轨迹是从5到6，再从6到8，到16……
5的末位二进制是1，所以5+1得到了6。6的末位二进制是2，6+2得到了8。是不是觉得很神奇？但道理并不难，我们加上最后一位的二进制位必然会发生进位，这个进位的过程就相当于我们沿着树向右一层的过程。同理，减去末位二进制的过程就相当于沿着树往左走的过程，不管是往左还是往右，每次移动的距离都是通过二进制的末位的1来决定的。
所以剩下的问题是怎么求一个数二进制末位的1？
lowbit
在树状数组当中，我们把求解二进制末位1的操作称为lowbit函数。这个lowbit函数的代码非常简单，只有一行，但是这一行代码想看明白却非常不容易，需要很多背景知识。我们一点一点开始给大家讲明白。
原码、反码、补码
首先需要了解一下计算机系统当中int数存储的方式，也就是原码、反码和补码。所谓原码就是原本的二进制表示，最高位表示符号位，0表示正数，1表示负数。反码也很好理解，也就是把原码除了符号位之外的位进行0变1，1变0的转化，补码则是在反码的基础上再加上1。
这里有一点需要注意一下，补码的操作只针对负数，正数的补码就是原码，不会进行取反以及+1操作。计算机系统为什么要这样设定呢？其实很简单为了统一加减法。比如说我们把一个时钟从10点拨到8点有两种拨法，一种是逆时针拨2格，一种是顺时针拨10格。因为，也就是我们绕了一圈又回来了。
计算机的整型的计算也是一样，比如32位的int，当我们加法超过32位int能表示范围的时候会自动高位溢出，这里面的道理和拨时钟是一样的，我们要减去一个数，等价于我们加上它的补码。这样就统一了二进制的加减法，可以提高运算以及转码的效率。
我们来举个例子，比如说我们现在一共有4位int，加上符号位就是5位。我们要计算14 - 7，首先我们计算14的补码，14是正数，它的补码等于它源码，14-7可以看成是14 + (-7)。-7是负数，我们根据刚才的公式计算它的源码是，主要最高位是符号位，它的反码是，它的补码是。
最后我们来计算，由于超过了位数的限制，最高位溢出，得到的结果就是，也就是7。如果大家对补码的概念记不清了，就回想一下时钟的例子，肯定可以想起来。
位运算与补码
理解了补码之后，我们就可以来思考如何求解lowbit了。
我们随便来举个例子，假设还是7好了，它的二进制是，最高位是符号位。我们希望得到的lowbit只有一位是1，其余全是0。如果我们希望可以通过位运算来得到它的话，显然使用&最有可能。如果使用&来求解lowbit的话，那么需要和它进行&运算的数应该是。
不知道大家看到这个数有没有觉得一点熟悉，这个不就是-7的补码表示么？的确如此，大家不相信也可以尝试一下其他的数，我们的lowbit就是这么算的，非常非常简单x & (-x)。
但是如果这背后不理解补码的概念的话，直接硬啃是很困难的，你会非常疑惑这个-x是怎么来的。
代码实现
最后， 我们把刚才所有列的内容整理一下使用代码来进行实现。
你会发现看代码真的很简单，所以很多人理解不了都是硬背的代码。老实讲也不是不可以，但是还是理解原理会掌握得更加深刻一些。
const int N = 100050;
int arr[N] = {0};
int lowbit(x) {
return x & (-x);
}
void update(int u, int x) {
for (int i = u; i < N; i+= lowbit(i)) {
arr[i] += x;
}
}
int query(int u) {
int ret = 0;
for (int i = u; i > 0; i -= lowbit(i)) {
ret += arr[i];
}
return ret;
}
怎么样，代码是不是比你们想的还要简单？
这也是树状数组的最大优势，其实树状数组能做的事情线段树全部都可以做。但是它的代码和线段树相比要简单非常多，也更加方便调试，因此能够使用树状数组解决问题的时候，大家都不愿意使用线段树。毕竟赛场上时间就是名次，大家都会倾向于使用自己更有把握的数据结构。
今天介绍的只是树状数组的基础应用，树状数组并不只是可以使用单点更新区间查询的场景，一样可以进行区间更新、单点查询以及区间更新区间查询，只不过需要稍稍进行一下改进。这些内容不少，本期写不下了，我们放到下篇文章和大家聊吧。
今天的文章就到这里，衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话，请来一个三连支持吧~（点赞、在看、转发）
发表评论 取消回复