对于n次前缀和的查询，时间复杂度为O(nlogn)
接下来讲解单点更新值
对于输入编号为x的值，要求为它的值附加一个value值，我们把图再一次拿下来
假设x==2，value==5，那么我们先找到A[2]的位置，通过观察我们得知，如果修改了A[2]的值，那么管辖A[2]的C[2]，C[4]，C[8]的前缀和都要加上value（所有的祖先节点），那么和查询类似，我们如何得到C2的所有祖先节点呢（因为C2和A2的下标相同所以更新时查询从C[x]开始），依旧是上述的巧妙的方法，但是我们把它倒过来
对于要更新x位置的值，我们把x转换成二进制，不断对二进制最后一个1的位置+1，直到达到数组下标的最大值n结束
对于给出的例子x==2，假设数组下标上限n==8，x转换成二进制后等于0010（C2），对末尾1的位置进行+1，得到0100（C4），对末尾的1的位置进行+1，得到1000（C8），循环结束，对C2，C4，C8的前缀和都要加上value，当然不能忘记对A[2]的值+value，单点更新值过程结束
给出代码
void update(int x, int value){ A[x] += value; //不能忘了对A数组进行维护，尽善尽美嘛 while(x <= n){ C[x] += value; x += lowbit(x); } }对于n次更新操作，时间复杂度同样为O(nlogn)
这里有一个注意事项，我们对于求前缀和与单点更新时，树状数组C是拿来直接使用的，那么问题来了，树什么时候建立好的，我怎么不知道？?事实上，对于一个输入的数组A，我们一次读取的过程，就可以想成是一个不断更新值的过程（把A1~An从0更新成我们输入的A[i]），所以一边读入A[i]，一边将C[i]涉及到的祖先节点值更新，完成输入后树状数组C也就建立成功了
完整代码如下：
#include<stdio.h> #include<string.h> int a[10005]; int c[10005]; int n; int lowbit(int x){ return x&(-x); } int getSum(int x){ int ans = 0; while(x > 0){ ans += c[x]; x -= lowbit(x); } return ans; } void update(int x, int value){ a[x] += value; while(x <= n){ c[x] += value; x += lowbit(x); } } int main(){ while(scanf("%d", &n)!=EOF){ //用于测试n == 8 memset(a, 0, sizeof(a)); memset(c, 0, sizeof(c)); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); //a[i]的值根据具体题目自己安排测试可以1，2，3，4，5，6，7，8 update(i, a[i]); //输入的过程就是更新的过程 } int ans = getSum(n-1); //用于测试输出n-1的前缀和 输出28 printf("%d\n", ans); } return 0; }---恢复内容结束---