Chinaunix首页 | 论坛 | 博客
  • 博客访问: 472092
  • 博文数量: 117
  • 博客积分: 3195
  • 博客等级: 中校
  • 技术积分: 1156
  • 用 户 组: 普通用户
  • 注册时间: 2009-08-04 01:44
文章分类

全部博文(117)

文章存档

2012年(5)

2011年(5)

2010年(46)

2009年(61)

我的朋友

分类:

2009-09-23 16:49:17

树状数组是一个查询和修改复杂度都为log(n)的数据结构,假设数组a[1...n],那么查询a[1] + …… + a[i] 的时间是log级别的,而且是一个在线的数据结构,支持随时修改某个元素的值,复杂度也为log级别。
来观察一下这个图:

 
令这棵树的结点编号为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
……
C2^n=a1+a2+….+a2^n
对于序列a,我们设一个数组C定义C[t] = a[t – 2^k + 1] + … + a[t],k为t在二进制下末尾0的个数。
K的计算可以这样:
2^k=t and (t xor (t-1)) 或者 t and (- t)
以6为例
               (6)10=(0110)2
xor            6-1=(5)10=(0101)2 
               (0011)2
and            (6)10=(0110)2 
                  (0010)2

这里有一个有趣的性质:
设节点编号为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));
//  return x & (-x);
}
当想要查询一个SUM(n)时,可以依据如下算法即可:
step1: 令sum = 0,转第二步;
step2: 假如n <= 0,算法结束,返回sum值,否则sum = sum + Cn,转第三步;
step3: 令n = n – lowbit(n),转第二步。
 
分析: 设原数组为a[1..N],树状数组为c[1..N],其中c[k] = a[k-(2^t)+1] + ... + a[k]。比如c[6] = c[5] + c[6]。也就是说,把k表示成二进制1***10000,那么c[k]就是1***00001 + 1***00010 + ... + 1***10000这一段数的和。设一个函数lowestbit(k)为取得k的最低非零位,容易发现,根据上面的表示方法,从a[1]到a[k]的所有数的总和即为sum[k] = c[k] + c[k-lowestbit(k)] + c[k-lowestbit(k)-lowestbit(k-lowestbit(k))] + ... 于是可以在logk的时间内求出sum[k]。当数组中某元素发生变化时,需要改动的c值是c[k],c[k+lowestbit(k)], c[k+lowestbit(k)+lowestbit(k+lowestbit(k))] ... 。
这个算法就是将这一个个区间的和全部加起来,为什么是效率是log(n)的呢?以下给出证明:
n = n – lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。而n的二进制里最多有log(n)个1,所以查询效率是log(n)的。
 
那么修改呢,修改一个节点,必须修改其所有祖先,最坏情况下为修改第一个元素,最多有log(n)的祖先。所以修改算法如下(给某个结点i加上x):
step1: 当i > n时,算法结束,否则转第二步;
step2: Ci = Ci + x, i = i + lowbit(i)转第一步。
i = i +lowbit(i)这个过程实际上也只是一个把末尾1补为0的过程。
 
//修改过程必须满足减法规则!
以上来自  http://blog.csdn.net/oopos/archive/2007/10/14/1824583.aspx
 
 
数列操作
  给定一个初始值都为0的序列,动态地修改一些位置上的数字,加上一个数,减去一个数,或者乘上一个数,然后动态地提出问题,问题的形式是求出一段数字的和.
  【算法分析】
  如果直接做的话,修改的复杂度是O(1),询问的复杂度是O(N),M次询问的复杂度是M*N.M,N的范围可以有100000以上,所以这样做会超时,但是如果用线段树的话,还是很不错的!
 
   C数组就是树状数组,a数组是原数组;
  对于序列a,我们设一个数组C定义C[t] = a[t – 2^k + 1] + … + a[t],k为t在二进制下末尾0的个数。
代码如下:

#include <stdio.h>
#include <string.h>
#include <conio.h>
int C[10];
int n = 10;

/*求2^k*/
int lowbit(int t)
{
  return t & (-t);
}

/*求1--end的和*/
int sum(int end)
{
    int sum = 0;
    while(end > 0)
    {
        sum += C[end];
        end

阅读(956) | 评论(2) | 转发(0) |
给主人留下些什么吧!~~

chinaunix网友2009-12-10 12:06:29

貌似没有copy完整. 是参加了比赛,我也没奖,悲剧啊。。。

chinaunix网友2009-11-29 12:13:43

是不是没有写完啊?你也参加了湖南省程序设计大赛啊?我参加了,不过没拿奖啊!!可惜啊!!