jak znaleźć sumę do kth elementu posortowanej tablicy od l do r?

Question

Problem:
Podaliśmy tablicę A[] o rozmiarze N. Teraz daliśmy Q zapytań, z których każda składa się z trzech zapytań całkowitą l,r,k gdzie:

1<=l<=r<=N 
1<=k<=(r-l+1) 
1<=N,Q<=10^5 

teraz, chcemy dowiedzieć się sumę zapisu do elementu k z posortowane sub-macierzy z l do r.
Na przykład:
Niech N=6 i element tablicy będzie 5,1,7,4,6,3
And Q=1 gdzie l,r,k być 2,5,3.
następnie sub-tablica z index 2 to index 5 być {1,7,4,6}
po sortowaniu staje jak {1,4,6,7} więc podsumować września k=3 termin jest równa (1+4+6)=11
więc odpowiedź 11.
Próbowałem użyć sortowania każdej pod-tablicy, a następnie podsumowania, w najgorszym przypadku zajmuje ona złożoność czasu w postaci Q*N*log(N).
Proszę pomóc znaleźć lepsze rozwiązanie w zakresie złożoności czasowej mniejszym niż Q*N w najgorszym przypadku.

Answer 1

Jednym podejściem byłoby wstępne przetwarzanie za pomocą mergesort z modyfikacją, która zachowuje kopię wszystkich posortowanych wyników pośrednich.

To przetwarzanie wstępne zajmuje O (nlogn).

Załóżmy, że zaczęliśmy od 32 elementów. Chcielibyśmy teraz:

• 16 sortowane 2 listy elementów
• 8 klasyfikowane 4 wykazy elementów
• 4 8 wymienia sortowanie elementów
• 2 posortowane 16 wymienia elementów
• 1 posortowane 32 listę elementów.

Możemy również wstępnie obliczać sumę prefiksów każdej z tych list w O (nlogn).

Następnie, gdy mamy do czynienia z zapytaniem od l do r, możemy zidentyfikować log (n) z wstępnie przetworzonych list, które razem obejmą wszystkie elementy od l do r.

Możemy następnie użyć wyszukiwania binarnego, aby znaleźć taką wartość, że w zidentyfikowanych listach znajduje się dokładnie k mniejszych elementów, i użyć sumy prefiksu do obliczenia sumy.

Answer 2

Jeśli O (Q)> = O (log n):

Sortowanie pierwotne indeksy tablicę o sortowania, ich elementów, na przykład:

values: [50, 10, 20, 40, 30] -> [10, 20, 30, 40, 50] 
indices: [#0, #1, #2, #3, #4] -> [#1, #2, #4, #3, #0] 

Następnie, dla każdego zapytania zeskanuj posortowane indeksy od lewej do prawej i dodaj wartości pierwszych elementów, których napotkasz, których indeksy znajdują się w zasięgu ([l, r]). Złożoność będzie O (QN + N log N) = O (QN) - ponownie, pod warunkiem, że O (Q)> = O (log N).

Istnieje sposób na poprawę tego poprzez sortowanie zakresów zapytań w pierwszej kolejności, a następnie wykonywanie wszystkich zapytań w jednym skanie posortowanych indeksów, ale nie ma sposobu, aby przewidzieć, jak wpłynie to na złożoność, nie wiedząc o czymś specjalnym. długości zakresów.