跪求北大题目poj2464的解答
来源:百度知道 编辑:UC知道 时间:2024/05/09 07:33:15
要pascal语言的,感谢各位懂程序的大哥大姐,急
树状数组是一个查询和修改复杂度都为log(n)级别的区间统计的数据结构,在思想上类似于线段树。
相比线段树,树状数组需要的空间较少,编程复杂度也较低,但适用范围比线段树小。
来观察一下这个图:
令这棵树的结点编号为C1,C2...Cn。令每个结点的值为这棵树的值的总和,那么容易发现:
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
...
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
这里有一个有趣的性质,下午推了一下发现:
设节点编号为x,那么这个节点管辖的区间为2^k(其中k为x二进制末尾0的个数)个元素。因为这个区间最后一个元素必然为Ax,
所以很明显:Cn = A(n – 2^k + 1) + ... + An
算这个2^k有一个快捷的办法,定义一个函数如下即可:
int lowbit(int x)
{
return x&(x^(x–1));
}
利用机器补码的特点,这个函数可以改得更方便
int lowbit(int i)
{
return i&(-i);
}
如果要把a[n]增加m,可以通过调用如下函数实现
void add(int i,int v)
{
while (i<=n)
{
a[i]+=v;
i+=lowbi