Ricerca della somma del sub-array in un array intero

Question

Dato un array di numeri interi N positivi. Può disporre di sotto-array n*(n+1)/2 compresi i sotto-array a elemento singolo. Ogni sotto-array ha una somma S. Trovare S's per tutti i sotto-array è ovviamente O(n^2) in quanto il numero di sotto-array è O(n^2). Molte somme S's possono anche essere ripetute. Esiste un modo per trovare il conteggio di tutte le somme distinte (non i valori esatti delle somme ma solo il conteggio) in O(n logn).

Ho provato un approccio ma bloccato sulla strada. Ho iterato la matrice dall'indice 1 al n.
Dire che a[i] è l'array specificato. Per ogni indice i, a[i] verrà aggiunto a tutte le somme in cui è coinvolto lo a[i-1] e si includerà anche come singolo elemento. Ma il duplicato emergerà se tra le somme in cui è implicato a[i-1], la differenza di due somme è a[i]. Intendo dire che, ad esempio, le somme Sp e Sq terminano allo a[i-1] e la differenza di entrambi è a[i]. Quindi Sp + a[i] equivale a Sq, fornendo come duplicato Sq.

Dire C[i] è il conteggio delle somme distinte in cui termina a a[i].
Quindi C[i] = C[i-1] + 1 - numbers of pairs of sums in which a[i-1] is involved whose difference is a[i].

Ma il problema è trovare la parte del numero di coppie in O(log n). Per favore, dammi qualche suggerimento su questo o se sono su una strada sbagliata e un approccio completamente diverso è necessario.

Answer 1

Quando S non è troppo grande, possiamo contare le somme distinte con una moltiplicazione polinomiale (veloce). Quando S è più grande, N è sperabilmente abbastanza piccolo da usare un algoritmo quadratico.

Sia x_1, x_2, ..., x_n essere gli elementi dell'array. Sia y_0 = 0 e y_i = x_1 + x_2 + ... + x_i. Sia P (z) = z^{y_0} + z^{y_1} + ... + z^{y_n}. Calcola il prodotto dei polinomi P (z) * P (z^{- 1}); il coefficiente di z^k con k> 0 è diverso da zero se e solo se k è una somma di sottoarray, quindi dobbiamo solo leggere il numero di coefficienti non nulli di potenze positive. Le potenze di z, inoltre, vanno da -S a S, quindi la moltiplicazione richiede tempo nell'ordine di S log S.

Answer 2

Puoi osservare i sotto-array come una specie di albero. Nel senso che subarray [0,3] può essere diviso in [0,1] e [2,3].

Quindi, creare un albero, in cui i nodi sono definiti dalla lunghezza del sottoarray e il suo spostamento iniziale nell'array originale, e ogni volta che si calcola un sottoarray, il risultato viene archiviato in questo albero.

Quando si calcola un sub-array, è possibile controllare questo albero per i valori pre-calcolati esistenti.

Inoltre, quando si divide, parti dell'array possono essere calcolate su diversi core della CPU, se questo è importante.

Questa soluzione presuppone che non siano necessari tutti i valori contemporaneamente, piuttosto ad-hoc. Per il primo, ci potrebbe essere una soluzione più intelligente.

Inoltre, presumo che stiamo parlando di conteggi di elementi in 10000 e altro. Altrimenti, tale lavoro è un bel esercizio ma non ha molto valore pratico.