用户登录:

用户名:
密码:      

文章分类:


最新评论:

userleijiankun 说:膜拜神牛。……
usercss 说:康拓展开和逆康拓展……
usersongrenchu 说:欢迎大家踊……
userAdmin 说:……

树状数组的实现过程

发表时间:2010-05-04 20:25:05  浏览(784) 评论(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.

网友评论:

Guest 发表评论