2.1 Constructeur

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

Le constructeur contiendra des appels récursifs pour construire les sous-arbres, le cas échéant.

Le champ acc dans la classe Fenwick permet de stocker la valeur associée au nœud.

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.

public 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.

public 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.

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

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

public 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]. Prenez le temps de vous en convaincre !

public 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].

Indication : se ramener au cas span = N.

On pourra pour cela utiliser les méthodes statiques suivantes de la classe Arrays, (après avoir importé celle-ci avec import java.util.Arrays; en début de fichier) :

• int[] copyOf(int[] a, int n),

• void sort(int [] a) (attention, cette méthode modifie a),

• int binarySearch(int[] a, val).

Pour un tableau a de longueur N, la complexité de sort est O(N log N) et celle de binarySearch est O(log N).