Zliczanie liczby sum z przyległych podtablic tablicy

Otrzymujemy tablicę ze wszystkimi .$a[1 \ldots n]$$a[i]>0$

Teraz musimy dowiedzieć się, ile różnych sum można uformować z jego podstron (gdzie podtablica to ciągły zakres tablicy, tj. dla niektórych , suma jest sumą wszystkich elementy podtablicy). Na przykład, jeśli , to odpowiedź brzmi 4: możemy utworzyć .$a[j\ldots k]$$j,k$$a=[1,2,1]$$1,2,3,4$

Wiem, jak policzyć liczbę odrębnych sum w czasie .$O(n^2)$

Ponadto zdałem sobie sprawę, że jest to podobne do klasycznego problemu, w którym musimy znaleźć liczbę różnych podciągów łańcucha. Myślałem o możliwości skonstruowania tablicy sufiksów i rozwiązania jej w podobny sposób (w czasie ). Ale nie byłem w stanie dowiedzieć się, jak to zmienić, aby działało tutaj. Na przykład, jeśli użyjemy tablicy sufiksów dla , otrzymamy 5 przypadków zamiast czterech dopuszczalnych. Czy można to zrobić za pomocą tablic przyrostków, czy też myślę w złym kierunku?$O(n)$$a=[1,2,1]$

Myślę też o jednym kierunku. Dziel i podbijaj. Jakbym za każdym razem dzielił tablicę na dwie części, dopóki nie zostanie zredukowana do jednego elementu. Pojedynczy element może mieć jedną sumę. Teraz, jeśli połączymy dwa pojedyncze elementy, można to zrobić na dwa sposoby: jeśli oba pojedyncze zakresy mają ten sam element, otrzymamy 2 różne sumy, lub jeśli oba mają różne elementy, otrzymamy 3 różne sumy. Ale nie jestem w stanie uogólnić tego dla scalania tablic o długości większej niż 1. Czy jest możliwe scalenie dwóch tablic o rozmiarze m i uzyskanie odpowiedzi w ?$O(m)$

W najgorszym przypadku prawie na pewno nie można uzyskać lepszej wartości niż ponieważ liczba różnych sum może być w .$O(n^2)$$\Theta(n^2)$

Rozważ np. Tablicę . Tutaj każda z sąsiednich podrzędnych ma inną sumę.$[1,2,4,8,\dotsc, 2^n]$$\frac{n(n+1)}2$

„Prawie na pewno” wynika z faktu, że problem nie wymaga wartości sum jako danych wyjściowych. Jednak nie sądzę, że duplikatów można uniknąć bez określenia przynajmniej większości wartości.