Quel est cet article?

L'utilisation d'arbres de segments peut être considérée comme une méthode pour obtenir rapidement le kème plus petit nombre d'un ensemble dans lequel des nombres sont ajoutés ou supprimés. Au début, je n'ai pas bien compris cette explication, alors je la vide.

Connaissances préalables

RSQ à l'aide de l'arborescence de segments. Ce qui suit est très facile à comprendre. Bien que ce soit une explication du RMQ, l'idée est à environ 95% la même pour Min et Sum. https://www.creativ.xyz/segment-tree-entrance-999/

RSQ lui-même n'est pas une structure de données dont le but est d'obtenir la kème plus petite valeur, mais cela peut être réalisé à grande vitesse en utilisant RSQ.

Le problème que vous souhaitez résoudre

ARC033C: Structure des données

Traitez la requête suivante pour l'ensemble de nombres S. --Type 1: ajoutez le nombre X à S. '' --Type 2: Répondez au Xe plus petit nombre de S et supprimez ce nombre de S. '' --Contraintes: 1 <= N, <= 200 000 --Point 1: le même numéro n'est pas ajouté à S

point

N est une valeur relativement petite. Cette contrainte est due à la contrainte de mémoire lors de la création d'un arbre de segments de $ len (N) $ et à la contrainte que O (N) est toujours appliqué à l'initialisation.

Dichotomie de l'arbre à segments RSQ

Par exemple, pensez à obtenir le troisième plus petit nombre de $ [2, 3, 5, 7] $.

Tout d'abord, définissez la valeur dans l'arborescence des segments avec $ index $ de chaque nombre comme $ 1 $. (À l'intérieur du carré sur la figure) Étant donné la requête RSQ $ [0, i) $, elle ressemble à la valeur sous la boîte.

En regardant cela, nous pouvons voir que le premier i (le plus à gauche) pour lequel la requête $ [0, i) $ = k est la valeur que nous voulons obtenir (le kème plus petit nombre).

Si vous obtenez $ i $ qui satisfait la requête la plus à gauche $ [0, i) $ = k, il est évident que l'index de i est la valeur que vous voulez obtenir. Par la suite, cette méthode sera considérée.

Méthode 1: exécutez la requête dans une recherche de 2 minutes pour trouver le k O le plus à gauche (log ^ 2 N)

Premièrement, la méthode décrite dans l'explication de ARC033 peut être considérée.

Profitant du fait que la quantité de calcul requise pour RSQ est au plus O (logN), il est possible de commencer par la requête [0, N) et d'effectuer une dichotomie comme la requête [0, milieu) pour obtenir l'index le plus à gauche. C'est réaliste.

Dans cette méthode, le montant du calcul du RSQ $ O (logN) $ est multiplié par le montant du calcul de la dichotomie $ O (logN) $, donc le total est $ O (log ^ 2N) $.

def segmentTreeBisectLeft(segTreeTarget: segmentTreeSum, x):
    lo, hi = 0, st.lenOriginalList
    while lo < hi:
        mid = (lo+hi)//2
        if segTreeTarget.query(0, mid + 1) < x: lo = mid + 1 #RSQ ici[0,mid)Requete
        else: hi = mid
    return lo

Méthode 2: Creusez un arbre de segments avec une recherche de 2 minutes pour trouver le k O le plus à gauche (log N)

Ici, considérons find (x, n) qui recherche le plus petit x géré sous le nœud n en utilisant la structure arborescente de l'arborescence de segments. Ensuite, en utilisant l'exemple d'entrée ci-dessus, l'opération lorsque vous souhaitez connaître le troisième plus petit nombre est affichée, et chaque opération est décrite.

--1: Entrée au nœud racine 0 (find (3, 0) -2: Passez find (3, 1) au nœud gauche 1 —— 3: Si le nœud a une valeur plus petite que le x reçu, il soustrait la valeur du nœud et la renvoie à son parent. Dans l'exemple, x = 3 moins son propre 2 est renvoyé au nœud 0. En effet, si vous voulez trouver le xième plus petit nombre mais que vous ne gérez que les nœuds x-a sous votre contrôle, il n'y a aucun nœud que vous souhaitez trouver sous votre contrôle. --4: Le nœud racine 0 renvoie 1 du nœud 1 à gauche, utilisez donc cette valeur pour envoyer find (1, 2) au nœud 2 à droite.

1. Le nœud 2 envoie find (1,5) au nœud 5 sur la gauche. ―― 6. Le nœud 5 envoie find (1, 11) au nœud 11 sur la gauche. Cette feuille n'a pas de valeur, elle renvoie donc None. ―― 7. Le nœud 5 envoie find (1, 12) au nœud 11 sur la gauche. ―― 8: Cette feuille correspond à x. Cela renvoie index = 5. Cela exigeait que la fonction ait la kième plus petite valeur de 5.

def findNthValueSub(self, x, nodeId):
    """
    [2, 3, 5, 7] = [0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0]
Fonction pour obtenir la xème plus petite valeur de l'arborescence des segments mappée sur
    """
    #À partir de là, traitement vers des nœuds qui ne sont pas des feuilles
    if self.dat[nodeId] < x: #Lorsque ce nœud a une valeur inférieure à celle demandée
        return (None, x - self.dat[nodeId])
    if nodeId >= self.lenTreeList - 1: #Lorsque nodeIf est un nœud
        return (True, nodeId - (self.lenTreeList - 1)) #Renvoie son numéro d'index
    resLeft = self.findNthValueSub(x, 2 * nodeId + 1) #Faites une recherche sur la gauche
    if resLeft[0] != None: #S'il y a une valeur, renvoyez-la
        return (True, resLeft[1])
    resRight = self.findNthValueSub(resLeft[1], 2 * nodeId + 2) #Faites une recherche sur la droite
    return resRight

Explication détaillée

https://www.slideshare.net/chokudai/arc033 https://ei1333.hateblo.jp/entry/2017/12/14/000000

Code source complet

https://github.com/recuraki/PythonJunkTest/blob/master/atcoder/lib/treeSegment/segmentTreeSum.py

[PYTHON] Obtenez le nième plus petit nombre du tableau avec O (logN) en utilisant une arborescence de segments