Trova la somma di una serie di sottoarray

Question

Questa è una domanda dell'APAC di Google 2017. Problem D: Sum of Sum

Alice presentato il suo amico Bob con una serie di N interi positivi, indicizzato da 1 a N. Ha sfidato Bob con molte query del tipo "Qual è la somma dei numeri tra questi due indici?" Ma Bob è stato in grado di risolvere il problema troppo facilmente. Alice ha preso il suo array e ha trovato tutti i sottotitoli non N * (N + 1)/2 non vuoti di esso. Ha trovato la somma di ciascun subarray e quindi ha ordinato questi valori (in ordine non crescente) per creare un nuovo array, indicizzato da 1 a N * (N + 1)/2. Ad esempio, per un array iniziale [2, 3, 2], Alice genera i sottoarray [2], [3], [2], [2, 3], [3, 2] e [2, 3, 2] (nota che [2, 2], ad esempio, NON è un sottoarray). Poi prendeva le somme - 2, 3, 2, 5, 5, 7 - e le ordinava per ottenere una nuova serie di [2, 3, 5, 5, 7]. Alice ha dato l'iniziale array a Bob, insieme alle query Q del modulo "qual è la somma dei numeri dall'indice Li a Ri, incluso, nel nuovo array?" Ora Bob è nei guai! Puoi aiutarlo?

La soluzione semplice è troppo inefficiente anche in C++ per set di dati di grandi dimensioni. C'è un modo più efficiente per risolvere questo?

Attualmente sto attraversando questo ciclo for per costruire la serie finale:

multiset<int> sums; 
    long long int temp = 0; 
    for (long long int len = 1; len <= n; ++len) 
    { 
     for (int start = 0; start+len <= n; ++start) 
     { 
      temp = 0; 
      for (int i = 0; i < len; ++i) 
      { 
       temp += arr[start + i]; //arr stores the original array of n digits 
      } 
      sums.insert(temp); 
     } 
    } 

P.S: E 'il mio attuale implementazione O (n^5)? Il mio errore, posso vedere come la sua O (n^3) ora. Grazie Modifica: le risposte finora sono state utili ma con dataset di grandi dimensioni che coinvolgono n = 200000 elementi, sembra che qualsiasi soluzione che calcoli l'intero array di subarray sia troppo costosa. Tutte le soluzioni inviate non sembrano calcolare l'intera gamma di sottoarray

Answer 1

Facendo una piccola ricerca ho trovato questo, spero possa essere utile

https://www.quora.com/How-can-problem-D-Sums-of-sums-from-Round-E-of-the-Google-APAC-Test-2016-be-solved-for-the-large-dataset

Answer 2

Come indicato nei commenti, la soluzione è O (N^3), calcolata come O (N^2) volte una somma O (N) e un inserimento in multiset (che puoi ignorare rispetto a O (N), vedi in fondo a questa risposta).

Ma scambiare i tuoi due primi cicli, si sta facendo la stessa identica N * (N + 1)/2 somme e inserimenti:

for (int start = 0; start < n; ++start) 
{ 
    for (long long int len = 1; start + len <= n; ++len) 
    { 
     temp = 0; 
     for (int i = 0; i < len; ++i) 
     { 
      temp += arr[start + i]; //arr stores the original array of n digits 
     } 
     sums.insert(temp); 
    } 
} 

Ora, se si guarda al vostro temp somme mi sembra ovvio che si stai facendo un lavoro ridondante. Somma start + 1-start + 1, poi start + 1-start + 2, poi start + 1-start + 3, ecc Per ogni nuovo len, la somma che stai calcolo è quello per il valore precedente di len, più un elemento. Quindi è possibile rimuovere questa loop interno:

for (int start = 0; start < n; ++start) 
{ 
    temp = 0; 
    for (long long int len = 1; start + len <= n; ++len) 
    { 
     temp += arr[start + len]; //arr stores the original array of n digits 
     sums.insert(temp); 
    } 
} 

Così in N * (N + 1)/2 si genera l'insieme di valori. Ovviamente, utilizzando un multiset si nasconde l'ordinamento dei dati, ma l'inserimento in generale costa log(sums.size()).

L'ordinamento a parte, poiché l'ordinamento di un set di dimensioni S deve portare S * log (S), costerebbe N*(N+1)/2 * log (N*(N+1)/2) che è (solo) inferiore a N*(N+1) * log((N+1)/sqrt(2)).

Nota che, poiché hai interi positivi, ogni serie di interi len generati con il ciclo interno è già ordinata, quindi forse puoi usarli per fare qualcosa di intelligente per accelerare l'ordinamento.Che è anche quello multiset fa according to cplusplus.com:

Se N elementi vengono inseriti, NLog (size + N) in generale, ma lineare dimensioni + N se gli elementi sono già ordinati secondo lo stesso criterio d'ordine utilizzato dal contenitore.

Answer 3

Il modo più conciso ed efficiente mi viene in mente è questa:

std::vector<int> in{ 2, 3, 2 }; 
std::vector<int> out(in.size()*(in.size()+1)/2); 

auto out_it = out.begin(); 
for (size_t i = 0; i < in.size() ; ++i) { 
    out_it=std::partial_sum(in.begin()+i, in.end(), out_it); 
} 
std::sort(out.begin(), out.end()); 

Accanto a considerazioni di complessità (Questa soluzione è - credo - O (n^2 * log (n)), come si stai ordinando un array con le voci O (n^2), dovresti evitare allocazioni di memoria dinamica e inseguimento del puntatore come la peste (che entrambe sono parte integrante di std::multi_set).