Contando o número de somas de sub-matrizes contíguas de uma matriz

Nos é dado um array com todos .$a[1 \ldots n]$$a[i]>0$

Agora precisamos descobrir quantas somas distintas podem ser formadas a partir de suas sub-matrizes (onde uma sub-matriz é um intervalo contíguo da matriz, ou seja, para alguns , a soma é a soma de todos os os elementos do subarray). Por exemplo, se , a resposta é 4: podemos formar .$a[j\ldots k]$$j,k$$a=[1,2,1]$$1,2,3,4$

Eu sei como contar o número de somas distintas em .$O(n^2)$

Além disso, percebi que isso é semelhante ao problema clássico em que precisamos encontrar o número de substrings distintos de uma string. Eu estava pensando na possibilidade de construir uma matriz de sufixos e resolvê-la de maneira semelhante (no tempo ). Mas não consegui descobrir como modificar isso para funcionar aqui. Por exemplo, se usarmos uma matriz de sufixos para , obteremos 5 casos em vez dos quatro aceitáveis. É possível fazer isso usando matrizes de sufixo ou estou pensando na direção errada?$O(n)$$a=[1,2,1]$

Também há mais uma direção em que estive pensando. Divida e conquiste. Como se eu dividisse a matriz em duas partes todas as vezes até que ela fosse reduzida a um único elemento. Um único elemento pode ter uma soma. Agora, se combinarmos dois elementos únicos, isso pode ser feito de duas maneiras: se os dois intervalos únicos tiverem o mesmo elemento, obteremos 2 somas diferentes, ou se ambos tiverem elementos diferentes, obteremos 3 somas diferentes. Mas não estou conseguindo generalizar isso para mesclar matrizes de comprimento maior que 1. É possível mesclar matrizes de dois m de tamanho e obter a resposta em ?$O(m)$

Você quase certamente não pode melhorar que na pior das hipóteses, pois o número de diferentes somas pode estar em Θ ( n 2 ) .$O(n^2)$$\Theta(n^2)$

Considere, por exemplo, a matriz . Aqui cada um dos n ( n + 1 $[1,2,4,8,\dotsc, 2^n]$ subarrays contíguos têm uma soma diferente.$\frac{n(n+1)}2$

O "quase certo" se deve ao fato de o problema não exigir os valores das somas como saída. No entanto, não creio que duplicatas possam ser evitadas sem determinar pelo menos a maioria dos valores.