1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

array a, b
sorted_sum C(a,b)
print(C[k])
class sorted_sum:
//"generates" a sorted array with the values (a_j+b_k) such that j<=k
def sorted_sum(a, b):
this.a = a
this.b = b
def value(j, k): //O(1)
if j<=k:
return a[j]+b[k]
return NaN
def operator[](index): //O(n lg^3 n)
//returns the value in the index position of the sorted array
f = lambda j,k: where_am_i(value(j,k))
[j,k] = triang_matrix_binary_search(f, 0, a.size(), 0, b.size(), index)
return value(j,k)
def where_am_i(value): //O(n lg n)
//gives the "lower_bound" position of value in the sorted array
position = 0
for x in a:
position += b.end()  lower_bound(array=b, val=valuex)
return position
def triang_matrix_binary_search(m, rbeg, rend, cbeg, cend, target): //O(lg^2 n)
//returns the coordinates of target on the m "matrix"
if rbeg == rend or cbeg == cend: //value not found
return nil
rmid = rbeg + (rendrbeg)/2
f = lambda x: m(rmid, x)
column = lower_bound(f, lower=cbeg, upper=cend, val=target)
if m(rmid, column) == target:
return rmid, column
//touching the diagonal
//discard the bottom because they are all greater (or invalid with j>k)
if column == rmid:
return triang_matrix_binary_search(m, rbeg, rmid, cbeg, cend, target):
//recurse
//here we part the matrix in 4
//the br quadrant has values that are all greater that what we want
//the ul quadrant has values that are all greater that what we want
//so we look in bl and ur
return
triang_matrix_binary_search(m, rbeg, rmid, column, cend, target): //ur
or triang_matrix_binary_search(m, rmid, rend, cbeg, column, target): //bl
 