2.1 Constructeur

class Fenwick {
    ...
    Fenwick(int lo, int hi) {
        /* TODO */
    }
}

2.2 Méthode get

Pour se familiariser avec la structure de l’arbre, on peut, par exemple, chercher les feuilles de l’arbre comme dans un arbre binaire de recherche (voir les diapos de l’amphi 5). On peut le faire itérativement ou récursivement.

class Fenwick {
    ...
    Fenwick get(int i) {
        /* TODO */
    }
}

2.3 Méthode inc

On veut maintenant implémenter la méthode inc. Un appel inc(i) incrémente les accumulateurs de tous les nœuds de l’arbre associés à un intervalle contenant i. L’appel ne fait rien si i n’est pas dans [lo, hi[. On implémentera cette méthode avec des appels récursifs.

Le schéma ci-dessous illustre l’appel inc(12). Les flèches jaunes représentent les appels récursifs. Les nœuds jaunes ont reçu un appel inc(12), incrémenté leurs compteurs et transmis l’appel à leurs sous-arbres. Les nœuds beiges ont reçu un appel inc(12) mais n’ont rien fait.

class Fenwick {
    ...
    void inc(int i) {
        /* TODO */
    }
}

2.4 Méthode cumulative

La méthode cumulative(i) renvoie la somme des éléments aux indices strictement inférieurs à i du tableau représenté par l’arbre. On remarque que si le nœud courant a des sous-arbres, alors cumulative(i) est égal à left.cumulative(i) + right.cumulative(i). Mais selon la valeur de i un calcul sans récursion est parfois possible.

Le schéma ci-dessous illustre l’appel cumulative(13). Il renvoie 21, la somme des nœuds jaunes (12+1+3+5), qui est aussi la somme des feuilles numérotées de 0 à 12. Les flèches jaunes représentent les appels récursifs. Les nœuds jaunes et beiges n’ont pas eu besoin de récursion pour renvoyer le résultat.

class Fenwick {
    ...
    int cumulative(int i) {
        /* TODO */
    }
}

3.1 Méthode naïve pour compter le nombre d’inversions

class CountInversions {
    ...
   static int countInversionsNaive(int[] a) {
        /* TODO */
    }
}

3.2 Inversions et arbres de Fenwick.

On va maintenant utiliser les arbres de Fenwick pour compter plus efficacement le nombre d’inversions dans un tableau a. On procède de la manière suivante.

• Commencer par créer un arbre de Fenwick fen sur l’intervalle [min,max+1[ où min et max sont respectivement le min et le max des valeurs stockées dans les cases de a.

• Parcourir ensuite a de droite à gauche et quand la case i est explorée, incrémenter la valeur de la case d’index a[i] dans fen. On peut remarquer qu’au moment où on explore la case i, le nombre fen.cumulative(a[i]) est égal au nombre d’éléments a[j], tels que j>i et a[j]<a[i], convainquez-vous en!

class CountInversions {
    ...
   static int countInversionsFen(int[] a) {
        /* TODO */
    }
}

3.3 Inversions et arbres de Fenwick : version optimisée

L’algorithme utilisé dans la partie précédente n’est pas efficace si la valeur de span pour a est grande par rapport à la taille de a, par exemple si a=[-10000,9999,2,350654,10]. Pour améliorer sa complexité, on va utiliser la remarque suivante : le nombre d’inversions d’un tableau ne dépend que de l’ordre relatif de ses éléments et pas de leur valeur.

Par exemple a=[-10000,9999,2,350654,10] et b=[0,3,1,4,2] ont le même nombre d’inversions, convainquez-vous en!

• Étant donné un tableau a, on va donc d’abord créer un tableau b de même longueur que a, dont les valeurs des cases seront comprises entre 0 et a.length-1 et tels que l’ordre relatif des cases dans a et dans b soit le même.

• Ensuite on appliquera la méthode countInversionsFen au tableau b.

class CountInversions {
    ...
   static int countInversionsBest(int[] a) {
        /* TODO */
    }
}