树状数组概念及操作(2)

上爬就可以找到所有的子区间了。左上角区间对应的二进制为 x-lowbit(x),这项操作就是将x的末尾的1变为0，其它位置不变。如6=110 6-6&-6=100，就像是先提取末尾的1，再做减法砍掉一样。对应的查询就可以这样写
int lowbit()
{
return x&-x;
}
Void query(x)
{
 Int ans=0;
 while(x>0)
 {
ans =c[x];
x=x-lowbit(x);
}
}
 这里的c[x]代表6—1图中的每个小区间。这样我们就完成了查询操作，接下来只需要搞定c[]的求法和修改操作就行了。
 开始序列都为0，若修改一个位置的值，那么它后面的区间都会受到影响，因此我们要修改后面的区间。在这里要找到一个区间的右上角的区间在哪，然后修改，再往后找。可以归纳出右上角的编号为x lowbit(x)。特殊地，当修改1号位置，如加1，那么其后面2^k,
K=1,2,3,4，即10，100，100，1000所在的区间都被加1。当查询sum[5]时，从6-1图中可以看出，sum[5]为100，101两区间内的元素和，而101区间没有被 1，最后的查询结果为
1． 我们在修改区间时是修改大的区间1，2，4，8，16，后面要查的数可以由前面这些区间
拆分。因此修改操作为log2(n)。当要修改的位置不是1时也是同样的道理。照这样就保证了修改的快速性。此时没添加一个数，就执行一次修改操作，c[](每段区间内的值)就可以顺便算出来了。修改操作代码如下，假设每次加1
Voi change(int x)
{
While(x<=n)
{
c[x]
x =lowbit(x);
}
}
最后总结一下：当要修改x位置时，执行一次change(x)。当要查询x—y内元素和时，
可以执行两次查询操作，再减去多余的部分就行了，query(y)-query(x-1);
至此这个问题就得到完美解决了。
#include<cstdio>
#include<cstring>
#define N 1001
using namespace std;
int n,q;
int a[N],c[N];
int query(int x)
{
int ret=0;
while(x>0)
{
ret =c[x];
x-=x&(-x);
}