// f is a frequency array. In your case, since n <= 10^5, declare it as int f[100004]; // The 2 methods below are code for Fenwick Tree, super short int rsq(int b) { // range sum query int s = 0; while (b) s += f[b], b -= b & -b; return s; } void adj(int k, int v) { // adjust // L should be the maximum value in the array, but the maximum value and the length of the input happens to be the same, so I'm being sloppy here. while (k <= L) f[k] += v, k += k & -k; } // main s = 0; // Number of inversions for (i = 1; i <= L; i++) { // L is the number of elements in the array ... // Assign the current element in the array to v adj(v, 1); // Adjust + 1 at value v in the Fenwick Tree s += i - rsq(v); // rsq(v) will be the number of numbers smaller than or equal to v. // i - rsq(v) will be number of numbers strictly larger than v }