## Approach 1: Fenwick Tree

• Time:O(n\log n)
• Space:O(n)

## C++

``````class FenwickTree {
public:
FenwickTree(int n) : sums(n + 1) {}

void update(int i, int delta) {
while (i < sums.size()) {
sums[i] += delta;
i += lowbit(i);
}
}

int get(int i) const {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowbit(i);
}
return sum;
}

private:
vector<int> sums;

static inline int lowbit(int i) {
return i & -i;
}
};

class Solution {
public:
int reversePairs(vector<int>& nums) {
int ans = 0;
unordered_map<long, int> ranks;
getRanks(nums, ranks);
FenwickTree tree(ranks.size());

for (int i = nums.size() - 1; i >= 0; --i) {
const long num = nums[i];
ans += tree.get(ranks[num] - 1);
tree.update(ranks[num * 2], 1);
}

return ans;
}

private:
void getRanks(const vector<int>& nums, unordered_map<long, int>& ranks) {
set<long> sorted(begin(nums), end(nums));
for (const long num : nums)
sorted.insert(num * 2);
int rank = 0;
for (const long num : sorted)
ranks[num] = ++rank;
}
};
``````

## Approach 2: Segment Tree

• Time:O(n\log n)
• Space:O(n)

## C++

``````struct SegmentTreeNode {
int lo;
int hi;
int sum;
SegmentTreeNode* left;
SegmentTreeNode* right;
SegmentTreeNode(int lo, int hi, int sum, SegmentTreeNode* left = nullptr,
SegmentTreeNode* right = nullptr)
: lo(lo), hi(hi), sum(sum), left(left), right(right) {}
~SegmentTreeNode() {
delete left;
delete right;
left = nullptr;
right = nullptr;
}
};

class SegmentTree {
public:
SegmentTree(const vector<int>& nums)
: root(build(nums, 0, nums.size() - 1)) {}

void update(int i, int val) {
update(root.get(), i, val);
}

int sumRange(int i, int j) const {
return sumRange(root.get(), i, j);
}

private:
std::unique_ptr<SegmentTreeNode> root;

SegmentTreeNode* build(const vector<int>& nums, int lo, int hi) const {
if (lo == hi)
return new SegmentTreeNode(lo, hi, nums[lo]);
const int mid = (lo + hi) / 2;
auto left = build(nums, lo, mid);
auto right = build(nums, mid + 1, hi);
return new SegmentTreeNode(lo, hi, left->sum + right->sum, left, right);
}

void update(SegmentTreeNode* root, int i, int val) {
if (root->lo == i && root->hi == i) {
root->sum += val;
return;
}
const int mid = (root->lo + root->hi) / 2;
if (i <= mid)
update(root->left, i, val);
else
update(root->right, i, val);
root->sum = root->left->sum + root->right->sum;
}

int sumRange(SegmentTreeNode* root, int i, int j) const {
if (root->lo == i && root->hi == j)
return root->sum;
const int mid = (root->lo + root->hi) / 2;
if (j <= mid)
return sumRange(root->left, i, j);
if (i > mid)
return sumRange(root->right, i, j);
return sumRange(root->left, i, mid) + sumRange(root->right, mid + 1, j);
}
};

class Solution {
public:
int reversePairs(vector<int>& nums) {
int ans = 0;
unordered_map<long, int> ranks;
getRanks(nums, ranks);
SegmentTree tree(vector<int>(ranks.size() + 1));

for (int i = nums.size() - 1; i >= 0; --i) {
const long num = nums[i];
ans += tree.sumRange(0, ranks[num] - 1);
tree.update(ranks[num * 2], 1);
}

return ans;
}

private:
void getRanks(const vector<int>& nums, unordered_map<long, int>& ranks) {
set<long> sorted(begin(nums), end(nums));
for (const long num : nums)
sorted.insert(num * 2);
int rank = 0;
for (const long num : sorted)
ranks[num] = ++rank;
}
};
``````

## Approach 3: Merge Sort

• Time:O(n\log n)
• Space:O(n)

## C++

``````class Solution {
public:
int reversePairs(vector<int>& nums) {
int ans = 0;
mergeSort(nums, 0, nums.size() - 1, ans);
return ans;
}

private:
void mergeSort(vector<int>& nums, int l, int r, int& ans) {
if (l >= r)
return;

const int m = (l + r) / 2;
mergeSort(nums, l, m, ans);
mergeSort(nums, m + 1, r, ans);
merge(nums, l, m, r, ans);
}

void merge(vector<int>& nums, int l, int m, int r, int& ans) {
const int lo = m + 1;
int hi = m + 1;  // 1st index s.t. nums[i] <= 2 * nums[lo]

// for each index i in range [l, m], add hi - lo to ans
for (int i = l; i <= m; ++i) {
while (hi <= r && nums[i] > 2L * nums[hi])
++hi;
ans += hi - lo;
}

vector<int> sorted(r - l + 1);
int k = 0;      // sorted's index
int i = l;      // left's index
int j = m + 1;  // right's index

while (i <= m && j <= r)
if (nums[i] < nums[j])
sorted[k++] = nums[i++];
else
sorted[k++] = nums[j++];

// put possible remaining left part to the sorted array
while (i <= m)
sorted[k++] = nums[i++];

// put possible remaining right part to the sorted array
while (j <= r)
sorted[k++] = nums[j++];

copy(begin(sorted), end(sorted), begin(nums) + l);
}
};
``````