Nora prépare huit cases fictives sur une feuille de service. Camille reçoit leurs comptes, puis une correction qui ne concerne qu'une case. Elle doit remettre des sommes sur les portions demandées en conservant cette correction. Aucun stock, appareil ou service réel n'est mesuré. Les regroupements seront calculés sur papier ; ils ne décrivent ni la capacité ni la disposition d'un rangement matériel.
LISTA présente une catégorie d'armoires à tiroirs.
Tennsco présente des catégories de rangement.
Lyon présente des catégories d'armoires.
Ces catégories seules ont été lues. Aucun meuble, image ou procédé réel ne fournit les regroupements et les comptes de cette feuille.
Les cases sont numérotées de un à huit et portent deux, un, trois, zéro, quatre, deux, un, cinq. Un préfixe de borne k comprend les cases un à k ; la borne zéro représente la somme vide, zéro. Nous utilisons une structure classique de sommes partielles, dite arbre de Fenwick. Elle ne doit pas être confondue avec les valeurs cumulées écrites à toutes les bornes : certaines de ses entrées ne couvrent qu'une petite portion terminant à leur propre indice.
Les entrées n'ont pas toutes la même longueur
Nora associe à chaque indice positif i la plus grande puissance de deux qui divise i. Cette longueur vaut un pour un, trois, cinq et sept ; deux pour deux et six ; quatre pour quatre ; huit pour huit. L'entrée B de l'indice i totalise exactement cette longueur de cases, en terminant à i. Ainsi B six couvre cinq et six, pas les six premières cases. B quatre couvre un à quatre, et B huit toute la feuille. Camille garde ces bornes auprès des sommes pour empêcher leur lecture comme une seconde rangée de comptes individuels.
Les huit entrées valent alors deux, trois, trois, six, quatre, six, un, dix-huit. B deux totalise les deux premières valeurs, deux plus un ; B trois garde seulement le trois reçu. B six additionne quatre et deux. Nora refuse donc d'additionner les huit entrées pour annoncer le total des comptes. Certaines cases s'y trouveraient plusieurs fois, notamment dans B quatre puis B huit. Le total entier peut être lu dans B huit ici parce que huit est une puissance de deux. Cette propriété de la dernière borne ne transforme pas toutes les autres entrées en préfixes complets.
Lire sept enlève successivement des morceaux disjoints
Camille demande les sept premières cases. Elle prend B sept, valeur un, couvrant la seule case sept. Elle retranche la longueur un de sa borne, qui devient six. B six vaut six et couvre cinq à six ; retrancher sa longueur deux donne quatre. B quatre vaut six et couvre un à quatre. Sa longueur quatre ramène la borne à zéro. Les trois morceaux sept, cinq-six, un-quatre sont disjoints et leur réunion est exactement un à sept. Nora remet un plus six plus six, soit treize, avec les trois entrées réellement lues.
La même règle sur une borne générale k retire un morceau finissant à cette borne et ayant sa longueur caractéristique. Il reste le préfixe finissant juste avant ce morceau ; la nouvelle borne est k moins cette longueur. Tant que la borne est positive, le retrait fait diminuer un entier et ne perd ni ne répète une case. Camille termine donc à zéro avec une partition complète du préfixe initial. Cette justification concerne l'addition de morceaux disjoints, différente d'une comparaison de minima sur des fenêtres qui se recouvraient. Nora ne garde pas la somme en déclarant gratuitement que plusieurs lectures d'une même case seraient sans effet.
Pour les cases trois à sept, Camille retire le préfixe deux du préfixe sept. Deux donne directement B deux, trois ; sept donnait treize. La portion demandée vaut dix. Nora conserve cette soustraction avec ses bornes, mais elle ne la présente pas comme la nouveauté du regroupement : deux sommes cumulées ordinaires permettraient aussi ce calcul. Le choix des entrées prendra son rôle lorsque les comptes seront corrigés. La feuille garde donc les portions et leurs valeurs, sans attribuer à leur seule différence une méthode indépendante de recherche déjà employée dans d'autres dossiers.
Une correction monte dans les seuls regroupements qui la contiennent
Nora ajoute deux à la case trois. Camille modifie B trois de trois à cinq, puis B quatre de six à huit, puis B huit de dix-huit à vingt. Elle atteint ces indices en ajoutant à chaque indice sa longueur caractéristique : trois plus un donne quatre ; quatre plus quatre donne huit ; huit plus huit dépasse la feuille. Les autres entrées gardent leurs valeurs. En particulier, B six couvre cinq-six et B sept seulement sept : elles ne contiennent pas la case corrigée. Nora retire une proposition qui ajouterait deux à toutes les entrées d'indice supérieur ou égal à trois, comme si elles étaient toutes des préfixes complets.
La nouvelle lecture du préfixe sept suit encore sept, six, quatre. Les deux premières sommes demeurent un et six ; la dernière devient huit. Le résultat passe donc de treize à quinze, exactement les deux ajoutés à une case de ce préfixe. Le préfixe deux reste trois. La portion trois à sept vaut désormais douze. Camille a conservé les liens de lecture sans recopier les cinq sommes cumulées des bornes trois à sept. Nora peut vérifier l'effet unique de la correction en regardant les morceaux choisis : parmi eux, un seul contient trois et a reçu l'ajout.
Les indices visités par la montée sont ceux des intervalles conservés qui contiennent la case corrigée. Pour un indice i dont la longueur vaut deux à la puissance r, son bloc termine à un multiple de cette longueur et commence juste après le multiple précédent. Le prochain bloc englobant conservé finit à i plus cette longueur. Si cette nouvelle borne possède une longueur plus grande, son intervalle absorbe le bloc précédent ; les bornes intermédiaires finissent dans des blocs placés après la case de départ. Nora conserve cette description des intervalles, pas seulement le nom d'un bit, afin que la montée soit justifiée par les cases réellement regroupées.
Camille compare aussi les deux directions depuis trois. Pour lire le préfixe trois, elle descend vers deux puis zéro : B trois et B deux totalisent six sur la feuille initiale. Pour corriger la case trois, elle monte vers quatre puis huit. Copier la descente dans la correction ferait modifier B deux, qui ne contient pas trois, et oublierait B quatre et B huit, qui la contiennent. Nora note donc deux gestes inverses par leur signe, sans les tenir pour une même promenade à réutiliser indifféremment. La question lit une partition antérieure ; la correction modifie des blocs englobants.
Remplacer un compte demande un écart, pas la nouvelle valeur entière
Dans une branche repartant des comptes initiaux, Nora remplace le trois de la case trois par sept. L'écart à transmettre vaut quatre. Camille ajoute donc quatre aux seules entrées trois, quatre, huit, qui deviennent sept, dix, vingt-deux. Une transmission de sept comme ajout aurait donné dix à la case trois, car les anciens trois seraient restés dans tous ces blocs. Nora refuse ce résultat avant d'effectuer les questions. Le nouveau nombre remis par la correction est une valeur de case ; le geste de la structure attend une différence avec l'ancienne valeur, et non une seconde copie de ce nombre.
Si Nora n'avait pas gardé le compte individuel précédent, Camille pourrait le retrouver par différence de deux préfixes : somme jusqu'à trois moins somme jusqu'à deux. La feuille initiale donnait six moins trois, donc trois. Elle forme alors sept moins trois et transmet quatre. Cette récupération doit précéder la montée de correction ; lire les préfixes après l'ajout entier de sept retrouverait déjà une autre valeur et ne réparerait pas automatiquement l'erreur. Nora garde les deux lectures, l'écart calculé et les trois blocs modifiés dans cet ordre. Elle ne donne pas à une opération d'ajout le sens d'une affectation par simple changement de légende.
Trouver la neuvième unité choisit la première borne qui l'atteint
Camille revient encore aux comptes initiaux, tous non négatifs. Elle développe seulement pour contrôle les sommes cumulées : deux, trois, six, six, dix, douze, treize, dix-huit. Nora demande la case contenant la neuvième unité si les unités sont rangées dans l'ordre des cases. La réponse est cinq, puisque le préfixe quatre n'en possède que six et le préfixe cinq en possède dix. Une case de compte zéro n'occupe aucune unité dans cette liste. La demande porte sur une unité numérotée à partir de un, pas sur la neuvième case d'une feuille qui n'en possède que huit.
Pour trouver cette borne depuis les blocs, Camille part avant la case un avec un reste neuf. Elle essaie d'abord le bloc complet finissant à huit : dix-huit n'est pas strictement inférieur à neuf, elle ne le saute pas. Elle essaie ensuite B quatre, six : ce bloc est insuffisant, elle passe après quatre et retire six du reste, qui devient trois. À partir de là, B six couvre précisément les deux cases suivantes, cinq-six. Sa valeur six atteint déjà le reste ; Camille ne saute donc pas jusqu'à six. Le dernier essai B cinq vaut quatre, qui atteint encore trois. La première case non sautée est cinq, la réponse annoncée.
Ces essais utilisent les tailles huit, quatre, deux, un successivement. Quand une taille est essayée, la borne déjà sautée est alignée sur le double de cette taille ; l'entrée candidate représente donc exactement le bloc de cette taille placé après elle. Camille peut comparer sa somme au reste sans relire un préfixe complet pour chaque essai. Si le bloc est insuffisant, elle le consomme et réduit le reste ; sinon elle conserve la borne et essaie une moitié. Nora garde cet alignement avec le calcul de neuf. Une entrée prise à une borne arbitraire ne représenterait pas forcément la portion nouvelle que l'essai prétend ajouter.
Pour l'unité six, le plateau des sommes cumulées impose une attention différente. Les cases trois et quatre finissent toutes deux à six. La première qui atteint le rang est trois. B quatre vaut exactement six : Camille ne doit pas le sauter, car le saut exige une somme strictement inférieure au reste. Elle passe après deux, dont le bloc vaut trois, puis s'arrête devant trois, dont le compte trois atteint le reste trois. Remplacer le test strict par « inférieur ou égal » ferait sauter quatre et annoncer une borne trop tardive. Nora remet trois, même si la case quatre possède la même somme à sa fin.
Les comptes négatifs gardent les sommes, mais retirent cette sélection
Une autre feuille reçoit cinq, moins quatre, cinq. Ses sommes cumulées valent cinq, un, six. La première borne qui atteint quatre est un. Pourtant, la procédure de saut essaie le bloc finissant à deux, de somme un, le juge insuffisant et le consomme. Elle arrive alors devant trois et remet trois. Le calcul a sauté un préfixe contenant déjà la réponse, parce que la somme à sa fin était redescendue sous le rang. Nora refuse cette sélection sur les comptes signés. Elle ne transforme pas moins quatre en zéro pour faire réussir l'ancienne règle tout en prétendant conserver les données reçues.
Les lectures et corrections de sommes restent néanmoins valides sur cette feuille. B un vaut cinq, B deux un, B trois cinq ; lire trois additionne B trois et B deux et rend six. Ajouter deux à la deuxième case modifie B deux et produit le nouveau total huit. Aucune de ces opérations n'exige que les sommes cumulées soient croissantes ; elles exigent seulement les mêmes additions et soustractions sur les intervalles conservés. Nora retire donc seulement la méthode de sélection par saut, dont la preuve utilisait la monotonie. Elle garde une distinction précise entre la possibilité de calculer une somme signée et celle de localiser un rang d'unités par ces mêmes blocs.
Augmenter une portion entière se traduit par deux frontières
La dernière commande revient aux huit comptes initiaux et ajoute deux aux cases trois à six incluses. Les nouvelles valeurs sont deux, un, cinq, deux, six, quatre, un, cinq. Pour représenter cette modification autrement que par quatre corrections séparées, Nora prépare les différences entre comptes consécutifs : deux, moins un, deux, moins trois, quatre, moins deux, moins un, quatre. La somme de ces différences jusqu'à une case retrouve son compte individuel. Camille ne confond pas cette nouvelle suite signée avec les comptes d'unités tous non négatifs qui servaient à la précédente sélection.
Ajouter deux à toute la portion se traduit par deux changements dans les différences : plus deux à la position trois, moins deux à sept. À l'entrée de la portion, les sommes cumulées des différences gagnent deux ; après sa sortie, le second changement annule ce gain. La différence de trois passe de deux à quatre, celle de sept de moins un à moins trois. Les autres restent identiques. Nora vérifie ainsi cinq à la case trois, quatre à six et un à sept. Sans le retrait à sept, les deux cases sept et huit gagneraient également deux ; l'opération aurait augmenté un suffixe entier au lieu de la portion demandée.
Une structure de sommes partielles sur ces différences peut retrouver le compte d'une case, mais pas directement la somme des comptes d'un préfixe. Après modification, la somme des différences jusqu'à sept vaut seulement un, le compte de la case sept. Le préfixe des comptes vaut pourtant vingt et un. Nora refuse donc de garder la question « jusqu'à sept » en changeant silencieusement ce qu'elle additionne. La représentation par différences a rendu la correction courte, mais elle demande une seconde transformation avant de répondre à la somme des comptes. La réussite des deux changements de frontière n'avait pas conservé le sens de chaque lecture ancienne.
Une seconde somme pondérée rend les préfixes des comptes
Nora note D i la différence à la position i. Dans un préfixe de k comptes, cette différence participe au compte i, puis aux suivants jusqu'à k : elle est donc ajoutée k moins i plus un fois. Le total demandé vaut la somme de ces multiplicités fois D i. Camille réécrit chaque multiplicité comme k moins la quantité i moins un, cette dernière quantité étant prise entière entre parenthèses. Elle peut alors prendre k fois la somme des D i, puis retirer la somme des produits i moins un fois D i. Deux structures séparées conservent ces deux sommes sur les mêmes positions.
Sur la feuille corrigée, à la borne sept, la première somme vaut un. La seconde vaut moins quatorze : zéro fois deux, une fois moins un, deux fois quatre, trois fois moins trois, quatre fois quatre, cinq fois moins deux, six fois moins trois. Le total pondéré est moins un plus huit moins neuf plus seize moins dix moins dix-huit. Camille calcule donc sept fois un moins moins quatorze, soit vingt et un. Nora vérifie également par addition des sept comptes, deux plus un plus cinq plus deux plus six plus quatre plus un. Les deux réponses coïncident, tandis que la seule première somme un avait manqué la commande.
La correction de frontière doit désormais modifier les deux structures avec des quantités différentes. À trois, la première reçoit deux et la seconde deux fois deux, quatre. À sept, la première reçoit moins deux et la seconde six fois moins deux, moins douze. Les montées de blocs utilisent les mêmes indices, mais leurs valeurs ajoutées diffèrent. Nora refuse une copie qui transmettrait deux puis moins deux aux deux structures : elle représenterait les différences ordinaires deux fois, sans avoir constitué les produits nécessaires à la seconde somme. Camille garde donc les facteurs deux et six auprès des frontières, avant de monter dans les blocs englobants.
Avant correction, la première somme à sept valait déjà un ; la seconde valait moins six et donnait treize. Les modifications pondérées quatre moins douze l'ont fait diminuer de huit, jusqu'à moins quatorze. Sept fois un moins cette nouvelle somme augmente donc de huit, exactement deux ajouté à quatre cases. Nora peut expliquer pourquoi le compte final de sept ne change pas alors que la somme jusqu'à sept augmente. Les deux changements de frontière s'annulent dans la première lecture, mais leurs poids différents ne s'annulent pas dans la seconde. Conserver seulement leur somme nulle aurait effacé l'effet que la commande voulait précisément obtenir.
Pour les cases trois à sept, Camille calcule enfin vingt et un moins le préfixe deux, resté trois : dix-huit. Elle remet cette portion sous la commande d'augmentation trois à six, distincte de l'ancienne correction d'une seule case trois. Le droit d'ajouter à une portion n'impose pas d'ajouter encore aux anciennes feuilles qui servaient aux autres exemples. Nora garde une suite de différences et ses deux regroupements propres à cette dernière branche. Les résultats douze de la première correction et dix-huit de la dernière ne décrivent pas la même modification reçue, même si leur question possède les mêmes bornes.
Les catégories citées n'apportent aucune règle binaire ou somme pondérée à ces opérations sur papier.