二十天左右的集训结束了，虽然学校的教学完全学不到任何东西，但得承认通过自学学到了不少东西。
自学的第一个知识就是树状数组，它可以在 O(\log n) 的时间内完成单点修改和前缀和查询。由于码量奇少，在搭配上差分数组和权值数组，就能实现许多骚操作。
树状数组的结构
以下以维护区间和为例。假设使用c[i]数组作为树状数组，它存储了原数组的某一段区间和。右端点是 i，左端点是 i - lowbit(i) + 1，其中 lowbit(i) 是 i 的二进制表示中最低位的 1 的位置。比方说 6 = (110)_2，那么 lowbit(6) = 2 = (10)_2。
在树状数组中，每一个 c[i] 都指向父亲 c[i+lowbit(i)]。在区间和的情况下，c[i] 存储了 [i-lowbit(i)+1, i] 的区间和。比如 c[4] 存储了 [1, 4] 的区间和。如下图所示：
其中每一层c[i]都等于它的子节点之和与原数组以i为下标的数值之和，即c[i] = a[i]+\sum_{j=i-lowbit(i)+1}^{i}c[j]。
摸清楚结构后，树状数组的单点修改和前缀和查询就非常好写了。对于单点修改，只需自底向上更新父节点即可。对于前缀和查询则反过来自顶向下累加即可。
树状数组的实现
int lowbit(int x){
return x&-x;
}
int getsum(int x){
int ans=0;
while(x>0){
ans+=c[x];
x=x-lowbit(x);
}return ans;
}
void add(int x,int k){
while(x<=n){
c[x]+=k;
x+=lowbit(x);
}
}
树状数组的其他应用
区间加
如果题目要求实现这么个操作：给定一个区间 [l, r]，使得 a[l], a[l+1], \cdots, a[r] 都加上 k。这时候就可以使用差分数组和树状数组来实现。
差分数组是指原数组的相邻两个元素之差，即 d[i] = a[i] - a[i-1]。这时，可以以d[i]为原数组建立树状数组，然后对于区间 [l, r]，只需在 d[l] 加上 k，在 d[r+1] 减去 k 即可。这样就将区间加的操作转化为了单点加。
void f(int l,int r,int k){
add(l,k);
add(r+1,-k);
}
接下来是查询的问题，由d[i]=a[i]-a[i-1]可得a[i]=d[i]+d[i-1]+d[i-2]+\cdots+d[1]，所以只需求出d[1],d[2],\cdots,d[i]的前缀和即可得到a[1],a[2],\cdots,a[i]。
但这样只能求出某一个a[i]，如果要求a[l...r]的和，那么一个一个求时间上会很慢。甚至不如不用树状数组，这时候就需要维护第二个树状数组d[i]*i，原因请看公式：
我们知道
所以
可见要求出a[l...r]的和，只需求出\sum_{i=l}^{r}d[i]和\sum_{i=l}^{r}id[i]即可。因此，我们需要维护两个树状数组，一个维护d[i]的前缀和，一个维护d[i]*i的前缀和。