Need help! and Accept solution. C++ Using Segment Tree


  • 0
    L

    The idea is simple, I transform this problem to count of smaller numbers before self with positive integer.

    Also I am asking for help to use bind to pass multiple parameters functions to transform, which I commented out because of compiler error. I really appreciated if you can help me with this.

    struct SegmentTreeNode {
            int start;
            int end;
            int count;
            SegmentTreeNode *left, *right;
            SegmentTreeNode(int s, int e) : start(s), end(e), count(0), left(nullptr), right(nullptr) {}
        };
    
    
    vector<int> countSmaller(vector<int>& nums) {
         // write your code here
        vector<int> res;
        if (nums.empty()) return res;
        reverse(nums.begin(), nums.end());
        int minv = *min_element(nums.begin(), nums.end());
        //if (minv < 0) transform(nums.begin(), nums.end(), [this](int i) {return i++; });
        for (auto &num : nums) num += abs(minv);
        int maxv = *max_element(nums.begin(), nums.end());
        
        SegmentTreeNode *root = build(0, maxv);
        for (auto item : nums) {
            int cnt = query(root, 0, item);
            res.emplace_back(cnt);
            update(root, item);
        }
        reverse(res.begin(), res.end());
        cout << "res is " << res.size() << endl;
        return res;
    }
    
     SegmentTreeNode *build(int start, int end) {
        if (start > end)
            return nullptr;
        if (start == end)
            return new SegmentTreeNode(start, end);
        int mid = start + ((end - start) >> 1);
        SegmentTreeNode *root = new SegmentTreeNode(start, end);
        root->left = build(start, mid);
        root->right = build(mid + 1, end);
        return root;
    }
    
    int query(SegmentTreeNode *root, int start, int end) {
        if (!root || start > root->end || end < root->start)
            return 0;
        if (start <= root->start && end > root->end)
            return root->count;
        return query(root->left, start, end) + query(root->right, start, end);
    }
    
    void update(SegmentTreeNode *root, int item) {
        if (root == nullptr) return;
        if (root->start == item && root->end == item) {
            // there could have duplicate items.
            root->count += 1;
            return;
        } else if (item >= root->start && item <= root->end) {
            update(root->left, item);
            update(root->right, item);
            root->count = root->left->count + root->right->count;
        }
    }

Log in to reply
 

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