• 2008-08-20

    [Code]树状数组的一点认识 - [Code]

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/sgzxy-logs/27912113.html

          话说开始学线段树,先从树状数组入手看,又正巧看到POJ3468这题。第一感觉以为这题就是为数状数组设计的,于是拼命用树状数组想,优化再优化,仍然TLE。

         最后此题用静态线段树过了,用时2秒多。虽然前面的思考失败,但仍有些关于树状数组的心得,在此记下:

         一个很好的树状数组介绍和分析,受益匪浅:http://blog.edu.cn/user3/Newpoo/archives/2007/1712628.shtml

         1.首先是树状数组目前认识到的能力范围。在标准实现中,树状数组可以做到区间求和O(logn)和单个点修改O(logn);在一种特殊的实现中(参考上面链接,可以做到区间各点统一修改O(logn)和点查询O(logn),然而此时标准实现中O(logn)的操作无法实现。由此的确看到,树状数组的功能局限还是挺大的,因为一般题目要求的所有操作性能都要达到O(logn)。

         2.树状数组的建立,若按照初步思维,当读入一串原始数组时,对每一个数进行“点修改”的操作,则效率为O(nlogn)。同理,在标准实现中,当要进行区间各点(设区间中有k个点)的统一修改时,也是进行一个个“点修改”,效率为O(klogn)

         然而事实上,通过建立一个辅助数组(增加一倍空间),可以使上面两个操作均为O(n)(n是点数)。这一技巧在于:处理每一个原始数据的点时,仅完成这一点对应树状数组中那一点的修改,并把这个修改传递给它的父亲,辅助数组就是为了记录这种传递的修改,而当修改到那个父亲点时,则把前面所传递的修改都考虑进去,在修改自身的同时也将修改值传递到更高一层。

         也即每次修改无需向上直达树根,而是变成一个O(1)的操作,直到最后一次修改完后,才把前面累积的修改一路传递到树根(建立树状数组时没有这一步,因为树根也需要建立)。

          示意代码如下:

    建立树状数组的过程(tmp为辅助数组,记录i点之前修改的累积):

     for ( int i = 1; i<=N; ++i )
     {
      scanf("%d", &data );
      int inc = data+ tmp[ i ];
      tree[ i ] += inc;
      int p = i + GetLowbit( i );
      if ( p <= N )
       tmp[ p ] += inc;
     }

    区间统一修改各点:

    void IncreaseInterval( int start, int end, int c )
    {
     for ( int i = start; i<=end; ++i )
     {
      int inc = c + tmp[ i ];
      tree[ i ] += inc;
      int p = i + GetLowbit( i );
      if ( p <= N )
       tmp[ p ] += inc;
     }
     int p = end + GetLowbit( end );
     if ( p<=N )
      ChangePoint( p, tmp[ p ] );    //执行一个“点修改”操作,将区间改变的影响一路传递到树根
     memset(tmp, 0, (p+1)*sizeof(int) );
    }

          虽然O(n)的效率在一般题目要求的情况下也是无法达到要求的,不过这两点发现还是有助于我对树状数组性能的更好认识。

    分享到:

    历史上的今天: