Using Segment Tree data structure[CPP].


  • 0
    E

    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;
    	}
    }
    };

Log in to reply
 

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