2012-07-16 27 views
6

Sé que esta pregunta se ha discutido anteriormente, pero estoy interesado en hacer esto usando un árbol binario indexado. Encontré el enlace this para mostrar cómo hacerlo. No acabo de seguir la explicación. ¿Podría alguien darme una explicación de por qué lo siguiente dado es cierto?Contando las inversiones utilizando BIT

Create a BIT of size greater than n(no of elements). Iterate through array A (
let j be the index of loop),and for each element A[j] do: 

1) Add j-sum(A[j]) to the number of inversions 
2) add(A[j], 1) (i.e. add 1 to the position A[j] on BIT. This effectively 
counts the number of time value A[j] is seen so far) 

I dont get why this works.

Respuesta

13

Se produce una inversión cuando un elemento es más grande que algún elemento que lo sigue en la matriz.

Podemos contar las inversiones agrupándolas por el segundo elemento. Por ejemplo, en la matriz [4, 3, 1, 2], los pares de elementos (4, 3), (4, 1), (4, 2), (3, 1) y (3, 2) son inversiones Los agrupamos por segundo elemento, por lo tanto: [[(4, 1), (3, 1)], [(4, 2), (3, 2)], [(4, 3)]].

Consideramos cada elemento a su vez, y contamos de cuántas inversiones es el segundo elemento de. En el ejemplo, el elemento 4 es el segundo elemento en 0 inversiones, el elemento 3 en 1 inversión, y los elementos 1 y 2 en 2 inversiones cada uno.

Para que un elemento determinado sea el segundo elemento de una inversión, tiene que haber un elemento más grande en algún lugar antes que en la matriz.

Realizamos el recuento de manera eficiente atravesando la matriz de izquierda a derecha y siempre haciendo un seguimiento de cuántos elementos de cada valor se han encontrado hasta el momento, utilizando un BIT. Inicialmente, nuestra tabla de frecuencias será [0, 0, 0, 0], ya que no hemos visto ningún elemento. Después de visitar el 4, actualizamos su frecuencia, dando [0, 0, 0, 1]. Después de visitar el 3, [0, 0, 1, 1], y así sucesivamente.

Cada vez que visitamos una posición, utilizamos la BIT para averiguar cuántos elementos visitados hasta ahora son más grandes que ella. Entonces, por ejemplo, cuando nos encontramos con el 1, el BIT contiene actualmente [0, 0, 1, 1], lo que representa que hasta ahora había cero 1 y 2, uno 3 y uno 4. Al agregar los valores 0 + 1 + 1 , contamos el número de elementos hasta ahora que son mayores que 1.

Añadiendo todos estos recuentos individuales dan el número total de inversiones.

Tenga en cuenta que, en general, debe emplear la compresión de coordenadas para que esto sea eficiente. Por ejemplo, si su matriz inicial contiene números como A = [92, 631, 50, 7], no debe asignar un BIT con cientos de elementos. En su lugar, ordene la matriz para determinar que 7 631, lo que nos permite asignar los rangos 7 => 1, 50 => 2, 92 => 3, 631 => 4; luego reemplace cada elemento por su rango, dando B = [3, 4, 2, 1]. El número de inversiones de esta matriz será el mismo que en el original, ya que B [i]> B [j] si y solo si A [i]> A [j].

(Nota: un programador real probablemente usaría índices comenzando desde cero.)

+0

Awesomeness. ¡¡Muchas gracias!! – frodo

+0

Gran respuesta. Sin embargo, una cosa: la pregunta pregunta por qué se agrega 'j-sum (A [j])', que se pasa de largo ligeramente. Supongo que 'suma (A [j])' significa "la cantidad de elementos de A vistos hasta el momento que están entre 0 y A [j]". En ese caso, es la cantidad total de elementos hasta el momento * menor o igual que * A [j]. Todos los * otros * elementos hasta ahora deben, por lo tanto, ser mayores que j. ¿Cuántos hay? Si la matriz está basada en 0, debe haber j (si no j-1) de ellos. Entonces debe haber 'j-sum (A [j])' de estos elementos más grandes hasta el momento. (Que es lo mismo que 'suma (A [n]) - suma (A [j])' desde 'j == suma (A [n])'.) –