`
128kj
  • 浏览: 580740 次
  • 来自: ...
社区版块
存档分类
最新评论

初步了解树状数组

阅读更多
一、树状数组是干什么的?
     平常我们会遇到一些对数组进行维护查询的操作,比较常见的如,修改某点的值、
求某个区间的和,而这两种恰恰是树状数组的强项!当然,数据规模不大的时候,对于修改某点的值是非常容易的,复杂度是O(1),但是对于求一个区间的和就要扫一遍了,复杂度是O(N),如果实时的对数组进行M次修改或求和,最坏的情况下复杂度是O(M*N),当规模增大后这是划不来的!而树状数组干同样的事复杂度却是O(M*lgN),别小看这个lg,很大的数一lg就很小了。

二、树状数组的定义


如图所示,红色矩形表示的数组C[]就是树状数组。

给定序列(数列)A,我们设一个数组C满足
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
......
定义:
   C[t] = A[t – 2^k + 1] + … + A[t],k为t在二进制下末尾0的个数。(t>=1)

分析上面的几组式子可知,当 t 为奇数时,Ct=Ai ;当 t为偶数时,就要看 t的因子中最多有二的多少次幂,例如,6 的因子中有 2 的一次幂,等于 2 ,所以 C6=A5+A6(由六向前数两个数的和),4 的因子中有 2 的两次幂,等于 4 ,所以 C4=A1+A2+A3+A4(由四向前数四个数的和)。

三、基本操作
(1)C[t]展开以后有多少项?由下面公式计算:

int lowbit(int t){//计算c[t]展开的项数
   return t&(-t);
  }

例:
lowbit(1)=1   C1 = A1
lowbit(2)=2   C2 = A1 + A2
lowbit(3)=1   C3 = A3
lowbit(4)=4   C4 = A1 + A2 + A3 + A4
lowbit(5)=1   C5 = A5
lowbit(6)=2   C6 = A5 + A6
lowbit(7)=1   C7 = A7
lowbit(8)=8   C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
.......
c[t]展开的项数就是lowbit(t),c[t]就是从a[t]开始往左连续求lowbit(t)个数的和,


 lowbit(1)=1       lowbit(2)=2       lowbit(3)=1      lowbit(4)=4
 lowbit(5)=1       lowbit(6)=2       lowbit(7)=1      lowbit(8)=8
 lowbit(9)=1      lowbit(10)=2      lowbit(11)=1      lowbit(12)=4
lowbit(13)=1      lowbit(14)=2      lowbit(15)=1      lowbit(16)=16
lowbit(17)=1      lowbit(18)=2      lowbit(19)=1      lowbit(20)=4
lowbit(21)=1      lowbit(22)=2      lowbit(23)=1      lowbit(24)=8
lowbit(25)=1      lowbit(26)=2      lowbit(27)=1      lowbit(28)=4
lowbit(29)=1      lowbit(30)=2      lowbit(31)=1      lowbit(32)=32
lowbit(33)=1      lowbit(34)=2      lowbit(35)=1      lowbit(36)=4
lowbit(37)=1      lowbit(38)=2      lowbit(39)=1      lowbit(40)=8
lowbit(41)=1      lowbit(42)=2      lowbit(43)=1      lowbit(44)=4
lowbit(45)=1      lowbit(46)=2      lowbit(47)=1      lowbit(48)=16
lowbit(49)=1      lowbit(50)=2      lowbit(51)=1      lowbit(52)=4
lowbit(53)=1      lowbit(54)=2      lowbit(55)=1      lowbit(56)=8
lowbit(57)=1      lowbit(58)=2      lowbit(59)=1      lowbit(60)=4
lowbit(61)=1      lowbit(62)=2      lowbit(63)=1      lowbit(64)=64


(2)修改
    当我们修改A[i]的值时,可以从C[i]往根节点一路上溯,调整这条路上的所有C[]即可,对于节点i,父节点下标 p=i+lowbit(i) 

代码实现:
//增加某个元素的大小,给某个节点 i 加上 x 
 update(int i,int x){ 
 while(i<=n){ 
    c[i]=c[i]+x; 
    i=i+lowbit(i); 
     } 
} 


(3)求数列的前n项和,只需找到n以前的所有最大子树,把其根节点的C加起来即可。


int Sum(int n) //求前n项的和.
{ 
    int sum=0; 
    while(n>0) 
    { 
         sum+=c[n]; 
         n=n-lowbit(n); 
    }     
    return sum; 
} 

例:
 public class TreeArray{
       int n;//数组元素个数
       int[] a;//原数组
       int[] c;//对应的树状数组

  public TreeArray(int[] a){
       n=a.length;
       this.a=a;
       c=new int[a.length];
       for(int i=1;i<a.length;i++){
           for(int j=0;j<lowbit(i);j++)
             c[i]=c[i]+a[i-j];
       }
  }


  private int lowbit(int t){//计算c[t]展开的项数
   return t&(-t);
  }
   
  private void update(int i,int x){ 
      while(i<=n){ 
        c[i]=c[i]+x; 
        i=i+lowbit(i); 
     } 
    } 

  private int Sum(int k){ //求前k项的和.
   int sum=0; 
    while(k>0){ 
       sum+=c[k]; 
       k=k-lowbit(k); 
    }     
    return sum; 
  } 

    public static void main(String args[]){
       int a[]={0,1,2,3,4,5,6,7,8,9,10};
       TreeArray ta=new TreeArray(a);
       System.out.println(ta.Sum(10));
        ta.update(5,-20);
       System.out.println(ta.Sum(10));
       System.out.println(ta.Sum(4));

    }
 }
    
运行:
C:\java>java   TreeArray
55
35
10   


  • 大小: 35.9 KB
0
2
分享到:
评论

相关推荐

    树状数组树状数组资料下载

    树状数组 树状数组 树状数组 树状数组树状数组 树状数组 树状数组 树状数组树状数组 树状数组 树状数组 树状数组

    树状数组 树状数组.ppt

    树状数组 树状数组.ppt

    树状数组_洛谷_树状数组_

    洛谷上关于树状数组的一些简单例题,可参考学习,适合初学者

    java实现的 树状数组

    用java实现的树状数组,可以作为一个简单的模版来进行应用,如果有不懂得地方,可以上网查找树状数组的原理

    树状数组2.cpp 使用C++实现

    树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现树状数组2.cpp 使用C++实现...

    acm 树状数组讲解

    图文并茂的描述了树状数组的使用~~让大家详细了解梳妆数组的使用

    树状数组3.java 使用java实现

    树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3.java 使用java实现树状数组3....

    树状数组1.c 使用C语言实现的

    树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c 使用C语言实现的树状数组1.c...

    树状数组详解

    树状数组详解

    算法NOIP树状数组校门外的树.pdf

    本文详细介绍了树状数组的原理,并用树状数组解校门外的树这个问题.

    树状数组题目集

    其实学树状数组说白了就是看那张图,那张树状数组和一般数组的关系的,看懂了基本就没问题了,推荐下面这个教程:http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

    树状数组 后缀数组 字典树 多串匹配算法及启示

    树状数组 后缀数组 字典树 多串匹配算法及启示

    搞懂树状数组

    你知道树状数组吗,这是本人自己打的课件,希望你能喜欢,有区间求值单点修改,单点修改区间查询,区间修改区间查询,二维树状数组......

    bit.cpp(树状数组基本框架)

    含义其实就是用一个数组,构成树形结构来维护原数组的前缀和。 显然,对于树状数组C,C[I]对应“管辖”多少个元素,与它对应二进制数最右端第一个1的位置有关。这样,就能够达到询问一个区间的值,或者改变值的时间...

    数据结构(树状数组)

    数据结构基础之树状数组,有关其实现代码,及树状数组的建立和点的更新。

    树状数组算法的描述和代码的实现

    里面包含了树状数组算法的描述和代码实现 里面包含了树状数组算法的描述和代码实现 里面包含了树状数组算法的描述和代码实现

    树状数组的题目解法c++代码

    通过了解树状数组的原理和定义来解决有关给定一个由n个不同的整数组成的序列,最少需要交换多少次交换相邻的两个数,使其升序排列。

    二维树状数组

    它是ACM中关于二维树状数组方面的资料。。

    卡树状数组的数据

    树状数组要开long double(运算过程会爆long long)

    细讲树状数组

    该PPT详细的写了树状数组的(二叉索引树)区间和查询以及应用

Global site tag (gtag.js) - Google Analytics