DFS序与树链剖分

huge_wave · 2025-10-06 15:11:29 · 算法·理论

前言

作者因DFS写得太糖，导致此题调试4h，一节课就过去了

DFS序

这是老师ppt中对DFS的讲解，但这讲了跟讲了一样

不包含树链的操作

我们对一棵树进行DFS，把刚搜到他的顺序计为 in[x] ，离开这个点时记为 out[x] 。很容的知道以 x 为根的子树的 in 值都在 [in[x],out[x]] 之间，所以就可以把子树问题转为区间问题，可以用树状数组、线段树来快速处理
下面给出代码：

1点修改子树查

const int N=1e6+10;
int in[N],out[N],tr[N],cnt=0,a[N];
int maxn=1e6;
vector<int> g[N];
void xg(int x,int z){
    for(;x<=maxn;x+=x&-x){
        tr[x]+=z;
    }
}
int ask(int l,int r){
    int ans=0;
    for(;r>=1;r-=r&-r){
        ans+=tr[r];
    }
    l--;
    for(;l>=1;l-=l&-l){
        ans-=tr[l];
    }
    return ans;
}
void dfs(int x){
    cnt++;
    in[x]=cnt;
    for(int xx:g[x]){
        dfs(xx);
    }
    out[x]=cnt;
}

2