h2(#inversari). 'Inversari':problema/inversari

h2(#inversari). 'Inversari':problema/inversari
 
Pentru a determina numărul de inversiuni dintr-un interval, vom menţine o matrice $D[i][j]$ = numărul de inversiuni în intervalul de lungime $i$ care are ca ultim element poziţia $j$. Relaţia de recurenţă este $D[i][j] = D[i-1][j-1]$+numărul de elemente din intervalul curent mai mari decât cel de pe poziţia j. Pentru a determina acest număr vom menţine o dinamică $I[i][j]$ = numărul de elemente mari mari decat cel de pe pozitia j din intervalul de lungime $i$ ce are pe ultima poziţie poziţia $j$. Recurenţa este $I[i][j] = I[i-1][j]$, dacă elementul de pe poziţia $j-i+1$ este mai mic decât cel de pe poziţia $j$, sau $I[i-1][j]+1$ invers.
 
Se observă că, pentru cele două matrici nu avem nevoie decât de două linii, deci odată calculată matricea pentru o lungime de interval, vom răspunde la toate query-urile ce corespund acelei lungimi.
Complexitatea totală este $O(N^2^+Q)$.