infoarena informatica de performanta

Rest

Problema se reduce la gasirea unei structuri care sa permita rezolvarea celor doua tipuri de operatii. Putem folosi un arbore de intervale A, unde un nod reprezinta restul impartirii la P a numarului format din alipirea cifrelor in baza B din intervalul corespunzator. Constructia arborelui se poate face recursiv: A[i] = (A[fiu_stanga] * B^{lungime_interval_fiu_dreapta} + A[fiu_dreapta]) % P. Pentru a face o operatie de tipul 1 (update), modificam frunza corespunzatoare operatiei si actualizam arborele recursiv dinspre frunza spre radacina. La o operatie de tipul 2 (query), intervalul dat il spargem intr-un numar minim de intervale consecutive ce apar si in arbore. Rezultatul pentru un query, se face din compunerea acestor intervale, dupa aceeasi formula de recurenta.
Pentru a obtine complexitatea O(logN) atat pe operatia query, cat si pe update, este necesara precalcularea puterilor lui B modulo P.