# Clean C++ Solutions using Segment Tree and Discretization

• ``````#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
class Solution {
public:
int reversePairs(vector<int>& nums) {

if (nums.size() < 2) return 0;

set<long long> s;
for (int num : nums) {
s.insert(num);
s.insert(num * 2L + 1);
}
unordered_map<long long, int> idxs;

// discretization
int n = 0;
for (long long num : s) {
idxs[num] = n++;
}

vector<long long> sums(n << 2);
build(sums, 0, n - 1, 1);

int res = 0;
for (int num : nums) {

int idx = idxs[num * 2L + 1];
res += query(sums, idx, n - 1, 0, n - 1, 1);
update(sums, idxs[num], 0, n - 1, 1);
}
return res;
}

void build(vector<long long>& sums, int l, int r, int rt) {
sums[rt] = 0;
if (l == r) return;
int m = (l + r) >> 1;
build(sums, lson);
build(sums, rson);
}

void pushUp(vector<long long>& sums, int rt) {
sums[rt] = sums[rt << 1] + sums[rt << 1 | 1];
}

void update(vector<long long>& sums, int idx, int l, int r, int rt) {
if (l == r) {
sums[rt]++;
return;
}
int m = (l + r) >> 1;
if (idx <= m) update(sums, idx, lson);
else update(sums, idx, rson);
pushUp(sums, rt);
}

int query(vector<long long>& sums, int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) return sums[rt];
int m = (l + r) >> 1;
int ret = 0;
if (L <= m) ret += query(sums, L, R, lson);
if (R > m) ret += query(sums, L, R, rson);
return ret;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.