Essayer d'implémenter et de comprendre les arborescences de segments étape par étape (python)

introduction

Quand je fais AtCoder, je vois souvent des personnes fortes tweeter sur Twitter, comme coller un arbre seg, mais comme je ne l'ai pas moi-même, c'est un article que je vais mettre en œuvre à ce moment et le connecter à la compréhension et à l'application. ..

Si vous faites partie du concours et que vous souhaitez l'implémenter immédiatement, il y a un code dans le résumé de l'implémentation. Le fonctionnement ne peut pas être garanti.

Je suis désolé de dire quel est le numéro de la décoction. Je pense me différencier en n'omettant pas l'implémentation de Narutake.

Faites-en la structure la plus élémentaire de la mise à jour en un point et de l'acquisition de sections. J'écrirai sur l'évaluation du retard dans la suite si j'en ai envie (ou si j'en ai besoin).

Sites référencés

http://beet-aizu.hatenablog.com/entry/2017/09/10/132258 https://www.slideshare.net/iwiwi/ss-3578491 http://tsutaj.hatenablog.com/entry/2017/03/29/204841

Qu'est-ce qu'un arbre de segments?

Que puis-je faire?

Vous pouvez utiliser ** O (logN) ** pour rechercher des requêtes d'intervalle liées aux opérations et opérations qui satisfont certaines propriétés. (Par exemple, une requête pour trouver la valeur minimale du premier ou cinquième élément) Cependant, notez qu'il faut ** O (N) ** pour construire.

Alors quel type de calcul peut être utilisé?

Tout ce qui est appelé ** monoïde ** peut être intégré.

Qu'est-ce qu'un monoïde

Je pense que c'est un peu moins rigoureux,

Il suffit que la règle de liaison soit satisfaite et que l'élément unit existe.

Quelle est la loi de connexion?

Par exemple, si vous pensez à l'addition

Ce faisant, ** il est bon que le résultat ne change pas, peu importe où vous calculez lors du calcul entre trois ou plusieurs choses ** Puisque cela est vrai, l'arborescence de segments peut diviser de plus en plus la section en acquérant la valeur. ([0,6) → (comme [0,4) + [4,6))

Qu'est-ce qu'un élément unitaire?

Il est difficile de dire l'original, mais en termes d'application, si vous pensez en termes d'ajout,

** Un nombre qui est le même que le nombre d'origine lorsqu'il est calculé avec lui est appelé un élément d'unité ** D'ailleurs, par exemple, si vous pensez à la multiplication

1 est l'élément unitaire.

Exemples de monoïdes

• 1 En bref, si une valeur supérieure à la valeur qui peut apparaître est prise, elle devient un élément unitaire. Par exemple, si la contrainte du problème est $ A_i <= 10 ^ 4 $, si l'élément unitaire est $ 10 ^ 4 + 1 $, $ min (A_i, 10 ^ 4 + 1) = min (10 ^ 4 + 1,) A_i) = A_i $, qui est l'élément unitaire. Si la cible est composée de nombres naturels, il n'y a pas d'élément unité.

• 2 Dans une discussion similaire au cas de la valeur minimale, si une valeur inférieure ou égale à la valeur qui peut apparaître est prise, elle devient un élément unitaire.

Je pense que des opérations plus spéciales peuvent être traitées comme des monoïdes en fonction d'autres restrictions, mais je ne pense pas que les personnes qui proposent de telles idées aient besoin de lire cet article, alors je vais le laisser.

[référence] http://beet-aizu.hatenablog.com/entry/2017/09/10/132258

De quel genre de structure s'agit-il?

Une bissectrice avec les résultats d'une requête sur la section à couvrir. Implémenter en tant que tableau.

Comme ça. Plus vous allez bas, plus la section devient petite.

Veuillez faire attention à l'index du tableau. ** Vous pouvez obtenir l'index de l'enfant par l'index du parent x2 et l'index du parent x2 + 1. ** C'est basique dans BIT (arbre d'index binaire) et les arbres bifurqués, mais j'ai été impressionné quand je l'ai vu pour la première fois. Au fait, c'est parce que je pense avec 1-index, et quand c'est 0-index, ça devient × 2 + 1, × 2 + 2. Peu importe celui que vous utilisez, mais personnellement, si vous utilisez 1-index, l'opération pour voir le parent de l'enfant ne doit être coupée qu'en le divisant par 2, donc je l'ai mis à 1-index.

Ici, la feuille du bas contiendra les données d'origine de la séquence que vous souhaitez interroger. (Cette fois, il s'agit d'un tableau de taille 4)

Que faire si le nombre d'éléments dans le tableau n'est pas 2 ^ k?

Déterminez la profondeur de l'arbre afin que le nombre de feuilles en bas puisse être suffisamment préparé pour contenir la séquence d'intérêt pour laquelle vous souhaitez calculer l'intervalle d'interrogation. La partie excédentaire doit être remplie avec l'élément unitaire.

Modifions-le un peu et considérons un exemple de taille de tableau = 3. Si vous remplissez l'élément d'unité qui est apparu ci-dessus dans la partie restante,

De cette manière, il peut être traité sans aucune influence particulière.

la mise en oeuvre

Initialisation

Déterminez la taille du tableau qui stocke l'arborescence afin que le nombre de feuilles à la fin soit de 2 ^ k et que vous puissiez sécuriser plus que la taille du tableau que vous souhaitez interroger.

Étant donné que

Pour k, préparez un tableau de stockage d'arborescence d'une taille de 2 $ ^ {k + 1} $. La mise en œuvre ressemble à ceci.

class segtree:

    def __init__(self, n,operator,identity):
        """
        n:Taille du tableau de données
        operator:opérateur(Monoïde).. Objet de fonction
        identity:Élément unitaire correspondant à l'opérateur
        """
        nb = bin(n)[2:] #Convertir en binaire et supprimer 0b en combat
        bc = sum([int(digit) for digit in nb]) #Le nombre avec 1 en bit. Quand c'est 1, c'est juste 2^nb.Sinon, 2^nb<n<2^(nb+1)
        if bc == 1: #2^avec nb
            self.num_end_leaves = 2**(len(nb)-1) #La feuille du bas est 2^nb pièces
        else:#Sinon 2^(nb+1)Sécurise
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)] #Initialiser avec l'élément unit

        self.identity = identity 
        self.operator =operator
        #Avoir des éléments d'unité et des opérateurs pour une utilisation ultérieure

Mettre à jour la valeur

Je l'ai écrit brièvement au début, mais s'il s'agit d'un index 1, si vous divisez votre index par 2 et le tronquez, vous deviendrez votre parent. (Comme 3 → 1, 5 → 2)

La valeur est mise à jour en remontant à l'origine et en appliquant les opérateurs dans l'ordre. La mise en œuvre de cette seule partie ressemble à ceci.

    def update(self,x,val):
        """
        x:Emplacement de substitution
        val:Valeur à remplacer
        """
        actual_x = x+self.num_leaves #1-Ajouter la minute où commence l'index de la feuille à la fin de l'index(Par exemple, lorsque la taille du tableau de données est de 4, la taille du tableau de l'arborescence est de 8 et la seconde moitié commence à partir de l'index 4.
        self.array[actual_x] = val #Mettre à jour la valeur
        while actual_x > 0 :
            actual_x = actual_x//2#Voir les parents
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])#Mettre à jour les parents avec un nouvel enfant

Obtenez de la valeur

Pour une certaine gamme, il suffit que la gamme puisse être exprimée par une combinaison de feuilles qui couvrent une gamme aussi large que possible. Par exemple, si votre tableau de données a une taille de 4 et que vous voulez une plage de [0,2]

Comme ça

• Regardez l'enfant si votre domaine de responsabilité est en dehors de la requête.
• Si la plage de requête inclut votre zone de responsabilité, renvoyez la valeur.
• Si la position n'est pas liée à la requête, l'élément unit est renvoyé.

Si vous répétez, dans ce cas [0,1], [2], l'élément unité est obtenu sous forme de valeur, et cela ressemble à la fusion de ces sous-régions.

Vous pouvez obtenir une requête d'intervalle. La mise en œuvre est comme ça.

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        """
        q_gauche: à gauche de la section de requête
        q_right:À droite de l'intervalle de requête
        arr_ind:Index du tableau d'arborescence. Le premier est un parent donc 1
        leaf_left:À gauche de l'index du tableau d'arborescence, la plage couverte par les feuilles qu'il représente
        depth:Profondeur dans un tableau d'arbres. Utilisé pour calculer la taille de la couverture
        """
        width_of_floor = self.num_end_leaves//(2**depth) #Largeur de couverture de la feuille actuelle
        leaf_right = leaf_left+width_of_floor-1 #Trouvez le côté droit de la couverture de feuille actuelle à partir du bord gauche et de la largeur de la couverture.

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity #Renvoie l'élément unit si la zone de requête et la feuille ne sont pas liées

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind] #Renvoie la valeur de la feuille si la zone de requête est complètement remplie de feuilles

        else: #Sinon, regarde l'enfant
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)#La gauche de l'enfant
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)#Le droit de l'enfant
            return self.operator(val_l,val_r)#Effectue une opération pour fusionner les enfants.

Résumé de la mise en œuvre

class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2**(len(nb)-1)
        else:
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator =operator

    def update(self,x,val):
        actual_x = x+self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_end_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

Procès

Créez un tableau de plage approprié et demandez la valeur minimale. De plus, planifiez le temps d'exécution de manière appropriée.

s_tree = segtree(10**5,min,10**9) #10**Puisqu'il s'agit d'un tableau jusqu'à 5, l'élément unité est 10**9
arr = [i for i in range(10**5)]

print(datetime.datetime.now())

for i,a in enumerate(arr):
    s_tree.update(i,a)

print(datetime.datetime.now())


print(s_tree.get(0,10**4))
print(s_tree.get(3*10**4,5**10**4))
print(s_tree.get(2,7*10**4))

print(datetime.datetime.now())

2020-02-04 19:15:34.934814
2020-02-04 19:15:35.646339
0
30000
2
2020-02-04 19:15:35.646587

Après tout, la construction est la plus lourde. L'opération semble être normale. (Il semble que le bogue sera comblé si vous ne le déplacez pas avec un problème plus compliqué.)