关于线段树合并的一些问题
查看原帖
关于线段树合并的一些问题
397329
To_our_starry_sea楼主2024/9/10 23:36

在树上做线段树合并的时候,我们一般在完成一个节点的合并操作后立即计算当前点的贡献,如下面的代码所示:

inline void dfs(int u) {
    //...
    change(rt[u], ...); //更新当前点
    for (int v : ...) {
       //...
       merge(a, b, ...); //合并
    }
    //...
    query(rt[u], ...) //计算当前点的贡献
}

然而,如果在完成所有的合并之后再计算贡献,如下面的代码所示:

inline void dfs(int u) {
    //...
    change(rt[u], ...); //更新当前点
    for (int v : ...) {
       //...
       merge(a, b, ...); //合并
    }
    
}
int main() {
    //...
    for (int i = 1; i <= n; i++) {
       //...
       query(rt[u], ...) //计算当前点的贡献
    }
}

为什么后者是错误的?

2024/9/10 23:36
加载中...