Ilotrzyny (omówienie)

07.03.2010


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).

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com