Efficient query for finding an element in a range

Question

I face a problem, where I need to find a specific pairwise sum where the first element from the index has index > i.

Example:

[1, 2, 3, 4, 6] (index 0 to 4)

target_sum = 9

Now, from this array I need to find a pairwise sum where the first element from the index has index > i.

Now, the obvious solution is:

1. Calculate the pairwise sum array. [1+2, 1+3, 1+4, 1+6, 2+3, 2+4, 2+6, 3+4, 3+6, 4+6] [ O(n^2) ]
2. Loop through index i+1 to n to find the target_sum. [ O(n^2) ] (n being the length of original array)

Now, the main issue is 2. Even if I can't improve (1), I need to improve (2), as this will be queried a lot.

One approach that comes to my mind:

1. Make an array of index, value pair from the pairwise sum array. O(n^2) [n being the original length]
2. Sort the array first with value, then with index. O(n^2 * logn)
3. For each query, run a binary search to find the interval where the value exists. O(logn)
4. Run another binary search on that interval to find the index > i.

Is there any elegant and better approach?

Answer 1

Create a map sum -> highest first element index in O(n^2). Then answer each query in O(1) by looking up the target sum in the map and deciding if highest first element index is higher than i.