Bezpośrednie sumowanie wszystkich możliwych ilotrzynów dla każdego zapytania nie miało szans zmieścić się w czasie przy podanych ograczeniach. Potrzeba tu sprytniejszego algorytmu.
Powinniśmy umieć szybko odpowiadać na pytania postaci: suma_ijk( a_i*a_j*a_k )
po wszystkich indeksach i,j,k z dowolnego przedziału. Przyjrzyjmy się tożsamości:
( suma_i( a_i ) ) ^ 3 =
= ( suma_i( a_i^3 ) ) + ( 3*suma_ij( a_i^2*a_j ) ) + ( 6*suma_ijk( a_i*a_j*a_k ) )
Po nietrudnych przekształceniach otrzymamy ładny wzór:
suma_ijk( a_i*a_j*a_k ) =
[( suma_i( a_i ) )^3 - 3*( suma_i( a_i ) )*( suma_i( a_i^2 ) ) + 2*suma_i( a_i^3 )] /6
który wykorzystuje jedynie sumę, sumę kwadratów oraz sumę sześcianów danych liczb.
Potrzeba szybkiego odpowiadania na pytania o te sumy nasuwa rozwiązanie wykorzystujące drzewa przedziałowe (Czytelnikom nie znającym drzew przedziałowych polecam następujący artykuł). Mając trzy drzewa przedziałowe, wykonujemy wszystkie operacje w czasie O(log n). Złożoność algorytmu jest więc O(q log n).