一个关于复杂度的疑问

倍增lca+树上差分的复杂度是O（nlogn）还是O（n+nlogn）。就像luogu P3128

倍增LCA+树上差分的复杂度是 O(n+nlogn)。

倍增LCA 算法的时间复杂度是 O(nlogn)，其中 n 是节点数。这是因为倍增LCA 算法通过在倍增数组上进行二进制搜索来求出 LCA，其中每次搜索的时间复杂度为 O(logn)。

树上差分的时间复杂度是 O(n)，其中 n 是节点数。这是因为树上差分算法通过遍历树上的每个节点来计算差分值，每次遍历的时间复杂度为 O(1)。

所以总的时间复杂度为O(n+nlogn).

对于倍增Ica+树上差分，复杂度是O(n + nlogn)，其中n为结点个数。
对于倍增Ica+树上差分，在建树时需要O(nlogn)的时间复杂度，而每次查询单点修改后的答案则需要O(n)的时间复杂度。因此总的时间复杂度为O(n + nlogn)。
对于倍增Ica+树上差分，空间复杂度是O(nlogn)，其中n为结点个数。倍增Ica+树用于求解线段树，其中需要以O(nlogn)的空间复杂度存储n个节点信息，以及它所对应的logn个父节点信息。