## Leetcode 493

Posted on 13 Feb 2017
binary indexed tree discretization

### Tutorial

First, do the discretization. The discretization array should taken into account both nums[i] and nums[i] * 2.

Then, insert the elements into binary indexed tree from left. Before inserting nums[i], we should check how many elements in the binary indexed tree is greater than nums[i] * 2, and add it to the final answer.

From this problem, we can generalize the discretization method. It can discretize not only the elements of an array, but also some other elements together and keep their relations (greater, less). Note: Multiset will cause TLE since std::distance would take linear time to the size of the multiset.

### Solution

class Discrete:

def __init__(self, f):
self.f = list(set(f))
self.f.sort()

def index(self, a):
import bisect
return bisect.bisect_left(self.f, a)

class BITree:

def __init__(self, n):
self.f = [0]*(n+3)
self.n = n + 2

def sum(self, pos=None):
if not pos:
i = self.n
else:
i = pos
s = 0  #initialize result
while i > 0:
s += self.f[i]
i -= i & (-i)
return s

def update(self, pos ,value):
i = pos
while i <= self.n:
self.f[i] += value
i += i & (-i)

class Solution(object):
def reversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums2 = nums + list(map(lambda x: x * 2, nums))
d = Discrete(nums2)
bit = BITree(len(d.f))
ret = 0
for x in nums:
index = d.index(x) + 1
ret += bit.sum() - bit.sum(d.index(x * 2) + 1)
bit.update(index, 1)
return ret

#print(Solution().reversePairs([-5,-5]))
#print(Solution().reversePairs([1,3,2,3,1]))
#print(Solution().reversePairs([]))
#print(Solution().reversePairs([2,4,3,5,1]))


#define d(x)
#define LL long long
#define MAX_N (int(5e4 + 10) * 2)
struct BIT
{
LL binary_indexed_tree[MAX_N];

void init()
{
memset(binary_indexed_tree, 0, sizeof(binary_indexed_tree));
}

int low_bit(int x)
{
return x & (-x);
}

{
for (int i = pos; i < MAX_N; i += low_bit(i))
{
binary_indexed_tree[i] += val;
}
}

LL sum(int pos)
{
LL ret = 0;
for (int i = pos; i > 0; i -= low_bit(i))
{
ret += binary_indexed_tree[i];
}
return ret;
}
};

class Solution {
public:
int reversePairs(vector<int>& nums) {
vector<long long> discrete = vector<long long> ();
for (int i = 0; i < (int)nums.size(); i++) {
discrete.push_back(nums[i]);
discrete.push_back(nums[i] * 2LL);
}
sort(discrete.begin(), discrete.end());
discrete.resize(std::distance(discrete.begin(), unique(discrete.begin(), discrete.end())));

BIT bit = BIT();
bit.init();
int ret = 0;
for (int i = 0; i < (int)nums.size(); i++) {
long long a = lower_bound(discrete.begin(), discrete.end(), nums[i]) - discrete.begin() + 1;
long long a2 = lower_bound(discrete.begin(), discrete.end(), nums[i] * 2LL) - discrete.begin() + 1;
ret += bit.sum(MAX_N - 1) - bit.sum(a2);