看下面这个问题（动态连续和查询）：
有一个数组A（长度为n），要求进行两种操作：
add(i,x)：让Ai增大x；
query(a,b)：询问Aa+Aa+1+...+Ab的和；
若进行模拟，则每次query操作的最坏的时间复杂度为O(n)，在n较大时速度较慢。用前缀和也不能提高效率（每次add操作最坏为O(n)）。有一种数据结构，可以在O(n)时间里初始化，用O(logn)的速度执行add操作或查询前缀和，从而执行query操作。
首先，我们来介绍“lowbit”。对于一个数x，lowbit(x)是x的二进制里最右面的1所代表的数字，例如lowbit(20)=4,因为20的二进制为10100，最右面的1代表4。怎样计算lowbit呢？很简单，lowbit(x)=x&-x。这是因为负数是用补码保存的，-x就相当于(~x)+1。例（用8位计算）：
20=(00010100)
-20=(11101100)
现在我们来介绍二叉索引树。二叉索引树在程序中也是用数组来保存的。
（画得难看请见谅）
图中，深灰色方块代表树中的结点（结点0为虚拟结点），灰色线段代表树中的边。这些边并不需要显式保存；对于一个节点x，若它是父结点的左子结点，则父结点编号为x-lowbit(x)，否则为x+lowbit(x)。图中的每个结点左侧都有一个白色长条（包括它自己），如结点4的长条为1~4，节点3的长条为3~3。不难发现，结点x的长条为(x-lowbit(x)+1)~x。
然后，我们用一个数组S储存每个结点的白色长条内的所有数的和。例如，S4=A1+A2+A3+A4。这样，就可以使用一个辅助的前缀和数组,在O(n)时间内从左到右初始化S数组。代码如下：
int n;
int S[maxn],A[mxan],S1[maxn];
int begin()
{
memset(S1,0,sizeof(S1));
for(int i=1;i<=n;i++)
{
S1[i]=S1[i-1]+A[i];
S[i]=S1[i]-S1[i-lowbit(i)];
}
}
最后让我们来实现add操作和查询操作。对于某个add操作的结点i，它的修改会影响到那些结点呢？很显然，在它下面的结点（lowbit比它小）不会受到影响，在它左边的结点也不会受到影响，所以只需要考虑在它右边且lowbit比它大的第一个结点，这个结点的白色长条一定覆盖x。很显然，这个结点的编号为i+lowbit(i)。
接下来，x结点不需要考虑了，让我们来考虑i+lowbit(i)结点。与上面一样，只需要考虑在它右边且lowbit比它大的第一个结点，所以只需要让i+=lowbit(i)。代码如下：
void add(int i,int x)
{
//若需要其他操作，可以加一句：
//A[i]+=x;
while(i<=n)
{
S[i]+=x;i+=lowbit(i);
}
}
查询前缀和的方法与之类似，只是i+=lowbit(i);改成了i-=lowbit(i);这里不再介绍证明方法，与上面类似。代码如下：
int query2(int i)
{
int sum=0;
while(i!=0)
{
sum+=S[i];i-=lowbit(i);
}
return sum;
}
int query(int l,int r)
{
return query2(r)-query2(l-1);
}
最后，若有建议请提出。