# Segment Tree

1. Sort nums and map them to their id. So large id represents large number.
2. Build a segment tree from 0 to max id. Segment tree is used for counting sum of interval in O(logn).
3. for num from right to left:
count sum of [0, id - 1].
insert number.
``````class Solution {
public:
struct node
{
int l,r,n;
}tree[50005<<2];
void build(int l, int r, int now)
{
tree[now].l = l;
tree[now].r = r;
tree[now].n = 0;
if(l == r) return ;
int mid = (l + r) >> 1;
build(l, mid, now << 1);
build(mid + 1, r, now << 1 | 1);
}
void insert(int id, int now)
{
tree[now].n++;
if(tree[now].l == tree[now].r) return ;
int mid = (tree[now].l + tree[now].r) >> 1;
if(id <= mid) insert(id, now << 1);
else insert(id, now << 1 | 1);
}
int query(int l, int r, int now)
{
if(tree[now].l == l && tree[now].r == r) return tree[now].n;
int mid = (tree[now].l + tree[now].r) >> 1;
if(l > mid) return query(l, r, now << 1 | 1);
else if(r <= mid) return query(l, r, now << 1);
else return query(l, mid, now << 1) + query(mid + 1, r, now <<1 | 1);
}
vector<int> countSmaller(vector<int>& nums)
{
vector<int> sorted = nums;
sort(sorted.begin(), sorted.end());
unordered_map<int, int> mp;
for(int i = 0; i < sorted.size(); i++) mp[sorted[i]] = i + 1;
build(0, sorted.size(), 1);
for(int i = nums.size() - 1; i >= 0; i--)
{
int id = mp[nums[i]];
nums[i] = query(0, id - 1, 1);
insert(id, 1);
}
return nums;
}
};
``````

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