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) $.

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.

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 **.) segtree_1.jpg

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. segtree_2.jpg

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. segtree_3.jpg

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.

Index des parents i/2
Index enfant gauche 2i
Index enfant droit 2i+1
a_iIndex auquel la valeur de i+N

#### Mise en œuvre de la mise à jour (i, x) L'implémentation de $ update (i, x) $ est presque la même que pour le type récursif, faites juste attention à la relation ci-dessus. L'exemple de mise en œuvre est le suivant.
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]

#### Implémentation de la requête (l, r) Il s'agit d'une implémentation de $ query (l, r) $, mais si nous considérons les conditions nécessaires et suffisantes pour ajouter des données avec ** Segment Tree **, nous pouvons voir que: J'omettrai la preuve. "** Lorsque l'intervalle représenté par le nœud est complètement contenu dans $ [l, r) $ et que l'intervalle représenté par le nœud parent n'est pas complètement contenu dans $ [l, r) $ **"

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

#### Récapitulatif de l'implémentation de l'arborescence de segments non récursive Sur la base de ce qui précède, l'arborescence de segments non récursive 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) #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.

Nom du problème Récursif 非Récursif
AOJ DSL_2_A AC(3:08s) AC(1.73s)
AOJ DSL_2_B AC(3:73s) AC(1.78s)
AtCoder ABC_125_C TLE(2111ms) AC(968ms)

** 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.

Recommended Posts

Implémentation Python de l'arborescence de segments non récursive
Implémentation de l'arbre TRIE avec Python et LOUDS
Implémentation Python du filtre à particules
Implémentation du tri rapide en Python
Implémentation Python du filtre à particules auto-organisateur
Tour de Hanoi-Rétrospective / Non-récursive (édition Python)
Implémentation du jeu de vie en Python
Implémentation de Light CNN (Python Keras)
Implémentation du tri original en Python
Implémentation de la méthode Dyxtra par python
Algorithme (arborescence de segments) en Python (s'entraîner)
Arborescence de sortie des fichiers en Python
Arborescence de segments retardée en Python (demande de débogage)
Implémentation Python du modèle Markov caché continu
Les bases de Python ①
Bases de python ①
Copie de python
Introduction de Python
Pourquoi l'implémentation Python d'ISUCON 5 a utilisé Bottle
[Entretien de codage] Implémentation de la machine cryptographique Enigma (Python)
Explication de la distance d'édition et de l'implémentation en Python
[Python] Implémentation du clustering à l'aide d'un modèle gaussien mixte
[Python] Opération d'énumération
Exemple d'implémentation d'un système de traitement LISP simple (version Python)
Implémentation d'estimation la plus probable du modèle de sujet en python
Implémentation RNN en python
Unification de l'environnement Python
Copie des préférences python
Principes de base du grattage Python
[python] comportement d'argmax
Comparaison de l'implémentation de plusieurs moyennes mobiles exponentielles (DEMA, TEMA) en Python
Utilisation des locaux Python ()
le zen de Python
Implémentation python de la classe de régression linéaire bayésienne
Installation de Python 3.3 rc1
Implémentation de la séquence de Fibonacci
# 4 [python] Bases des fonctions
Connaissance de base de Python
Anecdotes sobres de python3
Résumé des arguments Python
Implémentation d'estimation bayésienne de variante du modèle de sujet en python
Un mémorandum sur la mise en œuvre des recommandations en Python
Bases de python: sortie
Installation de matplotlib (Python 3.3.2)
Application de Python 3 vars
Implémentation SVM en python
Divers traitements de Python
Implémentation Python du mode de fusion CSS3 et discussion sur l'espace colorimétrique
Une implémentation Python simple de la méthode k-voisinage (k-NN)
[Avec une explication simple] Implémentation Scratch d'une machine Boltsman profonde avec Python ②
[Avec une explication simple] Implémentation Scratch d'une machine Boltzmann profonde avec Python ①
Implémentation informatique quantique de Quantum Walk 2
Vers la retraite de Python2
Implémentation de TF-IDF à l'aide de gensim
Implémentation de MathJax sur Sphinx
résumé lié à l'opération de fichier python
Résumé des opérations de liste Python3
Python - Démarrage rapide de la journalisation