引入问题
给出一个长度为n的数组，完成以下两种操作：
- 将第i个数加上k
- 输出区间[i,j][i,j]内每个数的和
朴素算法
单点修改：O(1)O(1)
区间查询：O(n)O(n)
使用树状数组
单点修改：O(logn)O(logn)
区间查询：O(logn)O(logn)**
前置知识
lowbit()lowbit()运算：非负整数xx在二进制表示下最低位1及其后面的0构成的数值。
举例说明：
lowbit(12)=lowbit([1100]2)=[100]2=4lowbit(12)=lowbit([1100]2)=[100]2=4
函数实现：
int lowbit(int x)
{
return x & -x;
}
树状数组思想
树状数组的本质思想是使用树结构维护”前缀和”，从而把时间复杂度降为O(logn)O(logn)。
对于一个序列，对其建立如下树形结构：
每个结点t[x]保存以x为根的子树中叶结点值的和
每个结点覆盖的长度为lowbit(x)
t[x]结点的父结点为t[x + lowbit(x)]
树的深度为log2n+1log2n+1
树状数组操作
add(x, k)表示将序列中第x个数加上k。
以add(3, 5)为例：
在整棵树上维护这个值，需要一层一层向上找到父结点，并将这些结点上的t[x]值都加上k，这样保证计算区间和时的结果正确。时间复杂度为O(logn)O(logn)。
void add(int x, int k)
{
for(int i = x; i <= n; i += lowbit(i))
t[i] += k;
}
ask(x)表示将查询序列前x个数的和
以ask(7)为例：
查询这个点的前缀和，需要从这个点向左上找到上一个结点，将加上其结点的值。向左上找到上一个结点，只需要将下标 x -= lowbit(x)，例如 7 - lowbit(7) = 6。
int ask(int x)
{
int sum = 0;
for(int i = x; i; i -= lowbit(i))
sum += t[i];
return sum;
}