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(N2+Q).
