dw网站开发教程,宜昌网站seo收费,假电影网站做注册,用wang域名做购物网站怎么样所谓全局平衡二叉树#xff0c;就是在全局来看都很平衡的二叉树。 #xff08;逃
前言
这个引言倒是实话#xff08;雾 可以把一些本来只能用树剖两个 log 做的问题在单log 时间复杂度解决。 修改通常来说只能支持单点修改。 查询解决链上问题或者全局问题更为方便#x… 所谓全局平衡二叉树就是在全局来看都很平衡的二叉树。 逃
前言
这个引言倒是实话雾 可以把一些本来只能用树剖两个 log 做的问题在单log 时间复杂度解决。 修改通常来说只能支持单点修改。 查询解决链上问题或者全局问题更为方便但子树似乎也是可以的 常数比较大但总比LCT强。
解析
树剖其实可以看成对每一条重链上的节点都维护一棵线段树同一条重链上的节点享受同样的查询复杂度。 但是我们发现这样“看似平衡”的数据结构其实并不平衡因为有的节点可能有非常多的轻儿子而有的节点可能根本没有轻儿子前者在大部分数据中都会更多的被访问到。 因此引出了全局平衡二叉树的思想。
定义一个节点的权值 valxval_xvalx 为其所有轻儿子子树大小1。 全局平衡二叉树的结构和LCT十分相似。先对原树进行重链剖分然后对每个重链维护一棵二叉查找树这里每次选择的区间断点不是中点那样就是线段树了而是按照 valvalval 找到的带权重心并把二叉查找树根节点的父亲设为原树重链头的父亲。 于LCT不同的是这里二叉查找树的结构是静态的。 本人的写法中二叉搜索树的非叶节点都是虚点。
对于一个单点修改修改其信息后不断跳父亲更新即可。
对于一个链上查询对应的是若干条重链的前缀和一条重链的区间前者由建树的定义不难发现每次消耗复杂度必然siz翻倍故是 logn\log nlogn 的后者由于树高为 log故也是 logn\log nlogn 的。
子树就在子树根节点的二叉查找树上找一找需要的节点信息合并即可。
代码
P4751 【模板】“动态DP”动态树分治加强版
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(ok\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}const int N2e6100;
const int inf1e9100;
const bool Flag0;int n,m;
int tot;struct matrix{int x,y;int a[3][3];matrix(int X0,int Y0,int u-inf,int v-inf,int p-inf,int q-inf):x(X),y(Y){a[1][1]u;a[1][2]v;a[2][1]p;a[2][2]q;}
};
matrix operator * (const matrix u,const matrix v){matrix res(u.x,v.y);for(int k1;ku.y;k){for(int i1;iu.x;i){int tmpu.a[i][k];for(int j1;jv.y;j) res.a[i][j]max(res.a[i][j],tmpv.a[k][j]);}}return res;
}vectorinte[N];
int a[N],fa[N],siz[N],val[N],hson[N];
int s0[N],s1[N];
void dfs1(int x,int f){siz[x]1;fa[x]f;for(int to:e[x]){if(tof) continue;dfs1(to,x);siz[x]siz[to];if(siz[to]siz[hson[x]]) hson[x]to;}val[x]siz[x]-siz[hson[x]];return;
}
struct node{matrix ans;int fa,ls,rs;
}tr[N];
int nod[N];
inline void pushup(int x){tr[x].anstr[tr[x].rs].ans*tr[tr[x].ls].ans;
}
int build(int l,int r,int f){if(lr){int xnod[l];matrix o(2,2,s0[x],s1[x],s0[x],-inf);tr[x].anso;tr[x].faf;return x;}int cur(0),sum(0),now(0);for(int il;ir;i) sumval[nod[i]]; for(int il;ir;i){curval[nod[i]];if(cur*2sum) continue;if(ir) --i;nowtot;tr[now].faf;tr[now].lsbuild(l,i,now);tr[now].rsbuild(i1,r,now);break;}pushup(now);return now;
}
inline void ins(int rt,int op){int ftr[rt].fa;if(f){s0[f]op*max(tr[rt].ans.a[1][1],max(tr[rt].ans.a[1][2],max(tr[rt].ans.a[2][1],tr[rt].ans.a[2][2])));s1[f]op*max(tr[rt].ans.a[1][1],tr[rt].ans.a[2][1]);matrix o(2,2,s0[f],s1[f],s0[f],-inf);tr[f].anso;}
}
int dfs2(int x,int f){int top(0);for(int px;p;phson[p]){for(int to:e[p]){if(tohson[p]||tofa[p]) continue;dfs2(to,p);}}for(int px;p;phson[p]){nod[top]p;}int rtbuild(1,top,f);if(f) ins(rt,1);return rt;
}
inline void upd(int x,int y){if(!x) return;s1[x]y;for(int px;p;ptr[p].fa){if(tr[p].fatr[tr[p].fa].ls!ptr[tr[p].fa].rs!p) ins(p,-1);if(px) tr[p].ans.a[1][2]y; if(pn) pushup(p);if(tr[p].fatr[tr[p].fa].ls!ptr[tr[p].fa].rs!p) ins(p,1),ptr[p].fa;}return;
}signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();mread();for(int i1;in;i) s1[i]a[i]read();for(int i1;in;i){int xread(),yread();e[x].push_back(y);e[y].push_back(x);}totn;dfs1(1,0);int rtdfs2(1,0),lst(0);for(int i1;im;i){int xread()^lst,yread();upd(x,s1[x]y-a[x]);a[x]y;printf(%d\n,lstmax(tr[rt].ans.a[1][1],max(tr[rt].ans.a[1][2],max(tr[rt].ans.a[2][1],tr[rt].ans.a[2][2]))));}return 0;
}
practice
SP2666 QTREE4 - Query on a tree IV 本题的难点是如果对每个点开一个堆存储所有轻儿子到父亲的合法点距离最大值修改时需要对堆操作复杂度就两个log了。 一个神奇且小清新的优化方法是把整棵树三度化这样就只有一个轻儿子不必开堆了。
代码实现参考了 hehezhou 的博客。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(ok\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}const int N4e5100;
const int inf1e9;
const bool Flag0;int n,m;#define pr pairint,int
#define mkp make_pair
vectorpre[N];
int dep[N],tot;
int lson[N],wson[N],siz[N],val[N];
inline void link(int x,int y){//debug(link: %d %d\n,x,y);if(!lson[x]) lson[x]y;else wson[x]y;
}
void dfs0(int x,int f){link(xn,x);for(int i0;i(int)e[x].size();i){if(e[x][i].firstf){e[x].erase(e[x].begin()i);break;}}for(int i0;i(int)e[x].size();i){dep[e[x][i].firstn]dep[x];dep[e[x][i].first]dep[x]e[x][i].second;dfs0(e[x][i].first,x);}for(int i1;i(int)e[x].size();i) link(e[x][i-1].firstn,e[x][i].firstn);if(!e[x].empty()) link(x,e[x][0].firstn);
}
struct node{int l,r,ls,rs,lmax,rmax,ans,pre,suf,fa;
}tr[N];
void dfs1(int x){siz[x]1;if(wson[x]){dfs1(wson[x]);siz[x]siz[wson[x]];}if(lson[x]){dfs1(lson[x]);siz[x]siz[lson[x]];}if(siz[wson[x]]siz[lson[x]]) swap(lson[x],wson[x]);val[x]siz[x]-siz[wson[x]];return;
}
int zhan[N];
int build(int l,int r,int f){if(lr){tr[zhan[l]].pretr[zhan[l]].sufzhan[l];tr[zhan[l]].ltr[zhan[l]].rl;tr[zhan[l]].faf;return zhan[l];}int sum(0),cur(0),now(0);for(int il;ir;i) sumval[zhan[i]];for(int il;ir;i){curval[zhan[i]];if(cur*2sum) continue;if(ir) --i;nowtot;tr[now].lsbuild(l,i,now);tr[now].rsbuild(i1,r,now);break;}tr[now].ll;tr[now].rr;tr[now].prezhan[l];tr[now].sufzhan[r];tr[now].faf;if(Flag) printf(now%d (%d %d)\n,now,l,r);return now;
}
int dfs2(int x,int f){int top0;for(int px;p;pwson[p]) zhan[top]p;if(Flag) for(int i1;itop;i) printf(%d ,zhan[i]);if(Flag) puts(\n);int rtbuild(1,top,f);for(int px;p;pwson[p]){if(lson[p]) tr[p].lsdfs2(lson[p],p);}return rt;
}
bool ban[N];
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
inline void pushup(int x){if(tr[x].ltr[x].r){int dtr[ls(x)].lmaxdep[tr[ls(x)].pre]-dep[x];if(!ban[x]){tr[x].lmaxtr[x].rmaxmax(d,0);tr[x].ansmax(tr[ls(x)].ans,0);}else{tr[x].lmaxtr[x].rmaxd;tr[x].anstr[ls(x)].ans;}return;}else{tr[x].lmaxmax(tr[ls(x)].lmax,tr[rs(x)].lmax(dep[tr[rs(x)].pre]-dep[tr[ls(x)].pre]));tr[x].rmaxmax(tr[rs(x)].rmax,tr[ls(x)].rmax(dep[tr[rs(x)].suf]-dep[tr[ls(x)].suf]));tr[x].ansmax(max(tr[ls(x)].ans,tr[rs(x)].ans),tr[ls(x)].rmaxtr[rs(x)].lmaxdep[tr[rs(x)].pre]-dep[tr[ls(x)].suf]);return;}
}
void init(int x){if(!x) return;if(tr[x].ltr[x].r){init(tr[x].ls);}else{init(tr[x].ls);init(tr[x].rs);}pushup(x);if(Flag) printf(x%d lmax%d rmax%d ans%d\n,x,tr[x].lmax,tr[x].rmax,tr[x].ans);return;
}signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endiftr[0].lmaxtr[0].rmaxtr[0].ans-inf;nread();for(int i1;in;i){int xread(),yread(),wread();e[x].push_back(mkp(y,w));e[y].push_back(mkp(x,w));}totnn;dfs0(1,0);dfs1(1);int rtdfs2(1,0);for(int in1;itot;i) ban[i]1;init(rt);if(Flag) for(int i1;itot;i) printf(i%d dep%d\n,i,dep[i]);mread();char c;for(int i1;im;i){scanf( %c,c);if(cA){if(tr[rt].ans0) puts(They have disappeared.);else printf(%d\n,tr[rt].ans);}else{int xread();ban[x]^1;for(;x;xtr[x].fa) pushup(x);}if(Flag) init(rt);if(Flag) puts();}return 0;
}
/*
5
1 2 -8
2 3 -5
1 4 -7
4 5 -6*/
