树链剖分学习笔记
有关树链剖分的内容，其中有一篇文章我十分推荐
http://www.cnblogs.com/chinhhh/p/7965433.html
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
这里面讲的树链剖分内容也还算是比较详细了
接下来是我自己对树链剖分的一系列理解
首先是，树上的操作，单一操作比如说：x—y的路径上全部加和，这个时候我们可以利用树上差分的思想来做，这个时候再加上LCA可以达到修改O(1)，查询O(N)
但是如果是多次修改多次查询，极端的情况下复杂度能够到达O(N^2)（原因就是一次修改一次查询，每次都要用O(N)来查询）
接下来我们就引入了树链剖分
其实就是进行两次dfs，第一次dfs记录树上信息，第二次dfs将树上的链转化成一个又一个连续的区间，用线段树或者树状数组这样的数据结构进行维护
树链剖分查询查询修改的时间复杂度是NlogN（因为通过长链的拼接，来拆分成至少longer/2的长度）
基本需要维护的树上信息就是deep深度，fa父亲，size子树大小，son重儿子节点
然后转化成区间的操作，为了让链条连续，并且尽量让长的尽量长，这个时候就是将重儿子的所在链优先处理，然后再处理其他的儿子
这个时候需要维护的信息就是转化成区间上该点所在区间上的ID，以及该id所对应的点，该点在原数组的数据，链条端点用于快速跳转，
这个时候操作X点和Y点的路径上的数据的时候，一直往上找TOP，如果他们的TOP不相等，说明还未在一条链上，这个时候只需要在他们的连续的链上直接用数据结构进行操作，一直到他们的top节点相等，这个时候他们必定在在一条链上
1 #include <bits/stdc++.h> 2 3 typedef long long ll; 4 5 const int MAXN=100010, MAXM=1000010; 6 7 int N, M, R, MOD; 8 9 int ver[MAXM],next[MAXM],/* edge[MAXM], */head[MAXN],tot; 10 int deep[MAXN],fa[MAXN],size[MAXN],son[MAXN]; 11 int id[MAXN],rk[MAXN]; 12 int top[MAXN]; 13 int pos; 14 15 struct SegmentTree { 16 int l, r; 17 int dat; 18 int lazy; 19 } Tree[MAXN * 4]; 20 int num[MAXN],NUM[MAXN]; 21 22 void build(int p, int l, int r) { 23 Tree[p].l = l; 24 Tree[p].r = r; 25 if (l == r) { 26 Tree[p].dat = num[l]; 27 return; 28 } 29 int mid = (l + r) >> 1; 30 build(p * 2, l, mid); 31 build(p * 2 + 1, mid + 1, r); 32 Tree[p].dat = (Tree[p * 2].dat + Tree[p * 2 + 1].dat)%MOD; 33 } 34 35 void spread(int p) { 36 if (Tree[p].lazy) { 37 Tree[p * 2].dat += (Tree[p].lazy * (Tree[p * 2].r - Tree[p * 2].l + 1)); 38 Tree[p*2].dat%=MOD; 39 Tree[p * 2 + 1].dat += (Tree[p].lazy * (Tree[p * 2 + 1].r - Tree[p * 2 + 1].l + 1)); 40 Tree[p*2+1].dat%=MOD; 41 Tree[p * 2].lazy += Tree[p].lazy; 42 Tree[p * 2 + 1].lazy += Tree[p].lazy; 43 Tree[p].lazy = 0; 44 } 45 } 46 47 void change(int p, int l, int r, int d) { 48 if (l <= Tree[p].l && Tree[p].r <= r) { 49 Tree[p].dat += (long long)d * (Tree[p].r - Tree[p].l + 1); 50 Tree[p].dat%=MOD; 51 Tree[p].lazy += d; 52 return; 53 } 54 spread(p); 55 int mid = (Tree[p].l + Tree[p].r) >> 1; 56 if (l <= mid) change(p * 2, l, r, d); 57 if (mid < r) change(p * 2 + 1, l, r, d); 58 Tree[p].dat = Tree[p * 2].dat + Tree[p * 2 + 1].dat; 59 Tree[p].dat%=MOD; 60 } 61 62 long long ask(int p, int l, int r) { 63 if (l <= Tree[p].l && Tree[p].r <= r) return Tree[p].dat; 64 spread(p); 65 int mid = (Tree[p].l + Tree[p].r) >> 1; 66 long long val = 0; 67 if (l <= mid) val += ask(p * 2, l, r),val%=MOD; 68 if (mid < r) val += ask(p * 2 + 1, l, r),val%=MOD; 69 return val; 70 } 71 72 void addedge(int u,int v){ 73 ver[++tot]=v; 74 next[tot]=head[u]; 75 head[u]=tot; 76 } 77 78 void dfs1(int u,int par,int d){ 79 deep[u]=d; 80 fa[u]=par; 81 size[u]=1; 82 for(int i=head[u];i;i=next[i]) 83 { 84 int v=ver[i]; 85 if(v!=par) 86 { 87 dfs1(v,u,d+1); 88 size[u]+=size[v]; 89 if(size[v]>size[son[u]]) 90 son[u]=v; 91 } 92 } 93 } 94 95 void dfs2(int u,int sp){ 96 top[u]=sp; 97 id[u]=++pos; 98 num[pos]=NUM[u]; 99 rk[pos]=u; 100 if(son[u]==0) return; 101 dfs2(son[u],sp); 102 for(int i=head[u];i;i=next[i]) 103 { 104 int v=ver[i]; 105 if(v!=son[u] && v!=fa[u]) 106 dfs2(v,v); 107 } 108 } 109 110 ll queryRange(int l,int r){ 111 ll ans=0; 112 while(top[l]!=top[r]) 113 { 114 if(deep[top[l]]<deep[top[r]]) 115 std::swap(l,r); 116 ans+=ask(1,id[top[l]],id[l]); 117 ans%=MOD; 118 l=fa[top[l]]; 119 } 120 if(deep[l]>deep[r]) std::swap(l,r); 121 ans+=ask(1,id[l],id[r]); 122 ans%=MOD; 123 124 return ans; 125 } 126 127 ll querySon(int p){ 128 return ask(1,id[p],id[p]+size[p]-1); 129 } 130 131 void changeRange(int l,int r,int d){ 132 while(top[l]!=top[r]) 133 { 134 if(deep[top[l]]<deep[top[r]]) 135 std::swap(l,r); 136 change(1,id[top[l]],id[l],d); 137 l=fa[top[l]]; 138 } 139 if(deep[l]>deep[r]) 140 std::swap(l,r); 141 change(1,id[l],id[r],d); 142 } 143 144 void changeSon(int p,int d){ 145 change(1,id[p],id[p]+size[p]-1,d); 146 } 147 148 int main(){ 149 std::cin>>N>>M>>R>>MOD; 150 for(int i=1;i <= N;i++) 151 scanf("%d",&NUM[i]); 152 for(int i=1;i < N;i++) 153 { 154 int x,y; 155 scanf("%d%d",&x,&y); 156 addedge(x,y); 157 addedge(y,x); 158 } 159 dfs1(R,0,1); 160 dfs2(R,R); 161 build(1,1,N); 162 int x,y,z; 163 ll ans=0; 164 for(int i=1;i <= M;i++) 165 { 166 int opera; 167 scanf("%d",&opera); 168 if(opera == 1) 169 { 170 scanf("%d%d%d",&x,&y,&z); 171 changeRange(x,y,z); 172 } 173 if(opera==2) 174 { 175 scanf("%d%d",&x,&y); 176 ans=queryRange(x,y); 177 printf("%lld\n",ans); 178 } 179 if(opera==3) 180 { 181 scanf("%d%d",&x,&y); 182 /* printf("%d %d\n",id[x],id[x]+size[x]-1); */ 183 changeSon(x,y); 184 } 185 if(opera==4) 186 { 187 scanf("%d",&x); 188 ans=querySon(x); 189 printf("%lld\n",ans); 190 } 191 } 192 return 0; 193 }
更多精彩
