引入

场景

给出一个长度为 n 的数组，完成以下两种操作

• 将第 x 个数加上 k
• 输出区间[x,y]内每个数的和

最简单的方式自然是前缀和，但暂时不讨论它，我们引入新的算法---树状数组

下面以短数组举例

|1|2|1|5|2|5|2|5|

每次单次累加就很慢了，所以我们可以将相邻的数字累加，形成上一层的数字，再继续累加形成上一层，如下所示

|                       23                      |
|         **9**         |           14          |
|     3     |     6     |   **7**   |     7     |
|  1  |  2  |  1  |  5  |  2  |  5  |**2**|  5  |

|  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  | # 下标

如果是求下标7与之前的数字的和，直接累加9+7+2即可

排除

在这样的数组结构中：

|                       23                      |
|           9           |         **14**        |
|     3     |   **6**   |     7     |   **7**   |
|  1  |**2**|  1  |**5**|  2  |**5**|  2  |**5**|

不少数字其实是用不到的，例如：上面有两个数字的和的时候，右边的数字可以用上面的数字减去左边的数字获得

所以最后可以得到这样的数组：

|1|3|1|9|2|7|2|23|

这个数组就是树状数组，树状数组和原始数组刚好一样长

得到这个树状数组，我们如何去做增加删除呢，如果一层一层加上去不是更麻烦吗，这就需要关键函数lowbit

lowBit

x & (-x)

这就是lowbit函数

表示非负整数x在二进制表示下最低位以及其后面的0构成的数值

例如：

• lowbit(6)，也就是lowbit(110)，它的值就是二进制10 ，也就是2
• lowbit(44)，也就是lowbit(101100)，它的值就是二进制100，也就是4

原理

简单解释一下lowbit的x & (-x)究竟发生了什么

在计算机底层中，负数是以补码的形式存储的，补码就是对它每个位数取反¹再加1

例如我们现在求-12在计算机中存储的真实的值（就是求12的补码），12的二进制是00001100，取反就是11110011，再加1就是11110100，所以这个11110100就是-12在计算中中存储的真实的值

00001100 # 12
11110011 # 每一位取反，反码
11110100 # 反码+1，补码

至于为什么要+1，因为二进制只能存储偶数个数字，而除了正数和负数之外还有0，所以负数就匀了1个空间出来给0，所以整数类型正数负数范围通常差1。例如c++的int范围是-2^15 到 2^15 - 1

回到正题，x & (-x)究竟发生了什么

我们把12和-12的值放在一起看看

00001100 # 12
11110100 # -12
00000100 # 12 & -12

我们可以得到

这样的操作会得到，整数x的，最低位1以及后面的0所构成的数值

应用

层级规律

依旧用上面的例子距离：

|                       23                      |
|           9           |           14          |
|     3     |     6     |     7     |     7     |
|  1  |  2  |  1  |  5  |  2  |  5  |  2  |  5  |

成为树状数组后，将他们的下标列出：

	4   |                       9                       |
	3   |           4           |           8           |
	2   |     2     |     X     |     6     |     X     |
    1   |  1  |  X  |  3  |  X  |  5  |  X  |  7  |  x  |

他们的二进制：

	4   |                       1000                       |
	3   |           100          |             X           |
	2   |     10     |     X     |     110     |     X     |
    1   |  1  |  X  |  11  |  X  | 101 |  X  |  111  |  x  |

可以看到我上面的数组，在旁边我给树状数组加了一个层级，这个层级实际上就是下标的lowbit的长度

即：1层的lowbit都是1，2层的lowbit都是10，3层的lowbit都是100…

通过上面的规律我们可以衍生出后文的两个子规律

index + lowbit(index)

换一张图表：

                            s8
               s4              |
        s2      |       s6      |
        |       |       |       | 
    s1  |   s3  |   s5  |   s7  |
    |   |   |   |   |   |   |   |
    a1  a2  a3  a4  a5  a6  a7  a8

我们现在希望构造树状数组，从a数组转换成s数组，这时候就需要index + lowbit(index)（一直往上累加）

沿着链一直往上走，把a1放入s1，s2，s4，s8，把a2放入s2，s4，s8…把a7放入s8

这个下标是如何生成的呢？

下一个下标就是index+lowbit(index)

1的lowbit就是2，那么下一个节点就是2，2的lowbit是2，下一个节点就是4，4的lowbit就是4，下一个节点就是8，故得到s1，s2，s4，s8

这是一个非常巧合的东西，index+lowbit(index)意味着，index的二进制中的最低位1，要进位了，所以会导致上移一层

index - lowbit(index)

如果我们希望下标1到7的前缀和，用树状数组怎么求？

7的二进制是111，按照下图我们应该累加s7，s6，s4

                              s8
                s4              |
        s2      |       s6      |
        |       |       |       | 
    s1  |   s3  |   s5  |   s7  |
    |   |   |   |   |   |   |   |
    a1  a2  a3  a4  a5  a6  a7  a8

s7，s6，s4的二进制是111，110和100 ，也就是说，累加的上一个下标可以通过index - lowbit(index)来得到

7的下标是111，lowbit是1，那么减去lowbit就是110，也就是下标6二进制是110，110的lowbit是10，110减去10就是100也就是4

模板

int lowbit(int x) {
	return x & (-x);
}

// 单点增加数据，在x下标的原数组上增加k
// 其中x是以1开头的下标，x += lowbit(x)就是移动到下一层
void add(int x, int k) {
	for (; x <= n; x += lowbit(x) ) arr[x] += k;
}

// 前缀和查询
long long sum(int x) {
    long long ans = 0; // 开long long，省的爆int
    for (int i = x;i;i -= lowbit (i)) ans += c[i];
    return ans;
}