Computer Science Homework Solutions
Problem
#71581

Order-statistic tree (Augmenting Data Structures)

Need help to show how to use an order-statistic tree to count the number of inversions in an array of size n in time O(n lg n).

Note that we call a pair (i,j) an inversion if i < j, but key[i] > key[j]. Thus, an increasing sequence has no inversions. A decreasing list has the maximum number of inversions, n(n-1)/2.

I believe we start by letting k be the number of inversions in the sequence.  We then create an order-statistic tree and store with each node the original index in the sequence.  

Is there anything else we store in the node and what would be the algorithm for the number of inversions?

Solution
What is this?
By OTA - Overall OTA Rating
Xiao Liu, MS - 4.7/5
Purchase Cost Now
$2.19 CAD (was ~$19.95)
Included in Download
  • Plain text response
  • Attached file(s):
    • OS-inversion.doc
$2.19 Instant Download
Add to Cart
Why you can trust BrainMass.com
  • Your Information is Secure
  • Best Online Academic Help Service
  • Students find real academic Success
Related Solutions
  • This is a problem about Network Flows. - see attachment
  • Algorithm Problem - Let G = (V, E) be a flow network with source s, sink t, and suppose each edge e  E has capacity c(e) = 1. Assume also, for convenience, that |E| =  (V). a. Suppose we implement the ...
  • Smooth functions - PLEASE see attachment for proper display of equations. Let f be a function from N to R+ . Function f is eventually nondecreasing if such that . Function f is smooth if it is eventually nond ...
  • CountLetters.cpp C++ - Please enhance this program so that it would output a list of all the letters that occur in the text together with the number of times each letter occurs, listed in descending order by frequency. ...
  • Web Site Structures - Describe Web site structures and the purpose of each structure.
Browse