动态树LCT小结
最开始看动态树不知道找了多少资料，总感觉不能完全理解。但其实理解了就是那么一回事。。。动态树在某种意思上来说跟树链剖分很相似，都是为了解决序列问题，树链剖分由于树的形态是不变的，所以可以通过预处理节点间的关系，将树转化成连续的区间，再加以其它的数据结构，便能以较快的速度处理序列的修改和查询。
而动态树的问题，是包括了树的合并和拆分操作。这个时候，通过预处理实现的静态树的序列算法不能满足我们的要求，于是我们需要一颗‘动态’的树，能在O(logN)的时间复杂度，处理所有操作。
Splay实现的Link/cut tree
Splay能够维护一颗树的信息，我们将多颗Splay树，通过从下自上的单向边连成一颗树。我们将这些边称为“虚边”
这个时候，Splay树只能维护它本身的节点，而不能照顾到由虚边连成的树。
由于要处理一段序列，我们就要得到一段序列。
下面是杨哲的论文的一段原话：
称一个点被访问过, 如果刚刚执行了对这个点的 ACCESS 操作.
如果结点 v 的子树中, 最后被访问的结点在子树 w 中, 这里 w 是 v 的儿子, 那么就称 w 是 v 的 Pre-
ferred Child. 如果最后被访问过的结点就是 v 本身, 那么它没有 Preferred Child. 每个点到它的 Preferred
Child 的边称作 Preferred Edge. 由 Preferred Edge 连接成的不可再延伸的路径称为 Preferred Path.
这样, 整棵树就被划分成了若干条 Preferred Path. 对每条 Preferred Path, 用这条路上的点的深度作
为关键字, 用一棵平衡树来维护它(在这棵平衡树中, 每个点的左子树中的点, 都在 Preferred Path 中这个点
的上方; 右子树中的点, 都在 Preferred Path 中这个点的下方). 需要注意的是, 这种平衡树必须支持分离与
合并. 这里, 我们选择 Splay Tree 作为这个平衡树的数据结构. 我们把这棵平衡树称为一棵 Auxiliary Tree.
知道了树 T 分解成的这若干条 Preferred Path, 我们只需要再知道这些路径之间的连接关系, 就可以表
示出这棵树 T. 用 Path Parent 来记录每棵 Auxiliary Tree 对应的 Preferred Path 中的最高点的父亲结点,
如果这个 Preferred Path 的最高点就是根结点, 那么令这棵 Auxiliary Tree 的 Path Parent 为 null.
Link-Cut Trees 就是将要维护的森林中的每棵树 T 表示为若干个 Auxiliary Tree, 并通过 Path
Parent 将这些 Auxiliary Tree 连接起来的数据结构.
通过上述的Access操作，我们就可以得到一段从任意点到根的序列，而通过Splay我们又可以将任意点变成根！
同时使用Splay我们可以很轻松地维护点的信息。
从这里似乎看到了LCT的核心思路了。
考虑核心的操作Access:
node *Access (node *u) {
node *v = NIL;
for (; u != NIL; u = u->par) {
Splay (u);
u->Ch[1] = v;
update (v = u);
}
return v;
}
这样每次将当前Splay树连接到虚边连接的上一颗Splay树的根的右子树，就保证了Splay树的二叉树性质，同时对于所有指向儿子的点中，在u到根这个序列中，左儿子的深度总是小于父亲，右儿子的深度总是大于父亲。
正是这个关键的性质可以让我们实现我们需要的功能。
首先第一个想到的自然是找到一个点的根，只需要不断往左子树找就好了
node *getroot (node *x) {
for (x = Access (x); clear (x), x->Ch[0] != NIL; x = x->Ch[0]);
return x;
}
第二个是要让一个结点x变成新的根，显然做过Access后，在序列 根->x中根在Splay树的最左，x在Splay树的最右，此时只要将Splay树的根（注意区分这两个根）的左右子树交换位置，便让x成为了新的根，于是我们只要打上一个交换标记就好了
inline void evert (node *x) {
Access (x)->rev ^= 1;
Splay (x);
}
在打完标记后要让x旋转至根更新Splay树
下面要实现树的合并。要在不同的两颗树的两个结点u，v间连接一条边，那么先要让其中一个点成为根，用虚边连另外一个点，再用Access将虚边变成实边就好了
inline void link (node *x, node *y) {
evert (x);
x->par = y;
Access (x);
}
同样树的分离也是一样，先然其中一个结点x成为根，选取y到x的序列成为一颗Splay树，这个时候再将y旋转至根，那么显然它的左子树包含了除了y的其它点，将它们分离即可
inline void cut (node *x, node *y) {
evert (x);
Access (y);
Splay (y);
y->Ch[0]->par = NIL;
y->Ch[0] = NIL;
update (y);
}
如果要对一段序列进行操作，例如对树上x到y的路径上的点进行操作。先让x成为根，选取y到x的路径上的点和边做一颗Splay树，将y旋转至根（更新Splay树），将标记传给y就好了
inline void modify (node *x, node *y, int w) {
evert (x);
Access (y), Splay (y);
_inc (y, w);
}
查询只要同修改一样，只要直接返回我们需要的值就好了。
下面是一些例题：
只需要将上述操作按要求调用就行了，模板题 ------ 题解
装置从0开始
第i个装置能到达第i + ki个装置，意味着i的父亲是i + ki，如果i + ki 大于等于N，它的父亲就是N，这样即询问树上某个点到N 的距离，即由这点到n的Splay树的节点个数-1；
#include <iostream>
#include <cstdio>
using namespace std; const int MAXN = ; struct node {
int sum;
bool rev;
node *par, *ch[];
node() {sum = , rev = , par = ch[] = ch[] = ;}
node (int a) : sum (a) {rev = , par = ch[] = ch[] = ;}
} dt[MAXN], nil (), *NIL = &nil; struct LinkcutTree {
inline void update (node * x) {
x->sum = x->ch[]->sum + x->ch[]->sum + ;
}
void Rotate (node *x) {
node *p = x->par, *g = p->par;
int c = p->ch[] == x; //0左旋，1右旋
p->ch[c ^ ] = x->ch[c];
if (x->ch[c] != NIL) x->ch[c]->par = p;
x->par = g;
if (g->ch[] == p) g->ch[] = x;
else if (g->ch[] == p) g->ch[] = x;
x->ch[c] = p;
p->par = x;
update (p);
}
//将x旋转至x所在Splay树的根
void Splay (node *x) {
node *p, *g;
while ( (p = x->par) != NIL && (p->ch[] == x || p->ch[] == x) ) {
if ( (g = x->par) != NIL && (p->ch[] == x || p->ch[] == x) ) {
Rotate (x);
}
else {
if ( (g->ch[] == p) == (p->ch[] == x) )
Rotate (p), Rotate (x);
else
Rotate (x), Rotate (x);
}
}
update (x);
}
//获取从u到根的一段
node *Access (node *u) {
node *v = NIL;
for (; u != NIL; u = u->par) {
Splay (u);
u->ch[] = v;
update (v = u);
}
return v;
}
} LCT;
int n, m;
int f[MAXN], vis[MAXN];
int main() {
scanf ("%d", &n);
for (int i = ; i < n; i++)
scanf ("%d", &f[i]); for (int i = ; i <= n; i++) {
dt[i].sum = , dt[i].rev = ;
dt[i].par = dt[i].ch[] = dt[i].ch[] = NIL;
int t = i + f[i] < n ? i + f[i] : n;
if(i!=n) dt[i].par = dt + t;
}
scanf ("%d", &m);
for (int i = , cmd, x, k; i <= m; i++) {
scanf ("%d %d", &cmd, &x);
node * const tem = dt + x;
if (cmd == ) {
LCT.Access (tem);
LCT.Splay(tem);
printf ("%d\n", tem->sum-);
}
else {
scanf ("%d", &k);
LCT.Splay (tem);
tem->ch[]->par = tem->par;
tem->ch[] = NIL;
tem->par = dt + (x + k < n ? x + k : n);
}
}
}
维护cl,cr,sum分别表示最左边的颜色，最右边的颜色，和颜色段数。
每个节点x的相邻的两个节点的颜色就可以由 x->ch[0]->cr 和x->ch[1]->cl 得到
颜色段数也可以由左右儿子得到
要注意的是，在打上翻转标记后cl和cr也要交换
#include <iostream>
#include <cstdio>
using namespace std; const int MAXN = ; struct node {
//本身的颜色，最左边节点的颜色，最右边节点的颜色，颜色段数
int color, cl, cr, sum, cover;
bool rev;
node *par, *ch[];
inline void cov (int x) {
cover = cr = cl = color = x, sum = ;
}
inline void re() {
swap (cl, cr);
rev ^= ;
}
} dt[MAXN], *NIL = dt; struct LinkcutTree {
inline void clear (node *const x) {
if (x == NIL) return ;
if (x->rev) {
swap (x->ch[], x->ch[]);
x->ch[]->re();
x->ch[]->re();
x->rev = ;
}
if (x->cover) {
if (x->ch[] != NIL) x->ch[]->cov (x->cover);
if (x->ch[] != NIL) x->ch[]->cov (x->cover);
x->cover = ;
}
}
inline void update (node * x) {
if (x->ch[] != NIL) x->cl = x->ch[]->cl;
else
x->cl = x->color;
if (x->ch[] != NIL) x->cr = x->ch[]->cr;
else
x->cr = x->color;
x->sum = ;
if (x->ch[] != NIL) {
x->sum += x->ch[]->sum;
if (x->ch[]->cr == x->color) --x->sum;
}
if (x->ch[] != NIL) {
x->sum += x->ch[]->sum;
if (x->ch[]->cl == x->color) --x->sum;
}
}
void Rotate (node *x) {
node *p = x->par, *g = p->par;
int c = p->ch[] == x; //0左旋，1右旋
p->ch[c ^ ] = x->ch[c];
if (x->ch[c] != NIL) x->ch[c]->par = p;
x->par = g;
if (g->ch[] == p) g->ch[] = x;
else if (g->ch[] == p) g->ch[] = x;
x->ch[c] = p;
p->par = x;
update (p);
}
void Splay (node *x) {
node *p, *g;
clear (x);
while ( (p = x->par) != NIL && (p->ch[] == x || p->ch[] == x) ) {
if ( (g = p->par) != NIL && (g->ch[] == p || g->ch[] == p) ) {
clear (g), clear (p), clear (x);
if ( (g->ch[] == p) == (p->ch[] == x) )
Rotate (p), Rotate (x);
else
Rotate (x), Rotate (x);
}
else {
clear (p), clear (x);
Rotate (x);
}
}
update (x);
}
node *Access (node *u) {
node *v = NIL;
for (; u != NIL; u = u->par) {
Splay (u);
u->ch[] = v;
update (v = u);
}
return v;
}
inline void evert (node *x) {
Access (x)->re();
Splay (x);
}
inline void link (node *x, node *y) {
evert (x);
x->par = y;
Access (x);
}
inline int query (node *x, node *y) {
evert (x);
Access (y), Splay (y);
return y->sum;
}
inline void modify (node *x, node *y, int w) {
evert (x);
Access (y), Splay (y);
y->cov (w);
}
} LCT; int n, m; int main() {
scanf ("%d %d", &n, &m);
for (int i = , x; i <= n; i++) {
scanf ("%d", &x);
dt[i].par = dt[i].ch[] = dt[i].ch[] = NIL;
dt[i].cover =, dt[i].sum = ;
dt[i].cl = dt[i].cr = dt[i].color = x+;
}
for (int i = , x, y; i < n; ++i) {
scanf ("%d %d", &x, &y);
LCT.link (dt + x, dt + y);
}
char cmd;
for (int i = , u, v, k; i <= m; i++) {
scanf ("\n%c %d %d", &cmd, &u, &v);
if (cmd == 'Q')
printf ("%d\n", LCT.query (dt + u, dt + v) );
else if (cmd == 'C') {
scanf ("%d", &k);
LCT.modify (dt + v, dt + u, k+);
}
}
return ;
}
重点在于处理加和乘的共存问题
乘的时候所有值都要乘，加的时候sum要算上Splay树所有节点，中间值会爆INT
/*
BZOJ 2631 LCT
需要的操作 路径权值 + *
处理+和*的共存
*/
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std; const int MAXN = , mod = ; struct node {
int val, sum, inc, mtp,cnt;
bool rev;
node *par, *ch[];
} dt[MAXN], *NIL = dt; struct LinkcutTree {
inline void _inc (node * x, int inc) {
if (x == NIL) return;
x->inc=(x->inc + inc)%mod;
x->val=(x->val + inc)%mod;
x->sum=(x->sum + ((ll)inc*x->cnt)%mod)%mod;
}
inline void _mtp (node *x, int mtp) {
if (x == NIL) return;
x->inc=((ll)x->inc * mtp)%mod;
x->val=((ll)x->val * mtp)%mod;
x->sum=((ll)x->sum*mtp)%mod;
x->mtp=((ll)x->mtp*mtp)%mod;
}
inline void clear (node *const x) {
if (x == NIL) return ;
if (x->mtp!=) {
_mtp (x->ch[], x->mtp);
_mtp (x->ch[], x->mtp);
x->mtp = ;
}
if (x->inc) {
_inc (x->ch[], x->inc);
_inc (x->ch[], x->inc);
x->inc = ;
}
if (x->rev) {
swap (x->ch[], x->ch[]);
x->ch[]->rev ^= ;
x->ch[]->rev ^= ;
x->rev = ;
}
}
inline void update (node * x) {
x->sum=x->val,x->cnt=;
if(x->ch[]!=NIL) {
x->sum=(x->sum+ x->ch[]->sum);
x->cnt=(x->cnt+ x->ch[]->cnt);
}
if(x->ch[]!=NIL) {
x->sum=(x->sum+ x->ch[]->sum);
x->cnt=(x->cnt+ x->ch[]->cnt);
}
while(x->sum>=mod) x->sum-=mod;
}
void Rotate (node *x) {
node *p = x->par, *g = p->par;
int c = p->ch[] == x; //0左旋，1右旋
p->ch[c ^ ] = x->ch[c];
if (x->ch[c] != NIL) x->ch[c]->par = p;
x->par = g;
if (g->ch[] == p) g->ch[] = x;
else if (g->ch[] == p) g->ch[] = x;
x->ch[c] = p;
p->par = x;
update (p);
}
void Splay (node *x) {
node *p, *g;
clear (x);
while ( (p = x->par) != NIL && (p->ch[] == x || p->ch[] == x) ) {
if ( (g = p->par) != NIL && (g->ch[] == p || g->ch[] == p) ) {
clear (g), clear (p), clear (x);
if ( (g->ch[] == p) == (p->ch[] == x) )
Rotate (p), Rotate (x);
else
Rotate (x), Rotate (x);
}
else {
clear (p), clear (x);
Rotate (x);
}
}
update (x);
}
node *Access (node *u) {
node *v = NIL;
for (; u != NIL; u = u->par) {
Splay (u);
u->ch[] = v;
update (v = u);
}
return v;
}
inline void evert (node *x) {
Access (x)->rev ^= ;Splay (x);
}
inline void link (node *x, node *y) {
evert (x);x->par = y;Access (x);
}
inline void cut (node *x, node *y) {
evert (x);Access (y);Splay (y);
x=y->ch[]->par = NIL;
update (y);
}
inline int query (node *x, node *y) {
evert (x);Access (y), Splay (y);
return y->sum;
}
inline void modifyadd (node *x, node *y, int w) {
evert (x);Access (y), Splay (y);
_inc (y, w);
}
inline void modifymtp (node *x, node *y, int w) {
evert (x);Access (y), Splay (y);
_mtp (y, w);
}
} LCT;
int n, q;
int main() {
scanf("%d %d",&n,&q);
for (int i = ; i <= n; i++) {
dt[i].inc = ;
dt[i].mtp = dt[i].sum = dt[i].val = dt[i].cnt=;
dt[i].par = dt[i].ch[] = dt[i].ch[] = NIL;
}
for (int i = , x, y; i < n; i++) {
scanf("%d %d",&x,&y);
LCT.link (dt + x, dt + y);
}
char cmd;
for (int i = , x, y, k, u, v; i <= q; i++) {
scanf ("\n%c", &cmd);
switch (cmd) {
case '+': {
scanf ("%d %d %d", &x, &y, &k);
LCT.modifyadd (dt + x, dt + y, k);
break;
};
case '-': {
scanf ("%d %d %d %d", &x, &y, &u, &v);
LCT.cut (dt + x, dt + y);
LCT.link (dt + u, dt + v);
break;
}
case '*': {
scanf ("%d %d %d", &x, &y, &k);
LCT.modifymtp (dt + x, dt + y,k);
break;
}
case '/': {
scanf ("%d %d", &x, &y);
printf ("%d\n", LCT.query (dt + x, dt + y) );
break;
}
}
}
}
最新文章
- Django进阶（三）
- dp入门--poj 1163数塔
- 将mac上的项目上传到oschina，进行代码托管。
- Java-URL类详解
- jquery ajax 提交信息后等待返回的提示信息
- IEnumerable
- 性能是全新的 SEO
- 求n阶勒让德多项式
- hdu 5583 Kingdom of Black and White
- GO 基础
- fmt.Sprintf格式化使用
- Moqui 代码解释
- 电子签名在K2中的应用
- uniGUI经验几则
- MQTT再学习 -- MQTT 客户端源码分析
- d9
- Python 模块之wxpython 的应用
- MariaDB 视图与触发器(11)
- 用Canvas做动画
- Activity服务类-1 DynamicBpmnService服务类
热门文章
- java jdbc使用配置文件连接数据库：
- Longest Consecutive Sequence——Leetcode
- [转载+整理]JVM性能调优----JVM架构
- 突破LVS瓶颈，LVS Cluster部署（OSPF + LVS） - lxcong的运维技术 - 开源中国社区
- v
- servlet清晰理解
- iOS开发总结-搜索功能实现--使用SKTag
- Java Web中资源的访问路径
- Microsoft office word关闭英文输入首字母大写设置
- 树莓派安装mjpg-streamer视频监控 分类： Raspberry Pi 2015-04-12 23:41 144人阅读 评论(0) 收藏