随笔 - 87  文章 - 279  trackbacks - 0
<2007年9月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214423
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

那么,何为树形数组呢??
下图中的C数组就是树状数组,a数组是原数组;

可以发现这些规律:
C1=a1
C2=a1+a2
C3=a3
C4=a1+a2+a3+a4
C5=a5
……
C8=a1+a2+a3+a4+a5+a6+a7+a8
……
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))
以6为例
               (6)10=(0110)2
xor    6-1=(5)10=(0101)2
                        (0011)2
and          (6)10=(0110)2
                        (0010)2

所以问题变的很简单,重要写几个函数就可以了;
求2^k的函数代码如下:

int Lowbit(int t)
{
    return t & ( t ^ ( t - 1 ) );
}


求1 -- end和的函数代码如下:

int Sum(int end)
{
    int sum = 0;
    while(end > 0)
    {
        sum += in[end];
        end -= Lowbit(end);
    }
    return sum;
}


对某位进行操作函数如下(以加法为例)

void plus(int pos , int num)
{
    while(pos <= n)
    {
          in[pos] += num;
          pos += Lowbit(pos);
    }
}


有了这三个函数整个树形数组也就基本构建成功啦!!
对于刚才的一题,每次修改与询问都是对C数组做处理.空间复杂度有3N降为N,时间效率也有所提高.编程复杂度更是降了不少.


下面是用树状数组做的 pku star
#include <iostream>
using namespace std;

const int N = 32100;

int c[N];//树状数组

int lowBit(int x) {
    
return x & (x ^ (x - 1));
}


void add(int x, int k) 
    
//a[x] += k
    while (x <= N) {
        c[x] 
+= k;
        x 
+= lowBit(x);
    }

}


void sub(int x, int k) {
    
//a[x] -= k
    while (x <= N) {
        c[x] 
-= k;
        x 
+= lowBit(x);
    }

}


int sum(int x) {
    
//return sum(1..x);
    int ret = 0;
    
while (x > 0{
        ret 
+= c[x];
        x 
-= lowBit(x);
    }

    
return ret;
}


int out[N];
int f[N];

int main() {
    
//pku2352
    int i, j, k, x, y;
    
int n;
    
    scanf(
"%d"&n);

    
for (i=0; i<n; i++{
        scanf(
"%d%d"&x, &y);
        x
++;
        add(x,
1);
        
out[sum(x-1+ f[x]]++;
        f[x]
++;
    }


    
for (i=0; i<n; i++{
        printf(
"%d\n"out[i]);
    }

    
    system(
"pause");
    
return 0;
}

posted on 2007-03-01 22:02 阅读(1573) 评论(3)  编辑 收藏 引用 所属分类: 数据结构与算法

FeedBack:
# re: 树状数组[未登录] 2008-08-17 20:16 David
请问一下, out[sum(x-1) + f[x]]++; 中的sum(x-1)不是求和吗?
这句是怎样实现的啊,没看懂,麻烦lz解释一下  回复  更多评论
  
# re: 树状数组 2010-03-30 09:41 brightstar
可以换成out[sum(x) -1]++;这样就不用f数组了。
  回复  更多评论
  
# re: 树状数组 2010-03-30 09:42 brightstar
可以换成out[sum(x) -1]++;这样可以省掉f数组
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理