On a 2 ensembles de données (listes, arbres… ) L1 et L2, indexés avec une relation d’ordre total.
Cherche algorithme permettant
[] l’insertion/suppression d’1 élément dans un des ensembles
[] l’insertion/suppression d’une suite consécutive de m éléments de L1. ie: plusieurs éléments dont les index sont croissants et consécutif dans l’ensemble L1 (pas forcément des index consécutifs dans N…)
Tous supression dans un l’ensemble L1 se traduit par un ajout dans L2.
Ex.
L1 à les éléments d’index:
1,2, 3, … 23, 24, 26, 29, 30, 31, 33 …
Il faut déplacer les éléments d’index 24=< i =< 30
pour les mettres dans l’ensemble L2.
:??: J’ai trouvé en (m+1)*log(n) (ou m est le nombre d’éléments à déplacer et n la taille de l’ensemble) mais je pense qu’il y a moyen de faire en log(n).