My approach was to visit all inversion count pair and count how many subarrays these pair contribute. Visiting every pair requires \$\mathcal{O}(n^2)\$ time, but I want an optimized version of this, something like \$\mathcal{O}(n \log n)\$.

Can I do something with the Fenwick tree? Inversion in an array Fenwick tree

e.g. if arr = [1,3,4,2] , then total inversion count for all subarrays = 5.

number = int(input("Input number := "))
main_list = list(map(int,input().split()))
answer = 0
for i in range(number):
    for j in range(number):
        if i<j and main_list[i]>main_list[j]:
            k = (i+1) * (number-j)
            answer += k
  • 2
    \$\begingroup\$ Welcome to Code Review! Is this a task you have chosen for yourself or is this from a programming course or challenge? If so, please include a link to the original problem description and also include it in an abbreviated from directly in your question. \$\endgroup\$ – AlexV Oct 9 '19 at 11:05
  • 2
    \$\begingroup\$ Since you are only concerned with i < j why not put j in range(i + 1, n)? \$\endgroup\$ – Austin Hastings Oct 9 '19 at 15:41
  • 1
    \$\begingroup\$ You need to learn the naming convention.python.org/dev/peps/pep-0008 \$\endgroup\$ – Brijesh Kalkani Oct 9 '19 at 16:48
  • 3
    \$\begingroup\$ This question should include a brief description of what inversion and Fenwick tree mean in this context, as well as links for both. More context will get you a more meaningful review. \$\endgroup\$ – Reinderien Oct 9 '19 at 17:37
  • 1
    \$\begingroup\$ Your original code works. The edit by @brijeshkalkani changed n to number in several places, but k = (i+1) * (n-j) remained unchanged. It also changed l to main_list, but didn't change all occurrences, and mistyped one occurrence as mail_list. Moreover, it changed spacing (a PEP review comment) and added a prompt to an input() that never existed. The edit should never have been approved. \$\endgroup\$ – AJNeufeld Oct 9 '19 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.