Merge Sort Tree || C++ || Advanced Data Structure 🌳
Approach\nBasically I need to firstly encounter with x so for that I make an vector of pair and I sorted W.R.T to first element and now I will know my range by 
# Approach\nBasically I need to firstly encounter with x so for that I make an vector of pair and I sorted W.R.T to **first element** and now I will know my range by just doing binary search on x.\nNow main issue is how will I find my nums2[j] which are >= y for that I used the **merge sort tree**.\nYou can learn more on gfg.\nLink:- https://www.geeksforgeeks.org/merge-sort-tree-smaller-or-equal-elements-in-given-row-range/\nAlso qlogn solutions are present :\') I just had no idea how to solve in that time complexity so I done with this.\n\n# Complexity\n- Time complexity:\nO(q * (logn)^2)\n\n# Code\n```\nclass Solution {\npublic:\n\tclass Merge_seg{\n\t\tprivate:\n\t\t\tvector<vector<int>> M;\n\t\t\tvector<vector<pair<int, int>>> seg;\n\t\tpublic:\n\t\t\tMerge_seg(int n) {\n\t\t\t\tM.resize(4 * n);\n\t\t\t\tseg.resize(4 * n);\n\t\t\t}\n\t\t\tint find(int num, vector<pair<int, int>>& A) {\n\t\t\t\tint l = 0, h = (int) A.size() - 1;\n\t\t\t\tint index = -1;\n\t\t\t\twhile(l <= h) {\n\t\t\t\t\tint mid = (l + h) >> 1;\n\t\t\t\t\tif(A[mid].first >= num) {\n\t\t\t\t\t\tindex = mid;\n\t\t\t\t\t\th = mid - 1;\n\t\t\t\t\t}\n\t\t\t\t\telse {\n\t\t\t\t\t\tl = mid + 1;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\treturn index;\n\t\t\t}\n\t\t\tvoid build(int ind, int st, int en, vector<pair<int, int>>& A) {\n\t\t\t\tif(st == en) {\n\t\t\t\t\tseg[ind].push_back(A[st]);\n\t\t\t\t\tM[ind].push_back(A[st].first + A[st].second);\n\t\t\t\t\treturn;\n\t\t\t\t}\n\t\t\t\tint mid = (st + en) >> 1;\n\t\t\t\tbuild(2 * ind + 1, st, mid, A);\n\t\t\t\tbuild(2 * ind + 2, mid + 1, en, A);\n\t\t\t\tM[ind].resize((int) seg[2 * ind + 1].size() + (int) seg[2 * ind + 2].size());\n\t\t\t\tseg[ind].resize((int) seg[2 * ind + 1].size() + (int) seg[2 * ind + 2].size());\n\t\t\t\tmerge(seg[2 * ind + 1].begin(), seg[2 * ind + 1].end(), seg[2 * ind + 2].begin(), seg[2 * ind + 2].end(), seg[ind].begin());\n\t\t\t\tint mx = 0;\n\t\t\t\tfor(int i = (int) seg[ind].size() - 1; i >= 0; i--) {\n\t\t\t\t\tmx = max(mx, seg[ind][i].first + seg[ind][i].second);\n\t\t\t\t\tM[ind][i] = mx;\n\t\t\t\t}\n\t\t\t}\n\t\t\tint ask(int ind, int st, int en, int L, int R, int limit) {\n\t\t\t\tif(st > R || en < L || st > en) {\n\t\t\t\t\treturn -1;\n\t\t\t\t}\n\t\t\t\tif(st >= L && en <= R) {\n\t\t\t\t\tint index = find(limit, seg[ind]);\n\t\t\t\t\tif(index == -1) {\n\t\t\t\t\t\treturn -1;\n\t\t\t\t\t}\n\t\t\t\t\treturn M[ind][index];\n\t\t\t\t}\n\t\t\t\tint mid = (st + en) >> 1;\n\t\t\t\treturn max(ask(2 * ind + 1, st, mid, L, R, limit), ask(2 * ind + 2, mid + 1, en, L, R, limit));\n\t\t\t}\n\t};\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n\t\tint n = nums1.size();\n\t\tvector<pair<int, int>> vec;\n\t\tfor(int i = 0; i < n; i++) {\n\t\t\tvec.push_back({nums1[i], nums2[i]});\n\t\t}\n\t\tsort(vec.begin(), vec.end());\n\t\tfor(int i = 0; i < n; i++) {\n\t\t\tswap(vec[i].first, vec[i].second);\n\t\t}\n\t\tMerge_seg S(n);\n\t\tS.build(0, 0, n - 1, vec);\n\t\tfor(int i = 0; i < n; i++) {\n\t\t\tswap(vec[i].first, vec[i].second);\n\t\t}\n\t\tvector<int> ans;\n\t\tfor(auto& q : queries) {\n\t\t\tint x = q[0];\n\t\t\tint y = q[1];\n\t\t\tint index = -1;\n\t\t\tint l = 0, h = n - 1;\n\t\t\twhile(l <= h) {\n\t\t\t\tint mid = (l + h) >> 1;\n\t\t\t\tif(vec[mid].first >= x) {\n\t\t\t\t\tindex = mid;\n\t\t\t\t\th = mid - 1;\n\t\t\t\t}\n\t\t\t\telse {\n\t\t\t\t\tl = mid + 1;\n\t\t\t\t}\n\t\t\t}\n\t\t\tif(index == -1) {\n\t\t\t\tans.push_back(index);\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tans.push_back(S.ask(0, 0, n - 1, index, n - 1, y));\n\t\t}\n\t\treturn ans;\n    }\n};\n\n```
['Segment Tree', 'Merge Sort', 'C++']