data-structures
Arbre segment
Recherche…
Introduction à l'arbre du segment
Supposons que nous ayons un tableau:
+-------+-----+-----+-----+-----+-----+-----+
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
+-------+-----+-----+-----+-----+-----+-----+
| Value | -1 | 3 | 4 | 0 | 2 | 1 |
+-------+-----+-----+-----+-----+-----+-----+
Nous voulons effectuer une requête sur ce tableau. Par exemple:
- Quel est le minimum de l'index 2 à l'index 4 ? -> 0
- Quel est le maximum de l'index 0 au index 3 ? -> 4
- Quelle est la somme de l'index 1 à l'index 5 ? -> 10
Comment le découvrons-nous?
Force brute:
Nous pourrions parcourir le tableau de l'index de départ à l'index de finition et répondre à notre requête. Dans cette approche, chaque requête prend O(n) time où n est la différence entre l'index de départ et l'index de finition. Mais que se passe-t-il s'il y a des millions de chiffres et des millions de requêtes? Pour les requêtes m, il faudrait O(mn) temps. Donc, pour 10 valeurs dans notre tableau, si nous effectuons 10 requêtes, dans le pire des cas, nous devrons parcourir 10 éléments.
Programmation dynamique:
Nous pouvons créer une matrice 6X6 pour stocker les valeurs pour différentes plages. Pour la requête minimum (RMQ), notre tableau ressemblerait à ceci:
0 1 2 3 4 5
+-----+-----+-----+-----+-----+-----+-----+
| | -1 | 3 | 4 | 0 | 2 | 1 |
+-----+-----+-----+-----+-----+-----+-----+
0 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
+-----+-----+-----+-----+-----+-----+-----+
1 | 3 | | 3 | 3 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
2 | 4 | | | 4 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
3 | 0 | | | | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
4 | 2 | | | | | 2 | 1 |
+-----+-----+-----+-----+-----+-----+-----+
5 | 1 | | | | | | 1 |
+-----+-----+-----+-----+-----+-----+-----+
Une fois que cette matrice aura été construite, il suffira de répondre à tous les RMQ. Ici, la matrice [i] [j] stockera la valeur minimale de l'index- i à l'index- j . Par exemple: Le minimum entre index 2 et index 4 est Matrix [2] [4] = 0 . Cette matrice répond à la requête en temps O(1) , mais il faut O (n²) temps pour construire cette matrice et O(n²) pour la stocker. Donc, si n est un très grand nombre, cela ne va pas très bien.
Arbre de segment:
Une arborescence de segments est une structure de données arborescente permettant de stocker des intervalles ou des segments. Il permet d'interroger les segments stockés contenant un point donné. Il faut du temps O(n) pour construire une arborescence de segments, il faut de l'espace O(n) pour le maintenir et il répond à une requête en temps O(logn) .
L'arbre de segment est un arbre binaire et les éléments du tableau donné seront les feuilles de cet arbre. Nous allons créer l'arborescence des segments en divisant le tableau en deux jusqu'à ce que nous atteignions un seul élément. Donc, notre division nous fournirait:
Maintenant, si nous remplaçons les nœuds non-feuilles par la valeur minimale de leurs feuilles, nous obtenons:
Donc, voici notre arbre de segment. On peut remarquer que le nœud racine contient la valeur minimale de tout le tableau (plage [0,5]), son enfant gauche contient la valeur minimum de notre tableau gauche (plage [0,2]), enfant droit contient le minimum valeur de notre tableau droit (plage [3,5]) et ainsi de suite. Les nœuds feuilles contiennent la valeur minimale de chaque point individuel. On a:
Maintenant, faisons une requête sur cette arborescence. Pour effectuer une requête de plage, nous devons vérifier trois conditions:
- Chevauchement partiel: Nous vérifions les deux feuilles.
- Total Overlap: Nous retournons la valeur stockée dans le nœud.
- Pas de chevauchement: nous retournons une très grande valeur ou un infini.
Disons que nous voulons vérifier l'intervalle [2,4] , cela signifie que nous voulons trouver le minimum de l'index 2 à 4 . Nous allons commencer à partir de la racine et vérifier si la plage dans nos nœuds est chevauchée par notre plage de requêtes ou non. Ici,
- [2,4] ne se chevauchent pas complètement [0,5] . Nous allons donc vérifier les deux directions.
- Au sous-arbre de gauche, [2,4] chevauche partiellement [0,2] . Nous allons vérifier les deux directions.
- Au sous-arbre de gauche, [2,4] ne se chevauche pas [0,1] , cela ne va donc pas contribuer à notre réponse. Nous retournons à l' infini .
- Au sous-arbre de droite, [2,4] chevauche totalement [2,2] . Nous revenons 4 .
Le minimum de ces deux valeurs renvoyées (4, infini) est 4 . Nous obtenons 4 de cette portion.
- Au sous-arbre de droite, [2,4] se chevauche partiellement. Nous allons donc vérifier les deux directions.
- Au sous-arbre de gauche, [2,4] recouvre complètement [3,4] . Nous retournons 0 .
- Au sous-arbre de droite, [2,4] ne se chevauche pas [5,5] . Nous retournons à l' infini .
Le minimum de ces deux valeurs renvoyées (0, infini) est 0 . Nous obtenons 0 de cette partie.
- Au sous-arbre de gauche, [2,4] chevauche partiellement [0,2] . Nous allons vérifier les deux directions.
- Le minimum des valeurs renvoyées (4,0) est 0 . Ceci est notre minimum souhaité dans la gamme [2,4] .
Maintenant, nous pouvons vérifier que, quelle que soit notre requête, il faut au maximum 4 étapes pour trouver la valeur souhaitée à partir de cette arborescence de segment.
Utilisation:
- Intervalle minimum de requête
- Ancêtre commun le plus bas
- Propagation paresseuse
- Somme de sous-arbre dynamique
- Négligence & min
- Deux champs
- Trouver le plus petit élément k
- Trouver le nombre de paires non ordonnées
Implémentation de l'arborescence de segments à l'aide d'un tableau
Disons que nous avons un tableau: Item = {-1, 0, 3, 6} . Nous voulons construire un tableau SegmentTree pour trouver la valeur minimale dans une plage donnée. Notre arborescence de segments ressemblera à:
Les chiffres sous les noeuds indiquent les indices de chaque valeur que nous allons stocker dans notre tableau SegmentTree . Nous pouvons voir que pour stocker 4 éléments, nous avions besoin d'un tableau de taille 7. Cette valeur est déterminée par:
Procedure DetermineArraySize(Item):
multiplier := 1
n := Item.size
while multiplier < n
multiplier := multiplier * 2
end while
size := (2 * multiplier) - 1
Return size
Donc, si nous avions un tableau de longueur 5, la taille de notre tableau SegmentTree serait: ( 8 * 2 ) - 1 = 15 . Maintenant, pour déterminer la position de l'enfant gauche et droit d'un noeud, si un noeud est dans l'index i , alors la position de son:
- Left Child est noté par: (2 * i) + 1 .
- Right Child est désigné par: (2 * i) + 2 .
Et i peuvent être déterminées par l'indice du parent d'un noeud quelconque de l'indice (i - 1) / 2.
Le tableau SegmentTree représentant notre exemple ressemblerait donc à ceci :
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 3 | -1 | 0 | 3 | 6 |
+-----+-----+-----+-----+-----+-----+-----+
Regardons le pseudo-code pour construire ce tableau:
Procedure ConstructTree(Item, SegmentTree, low, high, position):
if low is equal to high
SegmentTree[position] := Item[low]
else
mid := (low+high)/2
constructTree(Item, SegmentTree, low, mid, 2*position+1)
constructTree(Item, SegmentTree, mid+1, high, 2*position+2)
SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
end if
Au début, nous saisissons les valeurs et initialisons le tableau SegmentTree avec l' infinity utilisant la longueur du tableau Item comme taille. Nous appelons la procédure en utilisant:
- low = Index de départ du tableau Item .
- high = Index de fin du tableau Item .
- position = 0, indique la racine de notre arbre de segment.
Maintenant, essayons de comprendre la procédure en utilisant un exemple: 
La taille de notre tableau d' article est 4 . Nous créons un tableau de longueur (4 * 2) - 1 = 7 et les initialisons avec l' infinity . Vous pouvez utiliser une très grande valeur pour cela. Notre tableau ressemblerait à ceci:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | inf | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Comme il s'agit d'une procédure récursive, nous allons voir le fonctionnement de ConstructTree utilisant une table de récurrence qui garde trace de la ligne low , high , position , mid et calling line à chaque appel. Au début, nous appelons ConstructTree (Item, SegmentTree, 0, 3, 0) . Ici, low n'est pas identique à high , nous aurons un mid . La calling line indique quel ConstructTree est appelé après cette instruction. Nous notons les appels ConstructTree dans la procédure en 1 et 2 respectivement. Notre table ressemblera à:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
Donc, lorsque nous appelons ConstructTree-1 , nous passons: low = 0 , high = mid = 1 , position = 2*position+1 = 2*0+1 = 1 . Une chose que vous pouvez remarquer, c'est que 2*position+1 est l'enfant gauche de root , qui est 1 . Comme low n’est pas égal à high , on obtient un mid . Notre table ressemblera à:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
Au prochain appel récursif, nous passons low = 0 , high = mid = 0 , position = 2*position+1 = 2*1+1=3 . Encore une fois, l’enfant gauche de l’index 1 est 3 . Ici, low est e high , nous définissons donc SegmentTree[position] = SegmentTree[3] = Item[low] = Item[0] = -1 . Notre tableau SegmentTree ressemblera à ceci :
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | -1 | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Notre table de récurrence ressemblera à ceci:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 0 | 3 | | |
+-----+------+----------+-----+--------------+
Donc, vous pouvez voir que -1 a sa position correcte. Comme cet appel récursif est terminé, nous revenons à la ligne précédente de notre table de récurrence. La table:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 1 |
+-----+------+----------+-----+--------------+
Dans notre procédure, nous exécutons l'appel ConstructTree-2 . Cette fois, nous passons low = mid+1 = 1 , high = 1 , position = 2*position+2 = 2*1+2 = 4 . Notre calling line change à 2 . On a:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
Puisque low est égal à high , nous définissons: SegmentTree[position] = SegmentTree[4] = Item[low] = Item[1] = 2 . Notre tableau SegmentTree :
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | inf | inf | -1 | 2 | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Notre table de récursivité:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
| 1 | 1 | 4 | | |
+-----+------+----------+-----+--------------+
Encore une fois, vous pouvez voir que 2 a sa position correcte. Après cet appel récursif, nous revenons à la ligne précédente de notre table de récurrence. On a:
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 1 |
+-----+------+----------+-----+--------------+
| 0 | 1 | 1 | 0 | 2 |
+-----+------+----------+-----+--------------+
Nous exécutons la dernière ligne de notre procédure, SegmentTree[position] = SegmentTree[1] = min(SegmentTree[2*position+1], SegmentTree[2*position+2]) = min(SegmentTree[3], SegmentTree[4]) = min(-1,2) = -1 . Notre tableau SegmentTree :
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| inf | -1 | inf | -1 | 2 | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+
Comme cet appel de récursivité est terminé, nous revenons à la ligne précédente de notre table de récurrence et appelons ConstructTree-2 :
+-----+------+----------+-----+--------------+
| low | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
| 0 | 3 | 0 | 1 | 2 |
+-----+------+----------+-----+--------------+
Nous pouvons voir que la partie gauche de notre arborescence de segments est complète. Si nous continuons de cette manière, après avoir terminé toute la procédure, nous aurons enfin un tableau SegmentTree terminé, qui ressemblera à ceci:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 0 | -1 | 2 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
La complexité en temps et en espace de la construction de ce tableau SegmentTree est la suivante: O(n) , où n désigne le nombre d'éléments du tableau Item . Notre tableau SegmentTree construit peut être utilisé pour effectuer une requête minimum (Range Minimum Query) . Pour construire un tableau pour exécuter une requête de plage maximale , nous devons remplacer la ligne:
SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
avec:
SegmentTree[position] := max(SegmentTree[2*position+1], SegmentTree[2*position+2])
Exécution d'une requête minimum d'intervalle
La procédure d'exécution d'un RMQ est déjà présentée en introduction. Le pseudo-code pour vérifier l'interrogation minimale de la plage sera:
Procedure RangeMinimumQuery(SegmentTree, qLow, qHigh, low, high, position):
if qLow <= low and qHigh >= high //Total Overlap
Return SegmentTree[position]
else if qLow > high || qHigh < low //No Overlap
Return infinity
else //Partial Overlap
mid := (low+high)/2
Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
end if
Ici, qLow = The lower range of our query , qHigh = The upper range of our query . low = starting index of Item array , high = Finishing index of Item array , position = root = 0 . Essayons maintenant de comprendre la procédure en utilisant l'exemple que nous avons créé précédemment:
Notre tableau SegmentTree :
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 0 | -1 | 2 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
Nous voulons trouver le minimum dans la plage [1,3] .
Comme il s'agit d'une procédure récursive, nous verrons le fonctionnement de RangeMinimumQuery aide d'une table de récurrence qui garde trace de qLow , qHigh , low , high , position , mid et calling line . Au début, nous appelons RangeMinimumQuery (SegmentTree, 1, 3, 0, 3, 0. Ici, les deux premières conditions ne sont pas remplies (chevauchement partiel). Nous aurons un mid . La calling line indique quel RangeMinimumQuery est appelé après cela. On notera les appels RangeMinimumQuery dans la procédure en 1 et 2 respectivement. Notre tableau ressemblera à RangeMinimumQuery :
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Ainsi, lorsque nous appelons RangeMinimumQuery-1 , nous passons: low = 0 , high = mid = 1 , position = 2*position+1 = 1 . Une chose que vous pouvez remarquer, c'est que 2*position+1 est l'enfant gauche d'un nœud . Cela signifie que nous vérifions l'enfant gauche de root . Puisque [1,3] chevauche partiellement [0,1] , les deux premières conditions ne sont pas remplies, nous obtenons un mid . Notre table:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Dans l'appel récursif suivant, nous passons low = 0 , high = mid = 0 , position = 2*position+1 = 3 . Nous atteignons la feuille la plus à gauche de notre arbre. Puisque [1,3] ne chevauche pas [0,0] , nous retournons l' infinity dans notre fonction d'appel. Table de récurrence:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 0 | 3 | | |
+------+-------+-----+------+----------+-----+--------------+
Comme cet appel récursif est terminé, nous revenons à la ligne précédente de notre table de récurrence. On a:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Dans notre procédure, nous RangeMinimumQuery-2 appel RangeMinimumQuery-2 . Cette fois, on passe low = mid+1 = 1 , high = 1 et position = 2*position+2 = 4 . Notre calling line changes to **2** . On a:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 2 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 1 | 1 | 4 | | |
+------+-------+-----+------+----------+-----+--------------+
Nous allons donc au bon enfant du nœud précédent. Cette fois, il y a un chevauchement total. Nous SegmentTree[position] = SegmentTree[4] = 2 la valeur SegmentTree[position] = SegmentTree[4] = 2 .
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
De retour à la fonction d'appel, nous vérifions quel est le minimum des deux valeurs renvoyées de deux fonctions d'appel. Evidemment le minimum est 2 , nous retournons 2 à la fonction appelante. Notre table de récurrence ressemble à:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Nous avons fini de regarder la partie gauche de notre arborescence. Nous allons maintenant appeler RangeMinimumQuery-2 partir d'ici. Nous passerons low = mid+1 = 1+1 =2 , high = 3 et position = 2*position+2 = 2 . Notre table:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 2 | 3 | 2 | | |
+------+-------+-----+------+----------+-----+--------------+
Il y a un chevauchement total. Nous SegmentTree[position] = SegmentTree[2] = 0 donc la valeur: SegmentTree[position] = SegmentTree[2] = 0 . Nous revenons à la récursivité à partir de laquelle ces deux enfants ont été appelés et obtenons le minimum de (4,0) , soit 0, et retournons la valeur.
Après avoir exécuté la procédure, nous obtenons 0 , qui est le minimum de l'index 1 à l'index 3 .
La complexité d'exécution pour cette procédure est O(logn) où n est le nombre d'éléments du tableau Items . Pour effectuer une requête de plage maximale, nous devons remplacer la ligne:
Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
avec:
Return max(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
Propagation paresseuse
Disons que vous avez déjà créé une arborescence de segments. Vous devez mettre à jour les valeurs du tableau, cela ne changera pas seulement les nœuds feuilles de votre arborescence de segments, mais également le minimum / maximum dans certains nœuds. Regardons ceci avec un exemple:
Ceci est notre arborescence de segments minimum de 8 éléments. Pour vous rappeler rapidement, chaque nœud représente la valeur minimale de la plage mentionnée à côté d'eux. Disons que nous voulons augmenter la valeur du premier élément de notre tableau de 3 . Comment peut-on faire ça? Nous suivrons la façon dont nous avons mené RMQ. Le processus ressemblerait à ceci:
- Au début, nous parcourons la racine. [0,0] recouvre partiellement avec [0,7] , nous allons dans les deux sens.
- Au sous-arbre de gauche, [0,0] recouvre partiellement avec [0,3] , nous allons dans les deux directions.
- Au sous-arbre de gauche, [0,0] recouvre partiellement avec [0,1] , nous allons dans les deux directions.
- Au sous-arbre de gauche, [0,0] recouvre totalement [0,0] , et puisque c'est le nœud feuille, nous mettons à jour le nœud en l’augmentant de 3 . Et renvoyer la valeur -1 + 3 = 2 .
- Au sous-arbre de droite, [1,1] ne chevauche pas [0,0] , nous renvoyons la valeur au noeud ( 2 ).
Le minimum de ces deux valeurs renvoyées ( 2 , 2 ) est 2 , nous mettons donc à jour la valeur du nœud actuel et la renvoyons.
- À droite, le sous-arbre [2,3] ne chevauche pas [0,0] , nous renvoyons la valeur du noeud. ( 1 ).
Puisque le minimum de ces deux valeurs renvoyées ( 2 , 1 ) est 1 , nous mettons à jour la valeur du nœud actuel et la renvoyons.
- Au sous-arbre de gauche, [0,0] recouvre partiellement avec [0,1] , nous allons dans les deux directions.
- À droite, le sous-arbre [4,7] ne chevauche pas [0,0] , nous renvoyons la valeur du noeud. ( 1 ).
- Au sous-arbre de gauche, [0,0] recouvre partiellement avec [0,3] , nous allons dans les deux directions.
- Enfin, la valeur du nœud racine est mise à jour car le minimum des deux valeurs renvoyées (1,1) est 1 .
Nous pouvons voir que la mise à jour d'un seul nœud nécessite une complexité temporelle O(logn) , où n est le nombre de nœuds feuilles. Donc, si on nous demande de mettre à jour certains nœuds de i à j , nous aurons besoin de la complexité temporelle O(nlogn) . Cela devient lourd pour une grande valeur de n . Soyons fainéants, c'est-à-dire ne travaillons que lorsque cela est nécessaire. Comment? Lorsque nous avons besoin de mettre à jour un intervalle, nous allons mettre à jour un nœud et marquer son enfant qu'il doit être mis à jour et le mettre à jour si nécessaire. Pour cela, nous avons besoin d'un tableau paresseux de la même taille que celui d'une arborescence de segments. Au départ, tous les éléments du tableau paresseux seront 0, ce qui signifie qu’il n’ya pas de mise à jour en attente. S'il y a un élément non nul dans lazy [i] , alors cet élément doit mettre à jour le nœud i dans l'arborescence des segments avant d'effectuer des opérations de requête. Comment allons-nous faire ça? Regardons un exemple:
Disons que, pour notre exemple d'arbre, nous voulons exécuter certaines requêtes. Ceux-ci sont:
- incrémenter [0,3] de 3 .
- incrémente [0,3] de 1 .
- incrémenter [0,0] de 2 .
incrémenter [0,3] de 3:
Nous partons du nœud racine. Au début, nous vérifions si cette valeur est à jour. Pour cela, nous vérifions notre tableau paresseux qui est 0 , ce qui signifie que la valeur est à jour. [0,3] recouvre partiellement [0,7] . Nous allons donc dans les deux directions.
- Dans le sous-arbre de gauche, il n'y a pas de mise à jour en attente. [0,3] se chevauchent totalement [0,3] . Nous mettons donc à jour la valeur du noeud par 3 . La valeur devient donc -1 + 3 = 2 . Cette fois, nous n'allons pas aller jusqu'au bout. Au lieu de descendre, nous mettons à jour l'enfant correspondant dans l'arbre paresseux de notre nœud actuel et nous l'incrémentons de 3 . Nous renvoyons également la valeur du nœud actuel.
- Au sous-arbre de droite, il n'y a pas de mise à jour en attente. [0,3] ne se chevauche pas [4,7] . Nous renvoyons donc la valeur du nœud actuel (1) .
Le minimum de deux valeurs renvoyées ( 2 , 1 ) est 1 . Nous mettons à jour le noeud racine à 1 .
Notre arbre de segment et arbre paresseux ressemblerait à ceci:
Les valeurs non nulles dans les nœuds de notre arbre paresseux représentent, il y a des mises à jour en attente dans ces nœuds et ci-dessous. Nous les mettrons à jour si nécessaire. Si on nous demande quel est le minimum de la plage [0,3] , nous arriverons au sous-arbre gauche du nœud racine et comme il n'y a pas de mises à jour en attente, nous retournerons 2 , ce qui est correct. Donc, ce processus n'affecte pas l'exactitude de notre algorithme d'arborescence de segments.
incrémenter [0,3] par 1:
- Nous partons du nœud racine. Il n'y a pas de mise à jour en attente. [0,3] recouvre partiellement [0,7] . Nous allons donc dans les deux sens.
- Dans le sous-arbre de gauche, il n'y a pas de mise à jour en attente. [0,3] chevauche complètement [0,3] . Nous mettons à jour le nœud actuel: 2 + 1 = 3 . Comme il s’agit d’un nœud interne, nous mettons à jour ses enfants dans l’arbre paresseux pour les incrémenter de 1 . Nous allons également retourner la valeur du nœud actuel ( 3 ).
- Dans le bon sous-arbre, il n'y a pas de mise à jour en attente. [0,3] ne se chevauche pas [4,7] . Nous retournons la valeur du nœud actuel ( 1 ).
- Nous mettons à jour le nœud racine en prenant le minimum de deux valeurs renvoyées ( 3 , 1 ).
Notre arborescence de segments et notre arbre paresseux ressembleront à:
Comme vous pouvez le constater, nous accumulons les mises à jour à Lazy Tree mais nous ne les réduisons pas. C'est ce que signifie Lazy Propagation. Si nous ne l'avions pas utilisé, nous avons dû réduire les valeurs aux feuilles, ce qui nous aurait coûté plus de temps inutile.
incrémenter [0,0] de 2:
- Nous partons du nœud racine. Puisque root est à jour et que [0,0] se chevauchent partiellement [0,7] , nous allons dans les deux sens.
- Dans le sous-arbre de gauche, le nœud actuel est à jour et [0,0] se chevauche partiellement [0,3] , nous allons dans les deux sens.
- Dans le sous-arbre de gauche, le nœud actuel de l'Arbre paresseux a une valeur différente de zéro. Il y a donc une mise à jour qui n'a pas encore été propagée à ce nœud. Nous allons d'abord mettre à jour ce nœud dans notre arborescence de segments. Donc, cela devient -1 + 4 = 3 . Ensuite, nous allons propager ce 4 à ses enfants dans l'Arbre Paresseux. Comme nous avons déjà mis à jour le nœud actuel, nous modifierons la valeur du nœud actuel dans l'Arbre paresseux à 0 . Alors [0,0] recouvre partiellement [0,1] , nous allons donc dans les deux sens.
- Au nœud de gauche, la valeur doit être mise à jour car il existe une valeur différente de zéro dans le nœud actuel de l'Arbre paresseux. Donc, nous mettons à jour la valeur à -1 + 4 = 3 . Maintenant, puisque [0,0] recouvre totalement [0,0] , nous mettons à jour la valeur du nœud actuel à 3 + 2 = 5 . Ceci est un nœud feuille, nous n'avons donc plus besoin de propager la valeur. Nous mettons à jour le nœud correspondant dans l'arbre paresseux à 0 car toutes les valeurs ont été propagées jusqu'à ce nœud. Nous retournons la valeur du nœud actuel ( 5 ).
- Au bon noeud, la valeur doit être mise à jour. Donc, la valeur devient: 4 + 2 = 6 . Puisque [0,0] ne se chevauche pas [1,1] , nous renvoyons la valeur du nœud actuel ( 6 ). Nous mettons également à jour la valeur dans l'Arbre paresseux à 0 . Aucune propagation n'est nécessaire car il s'agit d'un noeud feuille.
Nous mettons à jour le nœud actuel en utilisant le minimum de deux valeurs renvoyées ( 5 , 6 ). Nous retournons la valeur du nœud actuel ( 5 ).
- Dans le sous-arbre de droite, il y a une mise à jour en attente. Nous mettons à jour la valeur du noeud à 1 + 4 = 5 . Comme il ne s’agit pas d’un nœud feuille, nous propageons la valeur à ses enfants dans notre arbre paresseux et mettons à jour le nœud actuel à 0 . Puisque [0,0] ne chevauche pas avec [2,3] , nous retournons la valeur de notre noeud actuel ( 5 ).
Nous mettons à jour le nœud actuel en utilisant le minimum des valeurs renvoyées ( 5 , 5 ) et retournons la valeur ( 5 ).
- Dans le sous-arbre de gauche, le nœud actuel de l'Arbre paresseux a une valeur différente de zéro. Il y a donc une mise à jour qui n'a pas encore été propagée à ce nœud. Nous allons d'abord mettre à jour ce nœud dans notre arborescence de segments. Donc, cela devient -1 + 4 = 3 . Ensuite, nous allons propager ce 4 à ses enfants dans l'Arbre Paresseux. Comme nous avons déjà mis à jour le nœud actuel, nous modifierons la valeur du nœud actuel dans l'Arbre paresseux à 0 . Alors [0,0] recouvre partiellement [0,1] , nous allons donc dans les deux sens.
- Dans le sous-arbre de droite, il n'y a pas de mise à jour en attente et [0,0] ne se chevauchant pas [4,7] , nous renvoyons la valeur du nœud actuel ( 1 ).
- Dans le sous-arbre de gauche, le nœud actuel est à jour et [0,0] se chevauche partiellement [0,3] , nous allons dans les deux sens.
- Nous mettons à jour le noeud racine en utilisant le minimum des deux valeurs renvoyées ( 5 , 1 ).
Notre arborescence de segments et notre arbre paresseux ressembleront à:
Nous pouvons remarquer que la valeur à [0,0] , si nécessaire, a tous les incréments.
Maintenant, si on vous demande de trouver le minimum dans la plage [3,5] , si vous avez compris jusqu'ici, vous pouvez facilement comprendre comment la requête ira et la valeur renvoyée sera 1 . Notre segment Tree et Lazy Tree ressemblerait à ceci:
Nous avons simplement suivi le même processus que nous avons suivi pour trouver RMQ avec des contraintes supplémentaires de vérification de l'Arbre paresseux pour les mises à jour en attente.
Une autre chose que nous pouvons faire est de renvoyer des valeurs de chaque nœud, puisque nous savons quel sera le nœud enfant de notre nœud actuel, nous pouvons simplement les vérifier pour trouver le minimum de ces deux.
Le pseudo-code pour la mise à jour dans Lazy Propagation serait:
Procedure UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, low, high, position):
if low > high //out of bounds
Return
end if
if LazyTree[position] is not equal to 0 //update needed
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high //non-leaf node
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
end if
LazyTree[position] := 0
end if
if startRange > low or endRange < high //doesn't overlap
Return
end if
if startRange <= low && endRange >= high //total overlap
segmentTree[position] := segmentTree[position] + delta
if low is not equal to high
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
end if
Return
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, low, mid, 2 * position + 1)
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
endRange, delta, mid + 1, high, 2 * position + 2)
segmentTree[position] := min(segmentTree[2 * position + 1],
segmentTree[2 * position + 2])
Et le pseudo-code pour RMQ dans Lazy Propagation sera:
Procedure RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, low, high, position):
if low > high
Return infinity
end if
if LazyTree[position] is not equal to 0 //update needed
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high
segmentTree[position] := segmentTree[position] + LazyTree[position]
if low is not equal to high //non-leaf node
LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + LazyTree[position]
LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + LazyTree[position]
end if
LazyTree[position] := 0
end if
if qLow > high and qHigh < low //no overlap
Return infinity
end if
if qLow <= low and qHigh >= high //total overlap
Return segmentTree[position]
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
Return min(RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
low, mid, 2 * position + 1),
RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
mid + 1, high, 2 * position + 1)