题解里说的两颗线段树合并时间复杂度就是两颗线段树的重合节点数, 也就是不大于较小的那棵线段树的节点数, 这个我理解。
所以将 n 棵线段树合并起来的复杂度是 O(总节点数), 但我认为, 这里合并的顺序应该有要求吧, 比如: 将线段树2, 3, 4, ..., n分别与线段树1合并。这样才是 O(总节点数)的。
但是这道题题解里, 是将 u 与他的儿子的子树内线段树全部合并起来之后的线段树合并, 相当于每次合并是 O(子树内所有线段树节点数), 那这样时间复杂度不是 O(n2logn)的?但是题解里就是这么写的, 我也这么写, 并且通过了这道题, 所以麻烦有没有大佬解答一下疑惑。