当前位置:天才代写 > tutorial > 大数据教程 > 数据结构之树状数组

数据结构之树状数组

2021-03-02 15:22 星期二 所属: 大数据教程 浏览:38

1、简述

树状数组(binary indexed tree),是一种设计方案新奇的二维数组构造,它可以高效率地获得二维数组中持续n数量的和。归纳说,树状数组一般 用以处理下列难题:二维数组{a}中的原素很有可能持续的被改动,怎么才能迅速地获得持续好多个数的和?

2、树状数组操作过程

传统式二维数组(共n个原素)的原素改动和持续原素求饶的复杂性各自为O(1)和O(n)。树状数组根据将线性结构转化成伪树形结构构造(线性结构只有逐一扫描仪原素,而树形结构构造能够完成跳跃性扫描仪),促使改动和求饶复杂性均为O(lgn),进一步提高了总体高效率。

给出编码序列(数列)A,大家设一个二维数组C考虑

C[i] = A[i–2^k 1] … A[i]

在其中,k为i在二进制下结尾0的数量,i从1逐渐算!

则大家称C为树状数组。

下边的难题是,给出i,怎样求2^k?

回答非常简单:2^k=i&(i^(i-1)) ,也就是i&(-i)

下边开展表述:

以i=6为例子(留意:a_x表明数据a是x进制表明方式):
(i)_10 = (0110)_2
(i-1)_10=(0101)_2
i xor (i-1) =(0011)_2
i and (i xor (i-1))  =(0010)_2

2^k = 2
C[6] = C[6-2 1] … A[6]=A[5] A[6]

二维数组C的实际含意如下图所显示:

在我们改动A[i]的值时,能够从C[i]往根节点一路追溯到,调节这条道路上的全部C[]就可以,这一实际操作的复杂性在最坏状况下便是树的高宽比即O(logn)。此外,针对求数列的前n项和,只需寻找n之前的全部较大 子树,把其根节点的C加起來就可以。不会太难发觉,这种子树的数量是n在二进制时1的数量,换句话说是把n进行成2的幂方和时的项数,因而,求饶实际操作的复杂性也是O(logn)。

树状数组能迅速求随意区段的和:A[i] A[i 1] … A[j],设sum(k) = A[1] A[2] … A[k],则A[i] A[i 1] … A[j] = sum(j)-sum(i-1)。

下边得出树状数组的C语言完成:

//求2^k
int lowbit(int t)
{
    return t & ( t ^ ( t - 1 ) );
}
//求前n项和
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);
  }
}

3、拓展——二维树状数组

一维树状数组非常容易拓展到二维,二维树状数组以下所显示:

C[x][y] = sum(A[i][j])

在其中,x-lowbit[x] 1 <= i<=x且y-lowbit[y] 1 <= j <=y

4、运用

(1)    一维树状数组:

参照:http://hi.baidu.com/lilu03555/blog/item/4118f04429739580b3b7dc74.html

(2)    二维树状数组:

一个由数据组成的大引流矩阵,能开展二种实际操作

1) 对引流矩阵里的某一数再加上一个整数金额(可正可负)

2) 查看某一子引流矩阵里全部数据的和

规定对每一次查看,輸出結果

5、小结

树状数组最开始是在设计方案压缩算法时发觉的(见参考文献1),如今也会常常术语维护保养子序列和。它与线段树(实际见:算法设计之线段树)较为在思想方面相近,比线段树节约室内空间且程序编写复杂性低,但应用范畴比线段树小(如查看每一个区段极小值难题)。

6、参考文献

(1)    Binary Indexed Trees:

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

(2)    吴豪文章内容《树状数组》:

http://www.java3z.com/cwbwebhome/article/article19/zip/treearray.zip

(3)    郭炜文章内容《线段树和树状数组》:

http://poj.org/summerschool/1_interval_tree.pdf

 

    关键字:

天才代写-代写联系方式