关于BIT实现的空间的疑问
查看原帖
关于BIT实现的空间的疑问
542063
MightZero楼主2024/9/28 12:14

rt,大部分题解中对于统计父亲节点对子树贡献的树状数组所开空间的大小都是当前节点的子树大小

然而是否存在数据使得点分树上父亲节点到当前节点的距离大于子树大小导致爆空间?

即在以下代码中:

void modify(ll u,ll w)
{
    ll x=u;
    while(x)
    {
        bit[x][0].modify(dis(u,x)+1,w);
        if(dfa[x])bit[x][1].modify(dis(dfa[x],u)+1,w);
        x=dfa[x];
    }
}

dis(dfa[x],u)是否可能超过bit[x][1]的大小?

求dalao解答

2024/9/28 12:14
加载中...