[关闭]
@xzyxzy 2018-04-01T09:14:57.000000Z 字数 3575 阅读 565

树链剖分

数据结构


一、概念

把树剖成链再操作
博客安利:http://www.cnblogs.com/chinhhh/p/7965433.html

二、实现

方法

维护7个不同数组,通常和线段树一起使用

复杂度

首先两次DFS为
然后每个询问,查询子树是,线段树查询路径权值和等一般要求LCA,为
线段树贡献了一个
综上为
但实际上自带小常数,远不及log方

三、适用范围

维护树上两点之间的路径(带修改)
维护树上一棵子树的权值(带修改)

四、题目

1、模板题

2、应用题

四、做题经验

1、线段树加法进行下放懒标记和打标记时要乘区间长度

  1. if(l>=gl&&r<=gr)
  2. {
  3. t[now]=(t[now]+(r-l+1)*z)%P;
  4. lazy[now]=(lazy[now]+z)%P;
  5. return;
  6. }
  1. t[now<<1]=(t[now<<1]+lazy[now]*(mid-l+1))%P;
  2. t[now<<1|1]=(t[now<<1|1]+lazy[now]*(r-mid))%P;

这是P3384 模板,当时还请zsy帮忙调了

2、把边权下放到点权的时候注意临界情况

  1. if(Query(1,1,n,dfn[y]+1,dfn[x]))printf("No\n");

这是P3950 部落冲突,把边下放到点的时候,对于LCA特殊处理,比如说点A和B的LCA是K,K上方发生战争于是标记在K,但A和B还是联通的,所以查询时要忽略K,即+1。

3、注意lazy是非零即放,那么不要打叹号

查错时可以考虑一下

4、注意这一段

  1. if(deep[top[x]]<deep[top[y]])swap(x,y);

不是这个

  1. if(deep[x]<deep[y])swap(x,y);

附录

  1. //P3384 模板
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #define ll long long
  7. using namespace std;
  8. ll read()
  9. {
  10. char ch=getchar();
  11. ll h=0,t=1;
  12. while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
  13. if(ch=='-'){ch=getchar();t=-1;}
  14. while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
  15. return h*t;
  16. }
  17. const ll MAXN=500001;
  18. ll head[MAXN],cnt=0;
  19. struct edge{ll next,to;}a[MAXN<<1];
  20. void link(ll x,ll y){a[++cnt]=(edge){head[x],y};head[x]=cnt;}
  21. ll N,M,Root,P;
  22. ll top[MAXN],fa[MAXN],deep[MAXN],son[MAXN];
  23. ll dfn[MAXN],size[MAXN],id[MAXN],tot;
  24. void DFS1(ll x)
  25. {
  26. deep[x]=deep[fa[x]]+1;size[x]=1;
  27. for(ll i=head[x];i!=-1;i=a[i].next)
  28. {
  29. ll R=a[i].to;
  30. if(R==fa[x])continue;
  31. fa[R]=x;DFS1(R);
  32. size[x]+=size[R];
  33. if(size[R]>size[son[x]])son[x]=R;
  34. }
  35. }
  36. void DFS2(ll x)
  37. {
  38. dfn[x]=++tot;id[tot]=x;
  39. if(son[fa[x]]==x)top[x]=top[fa[x]];
  40. else top[x]=x;
  41. if(son[x])DFS2(son[x]);
  42. for(ll i=head[x];i!=-1;i=a[i].next)
  43. if(a[i].to!=fa[x]&&a[i].to!=son[x])DFS2(a[i].to);
  44. }
  45. ll t[MAXN<<2],lazy[MAXN<<2],f[MAXN];
  46. void Buildtree(ll now,ll l,ll r)
  47. {
  48. if(l==r){t[now]=f[id[l]];lazy[now]=0;return;}
  49. ll mid=(l+r)>>1;
  50. Buildtree(now<<1,l,mid);
  51. Buildtree(now<<1|1,mid+1,r);
  52. t[now]=t[now<<1]+t[now<<1|1];
  53. }
  54. void Pushdown(ll now,ll l,ll r,ll mid)
  55. {
  56. ll W=lazy[now];lazy[now]=0;
  57. t[now<<1]=(t[now<<1]+W*(mid-l+1))%P;
  58. t[now<<1|1]=(t[now<<1|1]+W*(r-mid))%P;
  59. lazy[now<<1]=(lazy[now<<1]+W)%P;
  60. lazy[now<<1|1]=(lazy[now<<1|1]+W)%P;
  61. }
  62. void Add(ll now,ll l,ll r,ll gl,ll gr,ll z)
  63. {
  64. if(l>gr||r<gl)return;
  65. if(l>=gl&&r<=gr){t[now]=(t[now]+(r-l+1)*z)%P;lazy[now]=(lazy[now]+z)%P;return;}
  66. ll mid=(l+r)>>1;
  67. if(lazy[now])Pushdown(now,l,r,mid);
  68. Add(now<<1,l,mid,gl,gr,z);
  69. Add(now<<1|1,mid+1,r,gl,gr,z);
  70. t[now]=(t[now<<1]+t[now<<1|1])%P;
  71. }
  72. ll Query(ll now,ll l,ll r,ll gl,ll gr)
  73. {
  74. if(l>gr||r<gl)return 0;
  75. if(l>=gl&&r<=gr)return t[now];
  76. ll mid=(l+r)>>1;
  77. if(lazy[now])Pushdown(now,l,r,mid);
  78. return (Query(now<<1,l,mid,gl,gr)+Query(now<<1|1,mid+1,r,gl,gr))%P;
  79. }
  80. void Work_A()
  81. {
  82. ll x=read(),y=read(),z=read()%P;
  83. while(top[x]!=top[y])
  84. {
  85. if(deep[top[x]]<deep[top[y]])swap(x,y);
  86. Add(1,1,N,dfn[top[x]],dfn[x],z);
  87. x=fa[top[x]];
  88. }
  89. if(deep[x]<deep[y])swap(x,y);
  90. Add(1,1,N,dfn[y],dfn[x],z);
  91. }
  92. void Work_B()
  93. {
  94. ll x=read(),y=read(),ans=0;
  95. while(top[x]!=top[y])
  96. {
  97. if(deep[top[x]]<deep[top[y]])swap(x,y);
  98. ans=(ans+Query(1,1,N,dfn[top[x]],dfn[x]))%P;
  99. x=fa[top[x]];
  100. }
  101. if(deep[x]<deep[y])swap(x,y);
  102. ans=(ans+Query(1,1,N,dfn[y],dfn[x]))%P;
  103. printf("%d\n",ans);
  104. }
  105. void Work_C()
  106. {
  107. ll x=read(),z=read()%P;
  108. Add(1,1,N,dfn[x],dfn[x]+size[x]-1,z);
  109. }
  110. void Work_D()
  111. {
  112. ll x=read(),ans=Query(1,1,N,dfn[x],dfn[x]+size[x]-1);
  113. printf("%d\n",ans);
  114. }
  115. int main()
  116. {
  117. N=read();M=read();Root=read();P=read();
  118. memset(head,-1,sizeof(head));
  119. for(ll i=1;i<=N;i++)f[i]=read();
  120. for(ll i=1;i<=N-1;i++)
  121. {
  122. ll x=read(),y=read();
  123. link(x,y);link(y,x);
  124. }
  125. DFS1(Root);DFS2(Root);
  126. Buildtree(1,1,N);
  127. for(ll i=1;i<=M;i++)
  128. {
  129. ll kind=read();
  130. if(kind==1)Work_A();
  131. if(kind==2)Work_B();
  132. if(kind==3)Work_C();
  133. if(kind==4)Work_D();
  134. }
  135. return 0;
  136. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注