Sort the edges by the index on the left of the node, then (for equal left indices) by the index on the right of the node. Look at the indices of the right nodes. Each intersection on the chart corresponds to a pair of indices not ordered in this sorted list. You just need to count such pairs “out of order”.
Insert each index on the right side of the node from the sorted list into the binary index tree. After each insertion, you can find how many large indexes are already in the tree in O (log (m)). Thus, the time complexity of the whole algorithm is O (h * (log (h) + log (m))): O (h * log (h)) for sorting and O (h * log (m)) for calculating the number of index inversions (here "h" is the number of edges). You can improve this to O (h * log (m)) by sorting or radix sorting.
Update:
As Android Decoded noted, a number of inversion problems can be solved using the Merge Sort separation and dormancy algorithm. Detailed description here . This approach has a greater time complexity O (h * log (h)) than the complexity of using the binary index tree O (h * log (m)), but for sparse graphs, where the number of edges is not much larger than the number of nodes, it should be faster because it requires less memory and is more convenient for caching.
The complexity of the Merge Sort approach can be improved to O (h * log (m)) if we exclude duplicate entries during the merge. To do this, apply Merge Sort for pairs (value, numberOfInstances), where adjacent identical values are combined into one record with the corresponding "numberOfInstances". In the worst case, duplicates are not deleted for the first log (m) merge, this has complexity O (h * log (m)); then until log (n) passes remain when duplicates are quickly eliminated O (h) times.
Binary Index Usage Details:
Implement a binary index tree, which for a given key can return its index in the tree, starting with the highest value (largest → index 0, second largest → index 1, ...). Then, after inserting each element into the tree, request its index - this will be the number of large values to the left of this element in the sorted list.
More: The binary index tree can be implemented as a search tree, each of which node is supplemented by a counter of descendant nodes. Do not create separate nodes for duplicate elements, just update the node counters for each of them. When querying an index for a certain key, we must first find the node corresponding to this index in the tree; then we should summarize all the counters for the immediate descendant of the descendants of each ancestor of the current node, including the right descendant of the current node, but excluding all cases when the current node is to the right of some of its ancestors.