在树上做线段树合并的时候,我们一般在完成一个节点的合并操作后立即计算当前点的贡献,如下面的代码所示:
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], ...)
}
}
为什么后者是错误的?