Persistent index tree
Intuition\nwe have points in space (x=nums1[i] and y=nums2[i]) with value x+y and need to query the maximum value for all points in x>=q[0] and y >= q[1].\n\n# 
# Intuition\nwe have points in space (x=nums1[i] and y=nums2[i]) with value x+y and need to query the maximum value for all points in x>=q[0] and y >= q[1].\n\n# Approach\nsort the points by x\ncompress the y coordinates, so we can use index tree\niterate the sorted points from back the to front, for each point add the y coordinate with value x+y to the index tree of the next point\nhaving index tree for each point uses too much memory, so use persistent index tree where it creates a new tree for each add that has new nodes along the path that changes and points to the nodes of the old tree otherwise\nfor each query do binary search to find the first point i in the sorted order with x>=q[0]\ndo binary search to find the y\' within the compressed y coordinates\nquery index tree i for max value for interval y\', n\n\n# Complexity**Bold**\n- Time complexity:\nn*logn\n\n- Space complexity:\nn*logn\n\n# Code\n```\nimport "math"\n\ntype node struct {\n\tv     int\n\tleft  *node\n\tright *node\n}\n\ntype indexTree struct {\n\tn            int\n\troot         *node\n\tf            func(i, j int) int\n\tdefaultValue int\n}\n\ntype Aggregation interface {\n\tDefaultValue() int\n\tAggregate(left, right int) int\n}\n\nfunc (m MinIndex) DefaultValue() int { return math.MaxInt32 }\nfunc (m MinIndex) Aggregate(left, right int) int {\n\tif left < right {\n\t\treturn left\n\t} else {\n\t\treturn right\n\t}\n}\n\nfunc (m MaxIndex) DefaultValue() int { return -1 }\nfunc (m MaxIndex) Aggregate(left, right int) int {\n\tif left > right {\n\t\treturn left\n\t} else {\n\t\treturn right\n\t}\n}\n\nfunc (m SumIndex) DefaultValue() int             { return 0 }\nfunc (m SumIndex) Aggregate(left, right int) int { return left + right }\n\nfunc (i *indexTree) Add(k, v int) IndexTree {\n\tnewRoot := i.traverse(i.root, 0, i.n, true, func(cur *node, b, e int) *node {\n\t\tif b <= k && e >= k {\n\t\t\tnext := &node{0, nil, nil}\n\t\t\tnext.v = i.f(cur.v, v)\n\t\t\treturn next\n\t\t}\n\t\treturn nil\n\t})\n\n\treturn &indexTree{i.n, newRoot, i.f, i.defaultValue}\n}\n\nfunc (i *indexTree) Get(qb, qe int) int {\n\tres := i.defaultValue\n\ti.traverse(i.root, 0, i.n, false, func(cur *node, b, e int) *node {\n\t\tif b >= qb && e <= qe {\n\t\t\tres = i.f(res, cur.v)\n\t\t\treturn nil\n\t\t}\n\t\tif !(qe < b || qb > e) {\n\t\t\treturn &node{0, nil, nil}\n\t\t} else {\n\t\t\treturn nil\n\t\t}\n\t})\n\treturn res\n}\n\nfunc (i *indexTree) traverse(cur *node, b, e int, add bool, do func(node *node, b, e int) *node) *node {\n\tx := do(cur, b, e)\n\n\tif x == nil {\n\t\treturn cur\n\t}\n    \n    if cur.left == nil {\n        cur.left = &node{i.defaultValue, nil, nil}\n    }\n    if cur.right == nil {\n        cur.right = &node{i.defaultValue, nil, nil }\n    }\n    \n    x.left = cur.left\n\tx.right = cur.right\n\n\tm := (b + e) / 2\n\n\tif b != e {\n\t\tx.left = i.traverse(cur.left, b, m, add, do)\n\t\tx.right = i.traverse(cur.right, m+1, e, add, do)\n\t}\n\n\treturn x\n}\n\n// Aggregation types\ntype MinIndex struct{}\ntype MaxIndex struct{}\ntype SumIndex struct{}\n\ntype IndexTree interface {\n\t// Adds v to index i\n\tAdd(i, v int) IndexTree\n\t// Gets the aggregation in the interval [b, e]\n\tGet(b, e int) int\n}\n\nfunc NewIndexTree(n int, a Aggregation) IndexTree {\n\troot := &node{a.DefaultValue(), nil, nil}\n\n\treturn &indexTree{n, root, a.Aggregate, a.DefaultValue()}\n}\n\ntype p struct {\n    x, y int\n}\n\nfunc compress(arr []int) map[int]int {\n    sort.Ints(arr)\n    \n    res := make(map[int]int)\n    for i, v := range arr {\n        res[v] = i\n    }\n    \n    return res\n}\n\nfunc maximumSumQueries(nums1 []int, nums2 []int, queries [][]int) []int {\n    n := len(nums1)\n    arr := make([]p, 0)\n    \n    for i := 0; i < n; i++ {\n        arr = append(arr, p{ nums1[i], nums2[i] })\n    }\n        \n    sort.Slice(arr, func(i, j int) bool {\n        return arr[i].x < arr[j].x \n    })\n    \n    max := make([]IndexTree, n)\n    \n    c := compress(nums2)\n    \n    for i := n - 1; i >= 0; i-- {\n        x := arr[i].x\n        y := arr[i].y\n        if i == n - 1 {\n            max[i] = NewIndexTree(n + 1, MaxIndex{})\n            max[i] = max[i].Add(c[y], x + y)\n        } else {\n            max[i] = max[i+1].Add(c[y], x + y)\n        }                  \n    }\n    \n    res := make([]int, 0)\n    for _, q := range queries {\n        i := sort.Search(n, func(i int) bool {\n            return arr[i].x >= q[0]\n        })\n        y := sort.Search(n, func(i int) bool {\n            return nums2[i] >= q[1]\n        })\n        \n        if i >= len(max) {\n            res = append(res, -1)\n        } else {\n        \n            res = append(res, max[i].Get(y, n + 1))\n        }\n    }\n    \n    return res\n}\n```
['Go']