这周给平衡树开了一个头，这周可能是自打寒假以来最用功的一周了，树链剖分和线段树不说掌握的很透彻，但是模板题打的还是很顺手，还有主席树，比较难理解，虽然感觉平衡树更难理解一些，但是时间剩的不大允许了，
贴一下这后的模板：
树链剖分：
vector<int> G[N<<1];
int sz[N],son[N],fa[N],dep[N];
//函数调用 s 为源点：dfs(s,0)
void dfs1(int u,int f) //寻找重儿子
{
sz[u]=1;
dep[u]=dep[f]+1;
fa[u]=f;
son[u]=0; //初始化
int len=G[u].size();
for(int i=0;i<len;i++){ //遍历图
int v=G[u][i];
if(v==f) continue;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[son[u]]<sz[v]) son[u]=v;
}
}
int top[N],tree[N],id[N],tot=0;
//id : dfs序 tree : 线段树序
//函数调用 s 为源点：dfs(s,s)
void dfs2(int u,int f) //dfs序，线段树序
{
top[u]=f;
id[u]=++tot;
tree[tot]=u;
if(!son[u]) return ;
dfs2(son[u],f);
int len=G[u].size();
for(int i=0;i<len;i++){
int v=G[u][i];
if(v==fa[u] || v==son[u]) continue;
dfs2(v,v);
}
}
查询不同链上的节点之和
ll query(int l,int r,int id)
{
int L=node[id].l,R=node[id].r;
if(L>=l && r>=R){
return node[id].sum;
} else{
int mid=L+R>>1;
ll ans=0;
push_down(id);
if(mid>=l) ans+=query(l,r,id<<1);
if(r>=mid+1) ans+=query(l,r,id<<1|1);
push_up(id);
return ans;
}
}
#define nx top[x]
#define ny top[y]
ll ask(int x,int y) //x 左区间，y 右区间
{
ll ans=0;
while(nx!=ny){
if(dep[nx]<dep[ny]) swap(x,y);
ans+=query(id[nx],id[x],1);
x=fa[nx];
}
if(dep[x]>dep[y]) swap(x,y);
return ans+query(id[x],id[y],1);
}
查询和更新还是基于线段树的操作，只不过在函数调用形式上要注意一下
//函数调用 : update(id[x],id[x]+sz[x]-1,1,val)
//更新 x 到其根节点的所有点权
void update(int l,int r,int id,ll val)
{
int L=node[id].l,R=node[id].r;
if(L>=l && r>=R){
node[id].update(val);
} else{
int mid=L+R>>1;
push_down(id);
if(mid>=l) update(l,r,id<<1,val);
if(r>=mid+1) update(l,r,id<<1|1,val);
push_up(id);
return ;
}
}
树剖这里还有一类很经典的题目，也是今天上午才看到的，将节点变成边然后再线段树上操作，就先不更新了，下周说不定还要再放一下树剖的内容和主席树的内容
主席树 ：
const int N=1e5+5;
int n,m,t;
int i,j,k;
int a[N];
vector<int> v;
int root[N],cnt=0; //每一个根节点的编号 结点的个数
struct Node
{
int l,r;
int sum;
}T[N*40];
int get_id(int x)//返回 a[i] 在 v 中的位置
{
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void update(int l,int r,int &x,int y,int pos)
{
T[++cnt]=T[y];
T[cnt].sum++;
x=cnt;
if(l==r) return ;
int mid=l+r>>1;
// pos 在 x 节点的左区间上，右区间不变，左区间从前一个左区间复制过来在更新
if(mid>=pos) update(l,mid,T[x].l,T[y].l,pos);
else update(mid+1,r,T[x].r,T[y].r,pos);
}
int query(int l,int r,int x,int y,int k)
{
if(l==r) return l;
int mid=l+r>>1;
int cnt=T[T[y].l].sum-T[T[x].l].sum;
if(cnt>=k) return query(l,mid,T[x].l,T[y].l,k);
else return query(mid+1,r,T[x].r,T[y].r,k-cnt);
}
int main()
{
//IOS;
while(~sdd(n,m)){
for(i=1;i<=n;i++){
sd(a[i]);
v.pb(a[i]);
}
sort(v.begin(),v.end());
v.erase( unique( v.begin(),v.end() ) ,v.end() );
for(i=1;i<=n;i++) update(1,n,root[i],root[i-1],get_id(a[i]));
int x,y,k;
while(m--){
sddd(x,y,k);
pd( v[query(1,n,root[x-1],root[y],k)-1] );
}
}
//PAUSE;
return 0;
}
现在主席树的题目练习的不是很多，水平和之前的线段树有得一拼，下周结束平衡树专题，做几道主席树的练习，打算开数论了，这连续几周学习数据结构自己不动脑子，就是看题套模板->看题套模板，实力又变水了，不过代码能力确实有所提高，这周感冒也好的差不多了，期待下周能学到更多
