Posortowane sumy prefiksowe

http://jsmigiel.w.staszic.waw.pl/~jsmigiel/gim/WYC.pdf
Najbardziej optymalne rozwiązanie polega na użyciu posortowanego ciągu sum prefiksowych i poruszania się po nim gąsienicą.
Zwracam się o pomoc gdyż pierwszy raz spotykam się z sytuacją gdzie trzeba posortować sumy prefiksowe i nasuwa mi się kilka pytań m.in. o to jak liczyć takie sumy prefiksowe skoro nie będą już one oddawały stanu wyjściowej tablicy dla której policzono te sumy.

No to jedziemy z koksem:

A - oryginalna tablica
S - tablica sum prefiksowych
SUM(i, j) - suma od indeksu i do j
SS - tablica par (S[i], i), posortowana po S[i] oraz i

S[j] = ∑ A[i] | dla i <= j
SUM(i, j) =  S[j] - S[i-1],  dla i <= j; inny zapis to S[j] - S[i] + A[i]
A[i] = S[i] - S[i-1], dla i > 0

Przykład:
Szukamy sumy do 6.

A = [3, -2, 6, 1, -1, 5]
S = [3, 1, 7, 8, 7, 12]
SS = [(1,1), (3,0), (7,2), (7,4), (8,3), (12,5)]

SS juz oddaje wejściowy stan sum prefiksowych. Można się zastanowić jak to wykorzystać.
Ja bym to wykorzystał robiąc mapowanie suma_prefksowa -> posortowane_indeksy_sum_prefixowych.

S_to_idx = {
  1 -> (1),
  3 -> (0),
  7 -> (2, 4),
  8 -> (3),
  12 -> (5),
}

Weź 12, wyszukaj 12-6 = 6. Nie ma.
Weź 8, wyszukaj 8-6 = 2 . Nie ma.
Weź 7, wyszukaj 7-6 = 1. Jest. Teraz znajdź najmniejszy indeks mniejszy od 4 - będzie to pierwszy indeks w posortowanym zakresie. Jest to 1. Mamy kandydata na sumę zakresu SUM(1,4)
I tak dalej.

Akurat dla tego algorytmu pierwsze sortowanie wcale nie jest potrzebne, za to ważne by posortować indeksy (albo użyć kolekcji sortującej). Więc pewnie istnieje jeszcze alternatywne rozwiązanie. Złożoność, zakładając, że używamy std::unordered_map i std::set - bliskie O(n log n), pominąłem efekt kolizji hashowania oraz to, że w typowym przypadku lista posortowanych indeksów będzie proporcjonalna do n / k, gdzie k to ilość unikalnych sum.