Contando el número de sumas de subconjuntos contiguos de una matriz

Se nos da una matriz con todo a [ i ] > 0 .$a[1 \ldots n]$$a[i]>0$

Ahora necesitamos encontrar cuántas sumas distintas se pueden formar a partir de sus submatrices (donde una submatriz es un rango contiguo de la matriz, es decir, para alguna j , k , la suma es la suma de todas las elementos de la submatriz). Por ejemplo, si a = [ 1 , 2 , 1 ] , entonces la respuesta es 4: podemos formar 1 , 2 , 3 , 4 .$a[j\ldots k]$$j,k$$a=[1,2,1]$$1,2,3,4$

Sé cómo contar el número de sumas distintas en el tiempo .$O(n^2)$

Además, me he dado cuenta de que esto es similar al problema clásico en el que necesitamos encontrar el número de subcadenas distintas de una cadena. Estaba pensando en la posibilidad de construir una matriz de sufijos y resolverla de manera similar (en tiempo ). Pero no he podido averiguar cómo modificar eso para que funcione aquí. Por ejemplo, si usamos una matriz de sufijos para a = [ 1 , 2 , 1 ] obtendremos 5 casos en lugar de los cuatro aceptables. ¿Es posible hacer esto usando matrices de sufijos o estoy pensando en la dirección incorrecta?$O(n)$$a=[1,2,1]$

También hay una dirección más en la que he estado pensando. Divide y vencerás. Como si dividiera la matriz en dos partes cada vez hasta que se reduzca a un solo elemento. Un solo elemento puede tener una suma. Ahora, si combinamos dos elementos individuales, se puede hacer de dos maneras: si ambos rangos individuales tienen el mismo elemento, obtenemos 2 sumas diferentes, o si ambos tienen elementos diferentes, obtenemos 3 sumas diferentes. Pero no puedo generalizar esto para fusionar matrices de longitud mayor que 1. ¿Es posible fusionar matrices de dos m de tamaño y obtener la respuesta en ?$O(m)$

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

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

El "casi seguro" se debe al hecho de que el problema no requiere los valores de las sumas como salida. Sin embargo, no creo que se puedan evitar los duplicados sin determinar al menos la mayoría de los valores.