Implémentation Python de l'arborescence de segments non récursive

introduction

Comme son titre l'indique, cet article souhaite vous présenter l'implémentation de ** l'arborescence de segments non récursive ** par ** Python **. Je vais commencer par l'explication de ** Segment Tree ** pour ne pas avoir besoin des connaissances préalables "presque" [^ 1], donc si vous le connaissez déjà, veuillez l'ignorer. → [Implémentation de l'arbre de segment non récursif](#Implémentation de l'arbre de segment non récursif)

[^ 1]: Vous devez comprendre le concept de calcul et la notation Python.

Qu'est-ce que l'arborescence des segments?

Une structure de données communément appelée ** arbre de segment **, ** arbre de segment **, etc., un tableau de longueur $ N $ {$ a_i $} $ _ {i = 0} ^ {N-1} $ Par contre, les deux opérations suivantes liées à ** monoïde ** $ • $ peuvent être effectuées avec un montant de calcul du temps de $ O (logN) $.

• $ update (i, x) $: Changer $ a_i $ en $ x $
• $ query (l, r) $: Renvoie $ a_l • a_ {l + 1} • $… $ • a_ {r-1} $ pour l'intervalle semi-ouvert $ [l, r) $

Considérant l'addition générale comme ** monoïde **, $ query (l, r) $ est la somme des intervalles de $ a_l $ à $ a_ {r-1} $, soit $ \ Sigma_ {i = l} Correspond au résultat de ^ {r-1} a_i $.
Notez que ** monoid ** est un opérateur $ • $ qui satisfait les conditions suivantes.

• Pour tout $ a, b, c $, $ (a • b) • c = a • (b • c) $ (** join law **)
• Un certain $ e $ existe, et pour tout $ a $, $ e • a = a • e = a $ (** L'élément Unit existe **)

Des exemples de ** monoïdes ** incluent les ajouts et multiplications, $ min $ et $ max $.

Dans ce qui suit, ** l'arborescence de segments ** sera expliquée en utilisant l'ajout $ + $ comme exemple de ** monoïde **.
Tout d'abord, en considérant une mise en œuvre simple:

def update(i, x):
    a[i] = x

def query(l, r):
    res = 0
    for i in range(l, r):
        res += a[i]
    return res

Ces calculs de temps sont rapides, avec $ update (i, x) $ étant $ O (1) $, mais lents car $ query (l, r) $ est $ O (N) $.
Considérons maintenant la structure de données illustrée dans la figure suivante. (En conclusion, ce n'est autre que ** l'arborescence des segments **.)

• Les nombres entre [] indiquent l'index dans ** l'arborescence des segments ** et les caractères gras indiquent les valeurs des données contenues.
  En utilisant cet ** arbre de segments **, le montant du calcul de $ update (i, x) $ augmente à $ O (logN) $, mais le montant du calcul de $ query (l, r) $ est également $ O ( Vous pouvez le déposer dans logN) $.

Par exemple, pour $ query (1, 7) $, vous pouvez trouver la somme des parties grises dans la figure ci-dessous. Pour être honnête, 5 ajouts sont nécessaires, mais seulement 3 ajouts.

Je ne donnerai pas de preuve détaillée car je veux principalement expliquer l'implémentation, mais pour toute combinaison de $ l, r (l <r) $, $ query (l, r) $ fonctionne avec $ O (logN) $. Je vais.
Parlons maintenant de l'implémentation (** récursive **). Par souci de simplicité, nous le fixerons comme $ N = 8 $, mais il en va de même pour les cas autres que 8 $.

Mise en œuvre de la mise à jour (i, x)

Pour $ update (i, x) $, les valeurs à mettre à jour sont $ a_i $ (couche inférieure dans la figure ci-dessus), $ a_i + a_j $ (deuxième couche à partir du bas), $ a_i + a_j + a_k + a_l $ (3ème couche à partir du bas), $ a_i + a_j + a_k + a_l + $… (4ème couche à partir du bas) Il y en a quatre au total. Ce nombre est $ O (logN) $ car il est le même que la hauteur de l'arbre lorsque ** Segment Tree ** est considéré comme une dichotomie complète.

De plus, si les index sont définis comme indiqué ci-dessus, les index avec les valeurs à mettre à jour seront dans l'ordre. i+N-1, ((i+N-1)-1)/2, (((i+N-1)-1)/2-1)/2, ((((i+N-1)-1)/2-1)/2-1)/2 Il est devenu. ($ / $ Est arrondi et divisé.) Je ne vais pas l'expliquer en détail ici non plus, mais vous pouvez voir que ** l'arbre du segment ** est une dichotomie complète.

D'après ce qui précède, l'implémentation de $ update (i, x) $ est la suivante.

def update(i, x):
    i += N-1 #Index dans la couche inférieure
    dat[i] = x

    #Mettre à jour les valeurs lors de l'escalade des couches
    while i > 0:
        i = (i-1) >> 1 #Index de la couche immédiatement supérieure(Les parents dans une dichotomie complète)

        #Remplacez la somme des deux couches inférieures(Somme des enfants dans une dichotomie complète)
        dat[i] = dat[i*2+1] + dat[i*2+2]

Implémentation de la requête (l, r)

$ query (l, r) $ doit être ajouté lorsque la "valeur de l'intervalle affecté à une certaine donnée" correspond complètement à $ [l, r) $. Par conséquent, vous pouvez écrire comme suit en utilisant ** récursif **.

#Requête de fonction récursive(l, r, k, L, R)
# L :section[L,R)Bord gauche de(Valeur initiale 0), R :section[L,R)Extrémité droite de(Valeur initiale N)
# k :section[L,R)Index contenant le résultat du calcul pour(Valeur initiale 0)

def query(l, r, k=0, L=0, R=None):
    #Initialisation de R
    if R is None:
        R = N

    #Si section[l,r)Et section[L,R)Renvoie 0 si ne se coupe pas
    if R <= l or r <= L:
        return 0

    #section[L,R)Est la section[l,r)Renvoie cette valeur si elle s'intègre parfaitement dans
    if l <= L and R <= r:
        return dat[k]

    #À d'autres moments, plongez dans l'arbre et voyez les deux enfants
    else:
        lres = query(l, r, k*2+1, L, (L+R) >> 1)
        rres = query(l, r, k*2+2, (L+R) >> 1, R)
        return lres + rres

Résumé de la mise en œuvre de l'arborescence de segments (récursive)

Sur la base de ce qui précède, l'arborescence des segments est implémentée comme suit. Ceci est une implémentation pour les monoïdes généraux.

class SegmentTree:
    #Processus d'initialisation
    # f :Monoïde sur l'arbre des segments
    # default :Élément d'unité pour f
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() #Pour plus de simplicité, définissez le nombre d'éléments N sur 2
        self.default = default
        self.dat = [default]*(self.size*2-1) #Initialiser les éléments en unités
        self.f = f

    def update(self, i, x):
        i += self.size-1
        self.dat[i] = x
        while i > 0:
            i = (i-1) >> 1
            self.dat[i] = self.f(self.dat[i*2+1], self.dat[i*2+2])

    def query(self, l, r, k=0, L=0, R=None):
        if R is None:
            R = self.size
        if R <= l or r <= L:
            return self.default
        if l <= L and R <= r:
            return self.dat[k]
        else:
            lres = self.query(l, r, k*2+1, L, (L+R) >> 1)
            rres = self.query(l, r, k*2+2, (L+R) >> 1, R)
            return self.f(lres, rres)

Implémentation de l'arborescence de segments non récursive

Soit dit en passant, c'est une introduction assez longue, et le sujet principal est d'ici. Le ** SegmentTree ** ci-dessus utilise une ** fonction récursive **, donc c'est un peu lent. Par conséquent, l'implémentation par ** fonction non récursive ** devient utile.

Il peut être implémenté avec la même structure que pour récursif, mais il est beaucoup plus facile à implémenter en décalant l'index de 1 à ** 1-indexed **. Si ** 1-indexed ** est défini, l'indice sera comme indiqué dans la figure ci-dessous.

En le rendant ** 1-indexé **, vous pouvez obtenir la relation indiquée dans le tableau suivant pour un nœud $ i $. Cette relation est utile pour la mise en œuvre.

def update(i, x):
    i += N #Index dans la couche inférieure
    dat[i] = x

    #Mettre à jour les valeurs lors de l'escalade des couches
    while i > 0:
        i >>= 1 #Index de la couche immédiatement supérieure(Les parents dans une dichotomie complète)
        #Remplacez la somme des deux couches inférieures(Somme des enfants dans une dichotomie complète)
        dat[i] = dat[i*2] + dat[i*2+1]

Pour un nœud, la section représentée est entre $ [l, r) $, et lorsque la section représentée par le nœud parent s'étend dans la direction ** gauche **, le nœud est un enfant du côté ** droit **. Il a un indice de ** impair **. Par contre, lorsqu'il s'étend dans la direction ** droite **, le nœud est un enfant du côté ** gauche **, donc il a un index de ** pair **.

Par conséquent, pour le côté gauche, montez dans l'arborescence depuis le bas, et si la section parent s'étend au-delà (si l'index du nœud que vous consultez actuellement est ** impair **), ajoutez la valeur de ce nœud et ajoutez un index. Il vous suffit de répéter le processus de déplacement vers la droite. La même chose s'applique au côté droit, et lorsque la section parent s'étend au-delà, elle peut être ajoutée et l'index peut être décalé vers la gauche de un. Cependant, comme il est affiché dans la ** section semi-ouverte **, il est jugé s'il s'étend ou non en fonction du fait que l'index du nœud actuellement consulté est ** impair **. Notez également que c'est le nœud ** 1 gauche ** qui est ajouté.

L'exemple de mise en œuvre est le suivant.

def query(l, r):
    #Initialiser pour indexer dans la couche inférieure
    l += N
    r += N

    #Initialisez la réponse à gauche et la réponse à droite avec 0
    lres, rres = 0, 0

    #Effectuer l'addition en utilisant le jugement ci-dessus jusqu'à ce que l et r se chevauchent
    while l < r:
        #Si l est impair, dat[l]Ajouter
        if l & 1:
            lres += dat[l]
            l += 1

        #Si r est impair, dat[r-1]Ajouter
        if r & 1:
            r -= 1
            rres += dat[r]

        #Grimper à un arbre
        l >>= 1
        r >>= 1

    res = lres + rres
    return res

class SegmentTree:
    #Processus d'initialisation
    # f :Monoïde sur l'arbre des segments
    # default :Élément d'unité pour f
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() #Pour plus de simplicité, définissez le nombre d'éléments N sur 2
        self.default = default
        self.dat = [default]*(self.size*2) #Initialiser les éléments en unités
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) #Notez le sens du calcul car la loi de conversion n'est pas garantie pour les monoïdes.
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

Comparaison

Nous avons comparé les temps d'exécution en utilisant des problèmes qui peuvent être résolus à l'aide de ** Segment Tree **. Les résultats sont présentés dans le tableau suivant, confirmant que la non-récursive peut être exécutée dans un temps plus court.

** URL du problème ** AOJ DSL_2_A http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A

AOJ DSL_2_B http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

AtCoder ABC_125_C https://atcoder.jp/contests/abc125/tasks/abc125_c

** URL de soumission ** AOJ DSL_2_A (récursif) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4326213#1

AOJ DSL_2_A (non récursif) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4326214#1

AOJ DSL_2_B (récursif) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4326207#1

AOJ DSL_2_B (non récursif) http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4326206#1

AtCoder ABC_125_C (récursif) https://atcoder.jp/contests/abc125/submissions/11596118

AtCoder ABC_125_C (non récursif) https://atcoder.jp/contests/abc125/submissions/11596126

finalement

Loin de Qiita, j'ai écrit un article pour la première fois de ma vie, donc je pense que c'est plein de choses. Si vous avez des questions telles que «c'est étrange» ou «quelque chose d'étrange est écrit», veuillez le signaler. Merci beaucoup.