关于树状数组不太理解的地方

P3038 [USACO11DEC] Grass Planting G

mot1ve @ 2021-03-03 17:34:11

这里l,r数组记录的信息,(l是前序遍历的编号)为什么这样做就进行差分,想不明白为什么这样是对的。求解释


//树状数组+树上差分+倍增LCA
//由于是多次查询修改,要用树状数组维护,修改查询都是logn 
#include<bits/stdc++.h>
using namespace std;
int dfn,t,n,m;
struct node{
    int nxt,to;
}edge[200010];
int head[200010],c[200010],dep[200010],f[200010][30],l[200010],r[200010];
int idx=0;
void add(int u,int v)
{
    edge[++idx].nxt=head[u];
    edge[idx].to=v;
    head[u]=idx;
}
int lowbit(int x)
{
    return x&(-x);
}
void update(int i,int x)
{
    while(i<=n)
    {
        c[i]+=x;
        i+=lowbit(i);
    }
}
int ask(int i)
{
    int res=0;
    while(i>0)
    {
        res+=c[i];
        i-=lowbit(i);
    }
    return res;
}
void dfs(int now,int fath)
{
    dep[now]=dep[fath]+1;
    f[now][0]=fath;
    dfn++;
    l[now]=dfn;
    for(int i=1;i<=t;i++)
    {
        f[now][i]=f[f[now][i-1]][i-1];
    }
    for(int i=head[now];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(v==fath)
        continue;
        dfs(v,now);
    }
    r[now]=dfn;
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y])
    swap(x,y);
    for(int i=t;i>=0;i--)
    {
        if(dep[f[x][i]]>=dep[y])
        {
            x=f[x][i];
        }
    }
    if(x==y)
    return x;
    for(int i=t;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    cin>>n>>m;
    t=(int)(log(n)/log(2))+1;
    for(int i=1;i<=n-1;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u); 
    }
    dfs(1,0);
    while(m--)
    {
        char op;
        int u,v;
        cin>>op;
        scanf("%d%d",&u,&v);
        if(dep[u]<dep[v])
        swap(u,v);
        if(op=='P')
        {
            int lca=LCA(u,v);
            update(l[u],1);
            update(l[v],1);
            update(l[lca],-2);
        }
        else
        {
            printf("%d\n",ask(r[u])-ask(l[u]-1));
        }
    }
    return 0;
}

by mot1ve @ 2021-03-03 17:35:06

普通的树上差分我知道,但不明白为什么这里用树状数组配合l,r数组这么处理是正确的。


by zjjws @ 2021-03-03 19:24:51

@wqy_03

对应到 dfn 序上,$[l_i,r_i]$ 表示的就是以 $i$ 为根的子树的所有点的 dfn 序。

by zjjws @ 2021-03-03 19:25:39

树上差分的询问要做的就是查询一颗子树的权值和,所以就这样就行了。


by zjjws @ 2021-03-03 19:26:27

树状数组只是处理区间和时间复杂度问题的,不要过度在意树状数组。


|