# Using Segment Tree data structure[CPP].

• I think this problem is much more simple when using BST or MergeSort rather than Segment Tree.

Anyway, here it is.

``````/*
Segment Tree version.
*/

class Solution {
public:
vector<int> countSmaller(vector<int>& nums)
{
std::vector<int> ans(nums.size(), 0);
if (nums.size() == 0)
return ans;

int maxVal = numeric_limits<int>::min();
int minVal = numeric_limits<int>::max();
for (int i = 0; i < nums.size(); ++i)
{
maxVal = max(maxVal, nums[i]);
minVal = min(minVal, nums[i]);
}

sgmTree = new SegmentTreeNode[4 * (maxVal - minVal + 1)];
buildSegmentTree(1, minVal, maxVal);

for (int i = nums.size() - 1; i >= 0; --i)
ans[i] = insert(1, nums[i]);

return ans;
}

private:
class SegmentTreeNode
{
public:
int left, right;
int value; // number of x, where  left <= x < right.
int rightBoundaryCnt;// number of x where x == right.
int delayMarkCnt;

SegmentTreeNode() { left = right = value = delayMarkCnt = rightBoundaryCnt = 0; }
};

SegmentTreeNode *sgmTree;

void buildSegmentTree(int root, int from, int to)
{
// deal with the situation like: [form,to] is [-3, -2] or [-1, 0]
if (from < 0 && (to - from) == 1)
{
sgmTree[root].left = from;
sgmTree[root].right = to;
sgmTree[root * 2].left = sgmTree[root * 2].right = from;
sgmTree[root * 2 + 1].left = sgmTree[root * 2 + 1].right = to;
return;
}

if (from == to)
{
sgmTree[root].left = sgmTree[root].right = from;
return;
}

int mid = (from + to) / 2;
// left child
buildSegmentTree(root * 2, from, mid);
// right child
buildSegmentTree(root * 2 + 1, mid + 1, to);
sgmTree[root].left = from;
sgmTree[root].right = to;
}

int insert(int root, int value)
{
if (sgmTree[root].right == value)
{
sgmTree[root].rightBoundaryCnt++;
return sgmTree[root].value;
}

int mid = (sgmTree[root].left + sgmTree[root].right) / 2;
if (value <= mid)
{
int cnt = insert(root * 2, value);
//	  [left, right) = [left, mid) + [mid, mid] + [mid, right);
sgmTree[root].value = (sgmTree[root * 2].value + sgmTree[root * 2].rightBoundaryCnt) + (sgmTree[root * 2 + 1].value);
return cnt;
}
else
{
int cnt = insert(root * 2 + 1, value);

sgmTree[root].value = (sgmTree[root * 2].value + sgmTree[root * 2].rightBoundaryCnt) + (sgmTree[root * 2 + 1].value);
return sgmTree[root * 2].value + sgmTree[root * 2].rightBoundaryCnt + cnt;
}
}
};``````

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