注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

树状数组小结  

2014-04-27 22:42:40|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
以前树状数组的题目都用线段树的,现在发现稍微难的题目线段树代码要写老长,还不方便调,于是今天就学了树状数组,顺便切了几题。
树状数组的题一定可以用线段树实现,因为树状数组是用来维护前缀和,线段树写前缀和轻而易举的。而有些线段树的题树状数组却写不了。
首先,个人认为树状数组其实是“任意一个数都可以用二进制表示”,比如5可以由2^2+2^1,8就是2^3,等等。这样可以用来维护前缀和。
但是我们得明确一下:前缀和可以在o(1)的时间查询(即得到答案),但树状数组查询的效率是o(logN)的。然而,前缀和如果要修改某一个值,则比它大的前缀和也必须是修改,时间效率是o(N)的。此时,树状数组却任然是o(logN)。最重要的是:树状数组不是一种算法,而是你想到了某种算法却TLE,用它来维护。且这个算法必须得利用到前缀和。树状数组的题目关键在于问题的转化,如一个公式本无法用前缀和维护,但化成3个式子分别开3个树状数组边OK了。
树状数组的实现是这样的:1.先看图树状数组小结 - 山哥 - OI之路,漫漫人生
有没有发现,2、4、8控制的都是整个1到它的范围,而如5、6却只控制了一部分范围。将数字转换成之前说的二进制,你发现了什么??   对,如5其实能够控制2^2+2^1个,即5能控制C4和C5,即A1+A2+A3+A4+A5=1到5个前缀和。6则控制了C6和C4,即控制了A1+...A7,每个数字其实表示了1到它本身的前缀和,而它是间接的控制的,下面就来介绍一下树状数组的1个函数:
lowbit()。去掉二进制下末尾的最后一个0,正如刚刚说的,5目前只控制了5,但其实他要控制1到5,而5减去lowbit()边弹道了4,间接的统计已经实现了。

对于修改某个值,我们同时必须修改大于它的前缀和是吧(位置小于它的当然影响不到)。那么我们可以加lowbit(i)弹到下一个地方,如4弹到了5,5又到了6,直到超过N。代码如下:
for (j=i;j<=n;j+=j&(-j));
统计某个值就-lowbit(i);
for (j=i;j;j-=j&(-j));                           以上是树状数组的基本操作,现在开始讲我刷的例题。

1.pojpoj2299 Ultra-QuickSort (求逆序数)

http://poj.org/problem?id=2299

由于数字很大先离散,然后

O(N)扫过去的同时先-lowbit统计比他小存在于树状数组中的数字。(因为是逆序,反着来N-1扫,见代码)

然后再将这个数字插入到树状数组+lowbit更新前缀和。

#include<cstdio>

#include<algorithm>

#include<cstring>

#define nn 500005

using namespace std;

typedef long long ll;

struct node{ll s,id;}a[nn];

ll n,i,j,ans,b[nn],tree[nn];

bool cmp(const node&a,const node&b){return a.s<b.s;}

int main()

{

 scanf("%I64d",&n);

 while (n!=0){

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

     for (i=1;i<=n;i++){scanf("%I64d",&a[i].s);a[i].id=i;}

     sort(a+1,a+n+1,cmp);

     for (i=1;i<=n;i++)b[a[i].id]=i;

     ans=0;

     for (i=n;i>=1;i--){

        for (j=b[i]-1;j;j-=j&(-j))ans+=tree[j];

        for (j=b[i];j<=n;j+=j&(-j))tree[j]++;

                        }

     printf("%I64d\n",ans);

     scanf("%I64d",&n);

             }

return 0;

}




2.poj2352 stars

http://poj.org/problem?id=2352

给你一堆星星的坐标,每一个星星左下角有i个星星,求有i个的星星这样的星星的个数。

先对y坐标进行升序排序,然后对x坐标O(N)扫过去同1,统计x坐标比他小的个数即可。

#include<cstdio>

#include<algorithm>

#define nn 15100

#define mm 32010

using namespace std;

struct node{int x,y;}a[nn];

int n,i,tem,r,tree[mm],j,f[nn];

int max(int a,int b){return (a>b)?a:b;}

bool cmp(const node&a,const node&b)

 {if (a.y!=b.y)return a.y<b.y;

  return a.x<b.x;

 }

int main()

{

 scanf("%d",&n);r=1;

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

{scanf("%d%d",&a[i].x,&a[i].y);a[i].x++;r=max(r,a[i].x);}

 sort(a+1,a+n+1,cmp);

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

         {tem=0;

      for (j=a[i].x;j;j-=j&(-j))tem+=tree[j];

      for (j=a[i].x;j<=r;j+=j&(-j))tree[j]++;

          f[tem]++;

         }

 for (i=0;i<=n-1;i++)printf("%d\n",f[i]);

 return 0;

}




3.POJ3067 Japanstars

http://poj.org/problem?id=3067

对某一坐标排序后,另一标同上搞,只不过是统计比它的了,那么前缀和变成后缀和,统计变+,修改变成了-;其他一模一样
#include<cstdio>
#include<algorithm>
#define nn 2001
using namespace std;
typedef long long ll;
struct node{ll x,y;}a[nn*nn];
ll t,k,q,p,n,tem,i,j,tree[nn];
bool cmp(const node&a,const node&b)
 {if (a.x!=b.x)return a.x>b.x;
  return a.y>b.y;
 }
int main()
{
 scanf("%I64d",&t);
 for (k=1;k<=t;k++)
      {
 memset(tree,0,sizeof(tree));
 scanf("%I64d%I64d%I64d",&q,&p,&n);
 for (i=1;i<=n;i++)scanf("%I64d%I64d",&a[i].x,&a[i].y);
 sort(a+1,a+n+1,cmp);tem=0;
 for (i=1;i<=n;i++)
          {
          for (j=a[i].y-1;j;j-=j&(-j))tem+=tree[j];
          for (j=a[i].y;j<=p;j+=j&(-j))tree[j]++;
          }
      printf("Test case %I64d: %I64d\n",k,tem);
      }
return 0;
}




4.poj2481 Cows

http://poj.org/problem?id=2481

按照l升序,r降序,那么就是统计比它大的个数(后缀和),同上。但要注意区间完全一样的是不算的,这样的解决方法是直接去上一个值即可。

#include<cstdio>

#include<algorithm>

#include<cstring>

#define nn 100005

#define mm 100010

using namespace std;

struct node{int x,y,id;}a[nn];

int n,r,i,tree[mm],f[nn],j;

bool cmp(const node&a,const node&b)

     {if (a.x!=b.x)return a.x<b.x;

      return a.y>b.y;

     }

int max(int a,int b){return (a>b)?a:b;}

int main()

{

 scanf("%d",&n);

 while (n!=0){

       r=0;memset(f,0,sizeof(f));memset(tree,0,sizeof(tree));

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

   {scanf("%d%d",&a[i].x,&a[i].y);a[i].y++;r=max(r,a[i].y);a[i].id=i;}

   sort(a+1,a+n+1,cmp);a[0].x=a[0].y=-1;

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

   if (a[i].x==a[i-1].x&&a[i].y==a[i-1].y)f[a[i].id]=f[a[i-1].id];

   else for (j=a[i].y;j<=r;j+=j&(-j))f[a[i].id]+=tree[j];

   for (j=a[i].y;j;j-=j&(-j))tree[j]++;                        

                      }

   printf("%d",f[1]);

   for (i=2;i<=n;i++)printf(" %d",f[i]);printf("\n");

   scanf("%d",&n);

              }

return 0;

}




5.poj3321 apple Tree;

http://poj.org/problem?id=3321

此题难度较大,我想了半天终于发现了其中的奥妙,(*^__^*) 嘻嘻……。首先要用dfs序,即dfs第一次到某个点和结束的次数用st[i]和ed[i]记录,如样例便是122331,那么我们可以发现:1.两个相同的数字中间一定是其儿子结点。2.对于没个结点,在他前面的父亲结点的特征是:将它包含。有了这么两个性质,套用树状数组即可了。比如我们要修改某个苹果,有无判断好后,那么只需修改它前面的结点:一开始我以为前面的结点万一是兄弟结点不是多多了,后来才发现我傻B了。树状数组是什么?是前缀和啊,运用刚才的2性质,若统计兄弟节点,在求那个区间是不可能将它包含,即不可能多加。然后我们要统计以某个结点i为子树的苹果个数,那么不就是st[I]到ed[I]之间的区间和,由于为了方便我写后缀和,就是先统计ed[I]+1到N的,再统计st[I]到N的,两个相减就是所求的。    1A超爽好开心(*^__^*) 嘻嘻……

#include<cstdio>

#define nn 100009

using namespace std;

struct node{int end,next;}g[nn];

int tot,n,i,x,y,re,ans1,ans2,j,m;

int a[nn],fa[nn],tree[nn*2],st[nn],ed[nn];

char flag;

void add(int a,int b)

{g[++tot].end=b;g[tot].next=fa[a];

fa[a]=tot;

}

void dfsx(int w)

 {int i;

  st[w]=++re;

 for (i=fa[w];i;i=g[i].next){

              int u=g[i].end;

              dfsx(u);

                             }

 ed[w]=++re;

 }

int main()

{

 scanf("%d",&n);

 for (i=1;i<=n-1;i++){

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

      add(x,y);

                          }

for (i=1;i<=n;i++)a[i]=1;

dfsx(1);

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

    for (j=st[i];j;j-=j&(-j))tree[j]++;

scanf("%d",&m);n*=2;

for (i=1;i<=m;i++){

               getchar();

               scanf("%c%d",&flag,&x);

                      if (flag=='Q'){ans1=ans2=0;

               for (j=ed[x]+1;j<=n;j+=j&(-j))ans1+=tree[j];

               for (j=st[x];j<=n;j+=j&(-j))ans2+=tree[j];

                                  printf("%d\n",ans2-ans1);       

                                     }

                           else{

                           if (a[x]){ 

                           for (j=st[x];j;j-=j&(-j))tree[j]--;

                           a[x]=0;

                                     }

                           else   {

                           for (j=st[x];j;j-=j&(-j))tree[j]++;

                           a[x]=1;

                                  }

                               }

                   }

return 0;

}




6.叶队树(叶队是个人)学哥出的模拟赛的最后一题,当时我就差这道没做出。伤心~~~~(>_<)~~~~ 
也是运用树状数组,可是这题比之前的可要难多了,没那么裸了。
题目描述:
Description
这题只是用来 Orz 叶队——中国高端数据结构专家和领导者
主席有主席树,BG 有 BG 树,叶队自然有叶队树
叶队树可以维护以下操作:
1 v x k:设 u是以 v 号点为根的子树中的一个点(u可以等于 v)
若 u 与 v 的深度差为 d,则给 u号点加上(x+k*d)*(-1)
d
2 v:询问 v 号点的权值 mod (109
+7)之后的值
(叶队规定 1 号节点为根)
因为叶队想虐你复杂度,所以请你实现这些操作
Input
第一行包含两个正整数 N 和 M。N 为树上的点数,M 操作的数量。
第 2~N 行,每行一个正整数,第 i 行的正整数是 i 号节点的父亲
再接下来 M 行,格式为“1 v x k”或“2 v” ,含义如题
Output
对于每个 2 操作输出一行,为 v 号点的权值 mod (109
+7)之后的值By Stilwell
Sample Input
5 8
1
1
3
3
1 1 0 2
2 1
2 2
2 4
1 3 1 3
2 3
2 4
2 1
Sample Output
0
1000000005
4
1000000006
0
0By Stilwell
HINT
负数取模要化为正数 //详见样例
数据保证树高不超过 30000 //就不来卡栈了
N的范围是10^5,k,x绝对值<=1000;
题解:公式的推导啊,SYC当场秒出的大神给我写了推导过程。一开始我想,dfs序弄出来,由于每次修改的深度不同,累加的东西怎么合并呢,若是线段树,就是down操作和上传写不出来。于是我们尝试转换一下公式:
对于每个修改x,k,u 我们要加的是不是[x+k*(dv-du)]*(-1)^(dv-du),di表示这个节点的深度,u是修改的结点,v是它子树中的某个结点。
[x+k*(dv-du)]*(-1)^(dv-du)
=[x+k*(dv-du)]/(-1)du*(-1)^dv
=(x/(-1)^du+k*dv/(-1)^du-k*du/(-1)^du)*(-1)dv;
到了这步,类似上面几题,我们试试前缀和的转换,首先如果我们要查询v这个点,是不是只于那些U是它祖先的修改有关,而对于刚才的公式,如果我们去掉dv,就变成了
(x/(-1)^du+k/(-1)^du-k*du/(-1)^du),也就是说对于点V,只于它祖先的修改u有关,此时我们分别对每一项开一个树状数组总共3个,记为R1,R2,R3,每次修改就修改st[u]到ed[u]之间的(即u的孩子),每次统计答案,就是
(R1+R2*dv-R3)*(-1)^dv。运用dfsx的性质1和2,做这种题真是爽,太感谢SYC大牛了。

未完待续。。。
  评论这张
 
阅读(2389)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018