[C++] Explanation of Sorting, Segment Tree, Mapping solution
Rectangles sorting\n1. This question type of reducing from 2 dimensions to 1, reminds me of the russian doll envelope question. https://leetcode.com/problems/ru
**Rectangles sorting**\n1. This question type of reducing from 2 dimensions to 1, reminds me of the russian doll envelope question. https://leetcode.com/problems/russian-doll-envelopes/ \n2. If you imagine it as a rectange with width and height, you are trying to find the largest perimeter rectangle where your query rectangle fits within it.\n3. Therefore, I include the queries with the original rectangles. **Sort it in ascending order of width and then height, and then based on whether it is a query(queries should be sorted last)**. Therefore, when I loop through and reach a query, I am assured that the rectangles that fit the criteria have already been processed. I mark the query with the index and mark the original rectangle with -1.\n\n**Segment Tree**\n\n4. However, of the already processed rectangles, some of them have heights that do not fit the criteria of the query. And of those rectangles who do fit the criteria, you cannot just take the rectangle with the largest height. As there might be a rectangle with a smaller height, but larger width such that the perimeter is larger.\n5. Therefore you must use a segment tree where **index is the height, and the value is the perimeter.**\n6. However, since the possible values of height is 10^9, it will exceed space limitation for segment tree.\n\n**Index Compression**\n\n7. Therefore, you must use a **mapping of height to index**, so as to compress the space. For example, if your heights are [4, 7, 10, 14], you will need an array of `4 * 15` size to represent this in a segment tree. But if you map them to [0, 1, 2, 3], you only need `4 * 4` size. Therefore, instead of 10^9, you can reduce it to 10^5.\n8. For each query, just query the segment tree for the largest perimeter that has index(height) above your criteria.\n9. Note: when you update the segment tree, you might accidentally override the old value with a smaller value. Therefore, I used `tree[x] = max(tree[x], v);` within the update member function.\n\n```\nstruct SegmentTree {\n    vector<int> tree;\n    int size;\n    \n    SegmentTree(int n) {\n        size = 1;\n        while (size < n) size *= 2;\n        tree.assign(2*size - 1, INT_MIN);\n    }\n\n    void build(vector<int>& a, int x, int lx, int rx) {\n        if (rx - lx == 1) {\n            if (lx < a.size()) tree[x] = a[lx];\n            return;\n        }\n        int m = lx + (rx - lx) / 2;\n        build(a, 2*x + 1, lx, m);\n        build(a, 2*x + 2, m, rx);\n        tree[x] = max(tree[2*x + 1], tree[2*x + 2]);\n    }\n\n    void build(vector<int>& a) {\n        build(a, 0, 0, size);\n    }\n\n    int query(int l, int r, int x, int lx, int rx) {\n        if (lx >= r || l >= rx) return INT_MIN;\n        if (lx >= l && rx <= r) return tree[x];\n        int m = lx + (rx - lx) / 2;\n        int leftMax = query(l, r, 2*x + 1, lx, m);\n        int rightMax = query(l, r, 2*x + 2, m, rx);\n        return max(leftMax, rightMax);\n    }\n\n    int query(int l, int r) {\n        return query(l, r, 0, 0, size);\n    }\n    \n    void update(int i, int v, int x, int lx, int rx) {\n        if (rx - lx == 1) {\n            tree[x] = max(tree[x], v);\n            return;\n        }\n        int m = lx + (rx - lx) / 2;\n        if (i < m) {\n            update(i, v, 2*x + 1, lx, m);\n        } else {\n            update(i, v, 2*x + 2, m, rx);\n        }\n        tree[x] = max(tree[2*x + 1], tree[2*x + 2]);\n    }\n\n    void update(int i, int v) {\n        update(i, v, 0, 0, size);\n    }\n};\n\nclass Solution {\npublic:\n\t// sort by width, followed by height, followed by data vs. query\n    static bool comp(vector<int> &a, vector<int> &b){\n        if(a[0]==b[0]){\n            if (a[1] == b[1]) {\n                return a[2] > b[2];\n            }\n            return a[1]<b[1];\n        }\n        return a[0]<b[0];\n    }\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        vector<vector<int>> envelopes;\n        \n        set<int> rv;\n\t\t// insert both data and query into envelopes array\n\t\t// remember to store their heights in an ordered set for mapping\n        for (int i = 0; i < nums1.size(); ++i) {\n            envelopes.push_back({nums1[i], nums2[i], -1});\n            rv.insert(nums2[i]);\n        }\n        for (int i = 0; i < queries.size(); ++i) {\n            envelopes.push_back({queries[i][0], queries[i][1], i});\n            rv.insert(queries[i][1]);\n        }       \n        sort(envelopes.begin(), envelopes.end(), comp);\n        reverse(envelopes.begin(), envelopes.end());\n        \n\t\t// generate the mapping for height to index\n        unordered_map<int, int> mapping;\n        int counter = 0;\n        for (auto e: rv) {\n            mapping[e] = counter;\n            counter++;\n        }\n        \n\t\t// create a segment tree with the size of set of heights\n        SegmentTree st(counter);\n        vector<int> ans(queries.size());\n        for (auto envelope: envelopes) {\n            if (envelope[2] != -1) {\n\t\t\t\t// if it is a query, check the segment tree\n                int val = st.query(mapping[envelope[1]], counter);\n                ans[envelope[2]] = val == INT_MIN ? -1 : val;\n            } else {\n\t\t\t    // if it is data, insert into the segment tree\n                st.update(mapping[envelope[1]], envelope[0] + envelope[1]);\n            } \n        }\n        \n        return ans;\n    }\n};\n```
['Tree', 'Sorting']