Subtree Inversion Sum II - Solution & Explanation

Problem Overview: You are given a tree where each node has a value. For every node, consider the values inside its subtree and count inversion pairs (i, j) where i appears before j but value[i] > value[j]. The task is to efficiently compute the inversion contribution across all subtrees without recomputing from scratch for each node.

Approach 1: Recompute Inversions Per Subtree (Brute Force) (O(n^2 log n) time, O(n) space)

Traverse the tree with DFS. For each node, collect all values from its subtree into an array. Run a classic inversion counting algorithm using merge sort on that array. Merge sort counts inversions in O(k log k) for a subtree of size k. Since many subtrees overlap and nodes may be processed repeatedly, the total runtime grows toward O(n^2 log n). This method is straightforward and useful for validating correctness on small inputs but does not scale to large trees.

Approach 2: DFS + Small-to-Large Set Merging (DSU on Tree) (O(n log n) time, O(n) space)

Process the tree using postorder DFS. Each node maintains a balanced structure (such as a multiset or Fenwick-friendly ordered container) storing values from its subtree. While returning from recursion, merge child containers into the largest one using the small-to-large technique. When inserting elements from the smaller container, query how many existing values are greater to count new inversion pairs. Because each element moves containers only logarithmically many times, the total complexity becomes O(n log n). This pattern is commonly called DSU on tree and appears frequently in advanced tree problems.

Approach 3: Euler Tour + Fenwick Tree (O(n log n) time, O(n) space)

Flatten the tree using an Euler tour so every subtree becomes a contiguous range in an array. After coordinate-compressing values, process nodes while maintaining a Fenwick Tree or Binary Indexed Tree. As nodes enter the structure, query the number of previously inserted values greater than the current one to accumulate inversion counts. Range boundaries from the Euler tour allow subtree queries to be handled efficiently. This approach replaces explicit set merging with prefix-sum queries and updates.

Recommended for interviews: Interviewers usually expect the small-to-large merging (DSU on tree) approach or an Euler tour combined with a Fenwick Tree. The brute-force solution demonstrates understanding of inversion counting with merge sort, but the optimized O(n log n) solution shows you can combine DFS, subtree processing, and ordered data structures to eliminate repeated work.