A normal segment tree is a full binary tree and it has n leaf nodes and n-1 internal nodes.

Hence, 2*n-1 nodes in total.

So, for building a segment tree, the value of every node is calculated once so complexity is O(n).

But for a merge sort tree, we combine the sorted vectors from current node’s left and right child using O(n) two-pointer merge. We do this for every non-leaf node, so why the overall build complexity of merge sort tree is not O(n*n)?