树状数组的实现过程
发表时间：2010-05-04 20:25:05 浏览(1370) 评论(0)
树状数组主要用于求解这样一类问题：对于一个数组的元素，进行两种操作，一是对某个元素num[i]加上一个数j，二是询问num[i]加到num[j]的和。
如果用传统的方法求解，会得到一个O(n2)的算法，显然不优!
于是，我们冥思苦想一种能够快速的求解方法。树状数组应运而生！
树状数组是一种充分利用数的位运算的绝妙算法，它的优点在于充分考虑二进制与树形结构的对应关系。
定义数组a[1..n],k表示（i）2的最低位1的位置，则p==1 shl (k-1);例如，(i)2=110011010000，则k=5，p=16。实现方法：p:=(i xor (i-1) and i);a[i]表示从i-p+1到i的元素和。我们就是要维护这样一种性质。
还有一个数组s[1..n]记录从1号元素到i号元素的和。
下面讨论具体实现。
1、插入操作：在i元素上加j。由于i元素的值的变化会影响a[i](因为a[i]是从i-p+1到i的元素和)，因此a[i]:=a[i]+j。并且，a[i+p]的值一定也受了影响（因为i一定在a[i+p]的范围中，易证）。而且要不断调用取新数（i+p）的最低位1位置p’和改变a[i+p+p’]的操作，直到下标的范围超过n。
Function find(x:longint):longint;
Begin
Exit(x xor (x-1) and x); //取x的最低位1并以之构造二进制数p的函数
End;
Procedure ins(x,y:lonignt); //将x位置的数增加y
Begin
While x<n do
Begin
a[x]:=a[x]+y; //影响了a[x]的值
x:=x+find(x); //寻找下一个受影响的元素下标（即x+find(x)）
End;
End；
2、询问操作：询问k到l区间上的元素的和。我们可以用一个过程算出1到i的元素和，算sum[k-1]和sum[l]的值，再相减即可。
因为a[i]记录的是从i-p+1到i的元素和，所以我们可以通过a的值算出sum(x)的值。过程是：加a[i]不断把i二进制表示的最末一位的1变成零，重加和过程，直到i==0，即得到了sum[i]的值。
Function sum(x:longint)：longint;
Var k:longint;
Begin
k:=0; //初始化答案
while x>0 do
Begin
k:=k+a[x]; //答案加上a[x]
x:=x-find(x); //将下标的最莫以为1变为0
End;
Exit(k); //返回答案
End;
整个程序代码如下：
Program treearray;
Var i,j,k,l,n,m:longint;
a:array[1..100000] of longint;
Function find(x:longint):longint;
Begin
Exit(x xor (x-1) and x);
End;
Procedure ins(x,y:lonignt);
Begin
While x<n do
Begin
a[x]:=a[x]+y;
x:=x+find(x);
End;
End；
Function sum(x:longint)：longint;
Var k:longint;
Begin
k:=0;
while x>0 do
Begin
k:=k+a[x];
x:=x-find(x);
End;
Exit(k);
End;
Begin
Read(n,m);
For i:=1 to m do
Begin
Read(j,k);
Ins(j,k);
End;
Read(m);
For i:=1 to m do
Begin
Read(j,k);
Writeln(sum(k)-sum(j-1));
End;
End.
如果用传统的方法求解，会得到一个O(n2)的算法，显然不优!
于是，我们冥思苦想一种能够快速的求解方法。树状数组应运而生！
树状数组是一种充分利用数的位运算的绝妙算法，它的优点在于充分考虑二进制与树形结构的对应关系。
定义数组a[1..n],k表示（i）2的最低位1的位置，则p==1 shl (k-1);例如，(i)2=110011010000，则k=5，p=16。实现方法：p:=(i xor (i-1) and i);a[i]表示从i-p+1到i的元素和。我们就是要维护这样一种性质。
还有一个数组s[1..n]记录从1号元素到i号元素的和。
下面讨论具体实现。
1、插入操作：在i元素上加j。由于i元素的值的变化会影响a[i](因为a[i]是从i-p+1到i的元素和)，因此a[i]:=a[i]+j。并且，a[i+p]的值一定也受了影响（因为i一定在a[i+p]的范围中，易证）。而且要不断调用取新数（i+p）的最低位1位置p’和改变a[i+p+p’]的操作，直到下标的范围超过n。
Function find(x:longint):longint;
Begin
Exit(x xor (x-1) and x); //取x的最低位1并以之构造二进制数p的函数
End;
Procedure ins(x,y:lonignt); //将x位置的数增加y
Begin
While x<n do
Begin
a[x]:=a[x]+y; //影响了a[x]的值
x:=x+find(x); //寻找下一个受影响的元素下标（即x+find(x)）
End;
End；
2、询问操作：询问k到l区间上的元素的和。我们可以用一个过程算出1到i的元素和，算sum[k-1]和sum[l]的值，再相减即可。
因为a[i]记录的是从i-p+1到i的元素和，所以我们可以通过a的值算出sum(x)的值。过程是：加a[i]不断把i二进制表示的最末一位的1变成零，重加和过程，直到i==0，即得到了sum[i]的值。
Function sum(x:longint)：longint;
Var k:longint;
Begin
k:=0; //初始化答案
while x>0 do
Begin
k:=k+a[x]; //答案加上a[x]
x:=x-find(x); //将下标的最莫以为1变为0
End;
Exit(k); //返回答案
End;
整个程序代码如下：
Program treearray;
Var i,j,k,l,n,m:longint;
a:array[1..100000] of longint;
Function find(x:longint):longint;
Begin
Exit(x xor (x-1) and x);
End;
Procedure ins(x,y:lonignt);
Begin
While x<n do
Begin
a[x]:=a[x]+y;
x:=x+find(x);
End;
End；
Function sum(x:longint)：longint;
Var k:longint;
Begin
k:=0;
while x>0 do
Begin
k:=k+a[x];
x:=x-find(x);
End;
Exit(k);
End;
Begin
Read(n,m);
For i:=1 to m do
Begin
Read(j,k);
Ins(j,k);
End;
Read(m);
For i:=1 to m do
Begin
Read(j,k);
Writeln(sum(k)-sum(j-1));
End;
End.