Java | Segment Tree | TreeSet
Complexity\n- Time complexity: $\mathcal{O}((n + q)\times\log{N})$\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(n)\n Add your space comp
# Complexity\n- Time complexity: $\\mathcal{O}((n + q)\\times\\log{N})$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int[] maximumSumQueries(int[] a1, int[] a2, int[][] queries) {\n        int n = a1.length;\n        int a[][] = new int[n][2];\n        for(int i = 0; i < n; i++){\n            a[i][0] = a1[i];\n            a[i][1] = a2[i];\n        }\n        Arrays.sort(a2);\n        hm = new TreeMap<>();\n        int k = 0;\n        for(int i = 0; i < n; i++)\n            if(!hm.containsKey(a2[i]))\n                hm.put(a2[i], k++);\n        \n        Arrays.sort(a, \n            new Comparator<int[]>(){\n                public int compare(int x[], int y[]){\n                    return x[0] - y[0];\n                }\n            }\n        );\n        \n        for(int i = 0; i < queries.length; i++){\n            queries[i] = new int[]{queries[i][0], queries[i][1], i};\n        }\n        Arrays.sort(queries,\n            new Comparator<int[]>(){\n                public int compare(int x[], int y[]){\n                    return -x[0] + y[0];\n                }\n            }\n        );\n        int max = 0;\n        int ans[] = new int[queries.length];\n        int j = 0;\n        int i = a.length - 1;\n        \n        seg = new int[4 * hm.size() + 4];\n        Arrays.fill(seg, -1);\n        while(j < queries.length){\n            while(i > -1 && a[i][0] >= queries[j][0]){\n                update(0, hm.size() - 1, hm.get(a[i][1]), a[i][0] + a[i][1], 0);\n                i--;\n            }\n            \n            if(hm.ceilingKey(queries[j][1]) == null){\n                ans[queries[j][2]] = -1;\n            } else{\n                ans[queries[j][2]] = find(0, hm.size() - 1, hm.ceilingEntry(queries[j][1]).getValue(), hm.size() - 1, 0);\n            }\n            j++;\n        }\n        while(j < queries.length)\n            ans[queries[j++][2]] = -1;\n        return ans;\n    }\n    private void update(int low, int high, int ind, int val, int node){\n        if(low == high){\n            seg[node] = Math.max(seg[node], val);\n            return;\n        }\n        int mid = (low + high) >> 1;\n        if(ind <= mid)\n            update(low, mid, ind, val, 2 * node + 1);\n        else\n            update(mid + 1, high, ind, val, 2 * node + 2);\n        seg[node] = Math.max(seg[2 * node + 1], seg[2 * node + 2]);\n    }\n    private int find(int low, int high, int l, int r, int node){\n        if(low > r || high < l)\n            return -1;\n        if(low >= l && high <= r)\n            return seg[node];\n        int mid = (low + high) >> 1;\n        return Math.max(find(low, mid, l, r, 2 * node + 1), find(mid + 1, high, l, r, 2 * node + 2));\n    }\n    private int seg[];\n    private TreeMap<Integer, Integer> hm;\n}\n```
['Java']