Segment Tree Solution in JAVA
\n# Complexity\n- Time complexity: O(Qlog(N + Q) + N * logN)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(N+Q)\n Add your space complexi
\n# Complexity\n- Time complexity: O(Qlog(N + Q) + N * logN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N+Q)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nclass Solution {\n\n    void propagate(int cur, int res, int[] segmentTree, int start, int end, int value){\n        \n        if (start == end){\n            segmentTree[cur] = Math.max(segmentTree[cur], value);\n            return;\n        }else{\n            int mid = (start + end)/2;\n            if (mid >= res){\n                propagate(cur * 2, res, segmentTree, start, mid, value);\n            }else{\n                propagate(cur * 2+1, res, segmentTree, mid+1, end, value);\n            }\n            segmentTree[cur] = Math.max(segmentTree[cur*2], segmentTree[cur*2+1]);\n        }\n        \n    }\n    int getQuery(int cur, int[] segmentTree, int start, int end, int l, int r){\n        if (start > end){\n            return -1;\n        }\n        if (start == l && end == r){\n            return segmentTree[cur];\n        }\n        int mid = (l + r)/2;\n\n        return Math.max(getQuery(cur * 2, segmentTree, start, Math.min(mid, end), l, mid),\n                getQuery(cur * 2 + 1, segmentTree, Math.max(mid+1, start), end, mid+1, r));\n\n    }\n    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {\n        int n = nums1.length;\n        int[][] arr = new int[n][2];\n\n        int q = queries.length;\n        int[][] procesedQueries = new int[q][3];\n\n        Set<Integer> points = new TreeSet<>();\n        for (int i=0; i<nums1.length; i++){\n            arr[i][0] = nums1[i];\n            arr[i][1] = nums2[i];\n            points.add(arr[i][1]);\n        }\n        Arrays.sort(arr, (a, b) -> b[0] - a[0]);\n\n        for (int i=0; i<queries.length; i++){\n            procesedQueries[i][0] = queries[i][0];\n            procesedQueries[i][1] = queries[i][1];\n            points.add(procesedQueries[i][1]);\n            procesedQueries[i][2] = i;\n        }\n        int start = 0;\n        Map<Integer, Integer> hash = new HashMap<>();\n        for (int a : points){\n            hash.put(a, start);\n            start++;\n        }\n        int limit = (int)Math.ceil((double)(Math.log(start) / Math.log(2)));\n        int range = (1 << (limit));\n        int[] segmentTree = new int[range * 2 + 4];\n        Arrays.fill(segmentTree, -1);\n        Arrays.sort(procesedQueries, (a, b) -> b[0] - a[0]);\n        int j = 0;\n        int[] answer = new int[q];\n        for (int i=0; i<procesedQueries.length; i++){\n            while(j < arr.length && arr[j][0] >= procesedQueries[i][0]){\n                int res = hash.get(arr[j][1]);\n            \n                propagate(1, res, segmentTree, 0, range - 1, arr[j][0] + arr[j][1]);\n              \n                j++;\n            }\n            int ans = getQuery(1, segmentTree, hash.get(procesedQueries[i][1]), range - 1, 0, range-1);\n            answer[procesedQueries[i][2]] = ans;\n        }\n        return answer;\n    }\n}\n\n\n\n\n\n```
['Segment Tree', 'Java']