ETT学习笔记
ETT(Eular Tour Tree)是一种维护有根树的数据结构,支持以下操作
- 修改一个点的点权
- 子树修改
- 单点查询
- 点到根路径查询
- 修改一个点的父亲
据说可以支持换根,但用的不多而且据说很难写,所以似乎失传了(
其实没啥技术含量,顾名思义就是维护一棵树的欧拉序。
欧拉序指在 dfs开始和结束时分别将当前点加入序列中,也称括号序。
用区间平衡树维护这个欧拉序。
平衡树不写 treap ,根本不是人
每个点第一次插入的权值为题目给定的权值,第二次插入时取相反数,要在平衡树上记录下这个符号,并记录下 每个原树上的点 两次插入时 在平衡树上的点 的编号。
对treap额外维护平衡树上的父结点 fa,然后可以找到给定编号的结点在平衡树上的排名。
单点操作直接搞就可以了。
因为欧拉序上一个子树对应的是一个括号,子树修改时直接修改这个括号的区间。注意每个点要分别乘上自己的符号,可以通过记录平衡树的子树的符号之和实现。
对于链查询,不难看出是这个点第一次出现的位置的前缀和,直接查询即可。
修改父亲直接把整个括号提出来插进新父亲第一次位置的后面。
复杂度是O ( n log n ) O(n\log n)O(nlogn),跑得比较慢
模板题
#include
#include
#include
#include
#include
#include
#include
#define MAXN 200005
#define MAXM 400005
using namespace std;
inline char gal()
{
char c=getchar();
while (!isalpha(c)) c=getchar();
return c;
}
inline int read()
{
int ans=0;
char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
typedef long long ll;
vector e[MAXN];
int w[MAXN];
int sig[MAXN],ind[MAXN],siz[MAXN],rad[MAXN],ch[MAXN][2],fa[MAXN],tot;
ll val[MAXN],sum[MAXN],lzy[MAXN];
inline int newnode(int v,int type)
{
++tot,siz[tot]=1,sum[tot]=val[tot]=v*type,sig[tot]=ind[tot]=type,rad[tot]=rand();
return tot;
}
inline void update(int x)
{
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1,ind[x]=ind[ch[x][0]]+ind[ch[x][1]]+sig[x];
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
}
inline void pushlzy(int x,ll v){val[x]+=sig[x]*v,sum[x]+=v*ind[x],lzy[x]+=v;}
inline void pushdown(int x)
{
if (lzy[x])
{
if (ch[x][0]) pushlzy(ch[x][0],lzy[x]);
if (ch[x][1]) pushlzy(ch[x][1],lzy[x]);
lzy[x]=0;
}
}
int merge(int x,int y)
{
if (!x||!y) return x|y;
pushdown(x),pushdown(y);
if (rad[x]
- 上一篇 »java获取src下文件路径和获取webRoot下文件路径
- 下一篇 »CSS绝对定位属性