[JAVA]: Segment tree
\nclass Node {\n    int start, end;\n    int val;\n    Node left;\n    Node right;\n    public Node(int start, int end) {\n        this.start = start;\n        
```\nclass Node {\n    int start, end;\n    int val;\n    Node left;\n    Node right;\n    public Node(int start, int end) {\n        this.start = start;\n        this.end = end;\n        this.val = Integer.MIN_VALUE;\n    }\n}\n\nclass SegmentTree {\n    private Node root;\n    public SegmentTree() {\n        this.root = new Node(1, 1000000000);\n    }\n    \n    public void pointUpdate(int point, int val) {\n        this.pointUpdateHelper(this.root, 1, 1000000000, point, val);\n    }\n    \n    // finds range max for point >= left\n    public int rangeMax(int left) {\n        return this.rangeMaxHelper(this.root, 1, 1000000000, left, 1000000000);\n    }\n    \n    private void pointUpdateHelper(Node curr, int left, int right, int point, int val) {\n        if(left == right && left == point) {\n            curr.val = Math.max(curr.val, val);\n            return;\n        }\n        \n        if(point < left || point > right)\n            return;\n        \n        int mid = (left + right)/2;\n        Node leftC = getOrCreateLeftChild(curr, left, mid);\n        Node rightC = getOrCreateRightChild(curr, mid + 1, right);\n        pointUpdateHelper(leftC, left, mid, point, val);\n        pointUpdateHelper(rightC, mid + 1, right, point, val);\n        curr.val = Math.max(leftC.val, rightC.val);\n        return;\n    }\n    \n    private int rangeMaxHelper(Node curr, int left, int right, int l, int r) {\n        if(l > right || left > r)\n            return Integer.MIN_VALUE;\n        \n        if(left >= l && right <= r)\n            return curr.val;\n        \n        int mid = (left + right)/2;\n        Node leftC = getOrCreateLeftChild(curr, left, mid);\n        Node rightC = getOrCreateRightChild(curr, mid + 1, right);\n        return Math.max(rangeMaxHelper(leftC, left, mid, l, r), rangeMaxHelper(rightC, mid + 1, right, l, r));\n    }\n    \n    private Node getOrCreateLeftChild(Node curr, int start, int end) {\n        if(curr.left != null)\n            return curr.left;\n        \n        curr.left = new Node(start, end);\n        return curr.left;\n    }\n    \n    private Node getOrCreateRightChild(Node curr, int start, int end) {\n        if(curr.right != null)\n            return curr.right;\n        \n        curr.right = new Node(start, end);\n        return curr.right;\n    }\n}\n\nclass Solution {\n    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {\n        int n = nums1.length;\n        int m = queries.length;\n        int res[] = new int[m];\n        int q[][] = new int[m][3];\n        int tuples[][] = new int[n][2];\n        \n        for(int i = 0; i<m; i++) {\n            q[i][0] = queries[i][0];\n            q[i][1] = queries[i][1];\n            q[i][2] = i;\n        }\n        \n        for(int i = 0; i<n; i++) {\n            tuples[i][0] = nums1[i];\n            tuples[i][1] = nums2[i];\n        }\n        \n        Arrays.sort(q, (a,b) -> a[0] - b[0]);\n        Arrays.sort(tuples, (a,b) -> a[0] - b[0]);\n        \n        // Segment tree for range max\n        SegmentTree seg = new SegmentTree();\n        \n        int i = n-1, j = m-1;\n        while(j >= 0) {\n            while(i >= 0 && tuples[i][0] >= q[j][0]) {\n                seg.pointUpdate(tuples[i][1], tuples[i][0] + tuples[i][1]);\n                i--;\n            } \n            \n            int max = seg.rangeMax(q[j][1]);\n            max = max == Integer.MIN_VALUE? -1: max;\n            res[q[j][2]] = max;\n            j--;\n        }\n        \n        return res;\n    }\n}\n```
[]