Compter le nombre de sommes provenant de sous-réseaux contigus d'un tableau

On nous donne un tableau avec tous a [ i ] > 0 .$a[1 \ldots n]$$a[i]>0$

Maintenant, nous devons trouver combien de sommes distinctes peuvent être formées à partir de ses sous-réseaux (où un sous-réseau est une plage contiguë du tableau, c'est-à-dire pour certains j , k , la somme est la somme de tous les éléments du sous-tableau). Par exemple, si a = [ 1 , 2 , 1 ] , alors la réponse est 4: nous pouvons former 1 , 2 , 3 , 4 .$a[j\ldots k]$$j,k$$a=[1,2,1]$$1,2,3,4$

Je sais compter le nombre de sommes distinctes en temps .$O(n^2)$

De plus, j'ai réalisé que cela est similaire au problème classique où nous devons trouver le nombre de sous-chaînes distinctes d'une chaîne. Je pensais à la possibilité de construire un tableau de suffixes et de le résoudre de manière similaire (en temps ). Mais je n'ai pas été en mesure de comprendre comment modifier cela pour fonctionner ici. Par exemple, si nous utilisons un tableau de suffixes pour a = [ 1 , 2 , 1 ], nous obtiendrons 5 cas au lieu des quatre cas acceptables. Est-ce possible de le faire en utilisant des tableaux de suffixes ou est-ce que je pense dans la mauvaise direction?$O(n)$$a=[1,2,1]$

Il y a aussi une autre direction à laquelle j'ai pensé. Diviser pour régner. Comme si je divisais le tableau en deux parties à chaque fois jusqu'à ce qu'il soit réduit à un seul élément. Un seul élément peut avoir une somme. Maintenant, si nous combinons deux éléments simples, cela peut être fait de deux manières: si les deux plages simples ont le même élément, nous obtenons 2 sommes différentes, ou si les deux ont des éléments différents, nous obtenons 3 sommes différentes. Mais je ne suis pas en mesure de généraliser cela pour fusionner des tableaux de longueur supérieure à 1. Est-il possible de fusionner deux tableaux de taille m et d'obtenir la réponse en ?$O(m)$

$O(n^2)$$\Theta(n^2)$

$[1,2,4,8,\dotsc, 2^n]$$\frac{n(n+1)}2$

Le "presque sûrement" est dû au fait que le problème ne nécessite pas les valeurs des sommes en sortie. Cependant, je ne pense pas que les doublons puissent être évités sans déterminer au moins la plupart des valeurs.