Operații statice pe secvențe

După ce la nivelul 1 am prezentat câteva tehnici de optimizare a problemelor în care ce lucrează cu mai multe operații pe secvențe ale unui șir, aici rezolvăm problema interogării când este vorba de minime (sau maxime), operații ce nu se pot rezolva folosind principiul sumelor parțiale.

Metoda se bazează pe precalcularea tuturor informațiilor pentru secvențe de lungime putere de 2, numărul acestora nefiind foarte mare, și apoi compunerea acestora pentru a obține informații despre secvențe de orice alte lungimi.

Odată înțeleasă metoda, putem folosi abordări similare la arbori, pe lanțurile către rădăcină, sau la aflarea celui mai apropiat strămoș comun pentru două noduri (LCA).