Define a "prefix" relationship between two positive integers

Definition: y is a prefix of x, as long as the bits in y which are no lower than lowest bit 1 are the same with those in x. For example, assume x = 11010010b, prefix of x can be y = 10000000b, 11000000b, 11010000b, 11010010b.

It's easy to see that the condition "y is a prefix of x" equals to "0 ≤ x-y < lowbit(y)". Therefore, if x is inside [y, y+lowbit(y)), then y is a prefix of x.

Look into prefixes of numbers that are bigger than x

Accroding to the conclusion in item 1. :

if x is inside [y, y+lowbit(y)), then y is a prefix of x

given collection C(n) = {c_1, c_2, c_3,...} where c_1 = y, c_{i+1} = c_i + lowbit(c_i) for i = 1,2,…, for any integer x inside [n, +∞), there is one and only one y in C(x) to be a prefix of y.

Take x = 11010010b as example, each time add 1 to x, we get

x prefix
11010010b 11010010b
11010011b 11010010b
11010100b 11010100b = 11010010b+10b
11010101b 11010100b
... ...
11010111b 11010100b
11011000b 11011000b = 11010100b+100b
... ...
11100000b 11100000b = 11011000b+1000b
... ...
100000000b 100000000b = 11100000b+100000b
... ...

Understand the code

-map<int, int> bit: If nums[i]-1 has a prefix to be c, there are additionally bit[c] elements in 2*nums[i+1:n-1] which are no bigger than nums[i]-1.

-void add(long long x): For every c in C(x), do ++bit[c].

-int que(long long x): For every c that is a prefix of x, do ans+=bit[c].

If i < j & nums[i]-1 ≥ 2*nums[j], then there is one and only one c to satisfy both "c ∈ C(nums[i]-1)" and "c is prefix of nums[i]-1". Therefore, a ++bit[c] would be done in add(2*nums[j]) and after for(j=n-1;j>i;--j){add(2*bit[nums[j]]);} a ans+=bit[c] would be done in que(nums[i]-1).

Analysis the complexity

Size of map<int, int> bit is no more than 34n. Comlexity of void add(long long x) is O(34log(34n)) = O(log n), so is that of int que(long long x). Thus the complexity of int reversePairs(vector<int>& nums) is O(n log n).

This solution is very beautiful.