明白树状数组有什么作用？

1. 使得某个位置上的数加上一个数$\ \ \ 时间复杂度：O(logn)$
2. 求某一个前缀和$\ \ \ 时间复杂度O(logn)$

相比于前缀和，它的优势在于可以在某个位置上加上一个数，整体时间复杂度为$O(logn)$，而前缀和整体时间复杂度为$O(n^2)$，就会快很多。

如何理解？

我们通过一张图来演示：

树状数组

第3层:                                      |8|
                               /         /  / |                     
第2层:                 |4|             /   /  |
                  /   / |           /     /   |
第1层:       |2|     /  |        |6|     /    |
          /   |     /   |      /  |     /     |
第0层:  |1|   |   |3|   |   |5|   |   |7|     |
         |    |    |    |    |    |    |      |
原数组: |1|  |2|  |3|  |4|  |5|  |6|  |7|    |8|  

介绍两个数组：

1. $C[x]：$$x$的二进制表示中最后有k个$0$，表示$x$在树状数组上的第k层，也就等价于$(x - 2^k, \ x]$的和。
2. $A[x]：$原数组。

关于$C[x]$中$(x - 2^k, \ x]$的和可以用lowbit(x)来转化为$(x - lowbit(x), \ x]$。

lowbit(x)的定义就是求出一个数二进制表示下末尾有多少个$0$，并返回$x^k（k表示0的个数）$

核心：$\color{#FF0000}{C[x]表示的是(x−lowbit(x), x]这一段的和}$

于是就有以下式子：）

C[1] = A[1]
C[2] = A[2] + C[1] = A[1] + A[2];
C[3] = A[3]
C[4] = C[3] + C[2] + A[4] = A[1] + A[2] + A[3] + A[4]

如何求出一个区间内的值？

我们知道C[x]表示为(x - lowbit(x), x]区间的和，在数轴上画出来
                          x - lowbit(x)         x 
                              ↓                 ↓
|-----------------------------(-----------------)--------|
1                                                        n

sum[x]:从1 ~ x的所有数之和，也就是前缀和
sum[x] += C[x];  // 我们已经加上了(x - lowbit(x), x]这一段的区间和，还剩下[1, x - lowbit(x)]这一段
// 在将这一段加上，我们就会发现其实它就是一个递归的过程，对吧。
sum[x] = C[x] + C[x - lowbit(x)] + ...

比如说:
sum[7] = C[7] + C[6] + C[4];

代码实现（核心代码）

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

int add(int x, int k)  // 添加函数
{
    for(int i = x; i <= n; i += lowbit(i) ) tr[i] += k;
}

int query(int x)  // 查询函数求区间[1, x]内的总和
{
    LL res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}