树状数组

 

     树状树组-----转载

树状数组是对一个数组改变某个元素和求和比较实用的数据结构。两中操作都是O(logn)。 在解题过程中，我们有时需要维护一个数组的前缀和S[i]=A[1]+A[2]+...+A[i]。

          但是不难发现，如果我们修改了任意一个A[i],S[i]、S[i+1]...S[n]都会发生变化。

          可以说，每次修改A[i]后，调整前缀和S[]在最坏情况下会需要O(n)的时间。

          当n非常大时，程序会运行得非常缓慢。

          因此，这里我们引入“树状数组”，它的修改与求和都是O(logn)的，效率非常高。

【理论】

          为了对树状数组有个形 象的认识，我们先看下面这张图。

         

   

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

          这里，C[i]表示A[i-2^k+1]到A[i]的和，而k则是i在二进制时末尾0的个数，

          或者说是i用2的幂方和表示时的最小指数。

         （ 当然，利用位运算，我们可以直接计算出2^k=i&(i^(i-1)) ）

          同时，我们也不难发现，这个k就是该节点在树中的高度，因而这个树的高度不会超过logn。

          所以,当我们修改A[i]的值时，可以从C[i]往根节点一路上溯，调整这条路上的所有C[]即可，

          这个操作的复杂度在最坏情况下就是树的高度即O(logn)。  

          另外，对于求数列的前n项和，只需找到n以前的所有最大子树，把其根节点的C加起来即可。

          不难发现，这些子树的数目是n在二进制时1的个数，或者说是把n展开成2的幂方和时的项数,

          因此，求和操作的复杂度也是O(logn)。

          接着，我们考察这两种操作下标变化的规律：

          首先看修改操作：

          已知下标i，求其父节点的下标。
          我们可以考虑对树从逻辑上转化：

 

如图，我们将子树向右对称翻折，虚拟出一些空白结点（图中白色），将原树转化成完全二叉树。

         有图可知，对于节点i，其父节点的下标与翻折出的空白节点下标相同。

         因而父节点下标 p=i+2^k  (2^k是i用2的幂方和展开式中的最小幂，即i为根节点子树的规模)

         即  p = i + i&(i^(i-1)) 。

         接着对于求和操作：

         因为每棵子树覆盖的范围都是2的幂，所以我们要求子树i的前一棵树，只需让i减去2的最小幂即可。

         即  p = i - i&(i^(i-1)) 。

        

         至此，我们已经比较详细的分析了树状数组的复杂度和原理。

         在最后，我们将给出一些树状数组的实现代码，希望读者能够仔细体会其中的细节。

求最小幂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);
    }
}

 

*****************************************************************************

下面是转载的：

下面是几道题目的简单分析；

一，两种情况； 1，要向上统计，向下修改；一般是修改一段区间的值，查找的是某个位上的值；

HDU1556 color the ball；

这个题是这类题最基本的；关键是理解这个向上统计，向下修改时怎么操作的和原理；

poj2155 Matrix

这个是楼天成出的题目；是一道很典型的二维数状数组的应用；是hdu1556的二维版本；

记住要向上统计，向下修改；二维情况，最主要的是理解那个数组中的每个点保存的值的意义（一个矩形区域的总和）；最后记住取余；

poj2299 Ultra-QuickSort；（求逆序数）；

这个题可以用归并排序做出，这里就略过不说了。。

求逆序数，也是树状数组的典型应用，求一堆数中前面比他大的数的个数；也需要向上统计，向下修改；

可以与求一串数中前面比他小的数的个数这个题来比较思考。。。

poj3067 Japan

此题要先对x排序，再对y求那个前面比他大的数的个数；（理解下）；

也是基本应用；

**************************************************************************************************************************

二，2，要向上修改，向下统计；一般是修改某个位置上的值，查找的是一段区间的和；

poj2352 stars

这个题是最基本的一维情况，刚才已说过。。

poj1195 Mobile phone

是个二维的情况。改变的是某个位置上的数的大小；就将所有管辖这个点的 点修改；

统计的时候，就是向下统计；

poj2481 Cows

这个题要把y按不降排序，x不升排序，基本是就是poj2352了。。不过注意其中可以有完全重合区间；

poj3321 apple Tree;

这题要用到树状数组；但难度在那个dfs怎么求那个时间戳；求出后，在套入树状数组的那部分东东。就搞定了。。

poj1990 MooFest ;

这题O（n^2）算法必然超时；排序后要存储前面比他小的数的总和，和个数；故树状数组；

poj2309

树状数组的小试牛刀，一下搞定，想明白的话。。

可以用树状数组的地方，一定可以用线段树；反过来则不行；

但是，树状数组编码简单，对于一定区间修改，求值，很高效；

另外，一个讲树状数组灰常好的网址要吐血推荐。。。

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

 

 

================================================================================================

 

 

树状数组，刚开始学习的时候觉得很神奇，特别是求lowbit的时候...写过几题之后，觉得这东西还是挺好用的。需要注意一个超时陷阱：x==0的情况

树状数组在动态求区间之和的问题时候是一个很好的选择。给出几个例题：

（1）：http://acm.pku.edu.cn/JudgeOnline/problem?id=2352 starts

题目大意为在二维坐标上给出一些星星的坐标，求某一个星星左方，下方，左下方的星星个数。求解这题时学习到了 “降维” 的思想，首先把星星按照Y坐标从小到大，X从小到大排序。树状数组以X坐标建立。这样，在每次对一个星星进行统计时，之前出现过的星星，只要X坐标比其小，则必在其左，下，左下方。 这时，只需利用树状数组进行求从1~x的和既可，统计完之后要记得更新树状数组（后面附上代码） （注意坐标为0的情况，这里是一个超时陷阱）

（2）：http://acm.pku.edu.cn/JudgeOnline/problem?id=2155 Matrix

二维树状数组，题目大意为一个二维矩形平面，里面有数字0或1，初始时全为0，给出两种操作，一种是改变一段子区间内的数值，把0改为1或者1改成0。另外一种是查询某一坐标上的数值是0还是1,。

数据范围：坐标N<=1000，操作数T <=50000。

解此题的方法很巧妙，首先我们考虑如果改变区间内数值时，把该区间内的每一个点都改变一次，那么时间一次操作就需要n^2，这样太耗时。想象一下，如果我们在求某一点的操作次数时，把求操作次数转化为求该点到（1,1）这点的和，那么我们在对某区间操作时，我们可设立四个哨兵来标记：

                   

 HDU 1166  

简单的树状数组模板应用，输入和输出必须 scanf 和 printf，否则会 TLE!

代码

 

#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;
int num=0;
int tree[50005],tmp[50005];
inline int lowbit(int t)
{
    return t & (t ^ (t-1));
}

inline void update(int pot,int val)
{
    while(pot <=num)
    {

     tree[pot]+=val;
     //if (pot==1) {cout<<tree[1]<<" "<<val<<endl;}
     pot+=lowbit(pot);

    }



}

inline int query(int pot)
{
    int sum=0;
    while(pot>0)
    {
      sum+=tree[pot];
      pot-= lowbit(pot);
    }

   return sum;
}




int main()
{
     int t,n,a,b;
     char s[10];
     cin>>t;
      for(int k=1;k<=t;k++)
     {
      memset(tree,0,sizeof(tree));
      cout<<"Case "<<k<<":"<<endl;
      scanf("%d",&n);
      num=n;
      for(int i=1;i<=n;i++)
      {
          scanf("%d",&tmp[i]);
          update(i,tmp[i]);
      }
      while(scanf("%s",s))
     {
       //scanf("%s",s);
       if (strcmp(s,"End")==0) break;
       if (strcmp(s,"Add")==0)
       {
           scanf("%d%d",&a,&b);
           update(a,b);

       }
       if (strcmp(s,"Sub")==0)
       {
           scanf("%d%d",&a,&b);
           update(a,-1*b);

       }

       if (strcmp(s,"Query")==0)
       {
           scanf("%d%d",&a,&b);

           int ans=query(b)-query(a-1);
           printf("%d\n",ans);
       }


     }
    //for(int i=1;i<=4;i++)
    //cout<<tree[i]<<endl;
    //cout<<query(4)<<endl;

}
    //cout << "Hello world!" << endl;
    return 0;
}

 

 

HDU  1541  

#include <iostream>

#include <stdio.h>

#include <cstring>

using namespace std;

const int maxn=35000;

int tree[maxn];

int level[maxn];

int num=0;

int lowbit(int t)

{

    return t & (-t);

}

 

 

void update(int pos,int val)

{

    while(pos<=num)

    {

        tree[pos]+=val;

        pos+=lowbit(pos);

 

    }

}

 

int query(int pos)

{

    int sum=0;

    while(pos>0)

    {

        sum+=tree[pos];

        pos-=lowbit(pos);

     }

    return sum;

    }

 

int main()

{

    int n,x,y;

    while(cin>>n)

    {

        memset(tree,0,sizeof(tree));

        memset(level,0,sizeof(level));

        num=maxn;

        for(int i=1;i<=n;i++)

        {

            scanf("%d%d",&x,&y);

            x++;//防止x=0，因为x=0,lowbit(0)会造成死循环！

            int tmp=query(x);//看它前面有几个星星.

            level[tmp]++;//输入的这个星星的层数+1

            update(x,1);

 

        }

        for(int i=0;i<n;i++)

         printf("%d\n",level[i]);

 

 

 

    }

 

 

 

    //cout << "Hello world!" << endl;

    return 0;

}