[Fenwick_Tree] Lecture de la bibliothèque AtCoder avec un codeur vert ~ Implémentation en Python ~

0. Introduction

AtCoder Official Algorithm Collection AtCoder Library (** ACL **) publié le 7 septembre 2020 c'était fait. J'ai pensé que c'était une bonne opportunité car la plupart des algorithmes et des structures de données enregistrés dans ACL étaient nouveaux pour moi, j'ai donc tout fait, de l'étude des algorithmes à leur implémentation en Python.

Dans cet article, nous examinerons ** Fenwick_Tree ** (** Phoenix Tree **).

Lecteurs cibles

• Si vous regardez le code ACL mais ** ne savez pas ce que vous faites **.
• Ceux qui ne comprennent pas le C ++ et veulent le lire en Python.

Lecteurs non ciblés

• Ceux qui veulent du code optimisé Python pour ACL. → Puisqu'il a été implémenté pour être autant que possible identique à ACL, la vitesse d'exécution en Python n'est pas du tout prise en compte. Il semble y avoir un mouvement pour le rendre disponible directement à partir de Cython, il peut donc être bon de suivre cela.

Référencé

À propos du mécanisme de l'arbre phénix

• Arbre indexé binaire (diapositive) Très facile à comprendre
• [Wikipedia - Arborescence de Phoenix](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%8B%E3%83%83%E3%82%AF % E6% 9C% A8)

À propos du fonctionnement des bits

• Opération de bits Python
• Complément Wikipedia-2

1. Qu'est-ce qu'un arbre phénix?

Pour comprendre "qu'est-ce qu'un arbre phénix?", Considérons d'abord les questions suivantes.

Étant donné une séquence de $ N $ de longueur $ a_1, a_2, \ cdots, a_N $, plusieurs des deux types de requêtes suivants sont lancés sur cette séquence: Veuillez gérer cela.

• ** add **: Puisque $ i et x $ sont donnés, ajoutez $ x $ à $ a_i $.
• ** sum **: Puisque $ i $ est donné, la somme du début au $ i $ th est calculée.

Dans ce qui suit, la valeur donnée peut être explicitement écrite comme add (i, x), sum (i).

1.1. Tout d'abord, une réponse simple

Tout d'abord, pensez exactement comme il est écrit dans le problème. Ajouter une requête

a_i \leftarrow a_i+x

Par conséquent, il peut être traité avec le montant de calcul $ O (1) $. D'autre part, la somme de la requête

a_1+a_2+\cdots+a_i

Doit être calculé, le montant du calcul est donc de O $ (N) $.

1.2. En parlant de somme partielle, somme cumulée

En parlant de sommes partielles de nombres comme la somme de requêtes, vous pouvez penser à des sommes cumulatives. En fait, la somme de la requête peut être traitée avec $ O (1) $ en préparant un tableau qui est la somme cumulée du nombre de colonnes $ a $. Mais qu'en est-il de l'ajout de requête? Si vous modifiez une partie de la séquence $ a $, vous devrez recalculer la somme cumulée, donc le montant du calcul sera $ O (N) $ à la fin.

1.3. Phoenix Tree à ce moment

La réponse simple et la somme cumulée nécessitaient un montant de calcul de O $ (N) $ pour traiter à la fois les requêtes d'addition et de somme. Bien sûr, ce serait bien si cela suffisait, mais je veux le rendre plus rapide. .. .. ** Phoenix Tree ** apparaît à de tels moments. Phoenix Tree peut traiter à la fois ** des requêtes add et sum avec $ O (\ log N) $ à la fois! ** ** Les arbres Phoenix sont également connus sous le nom de ** arbre indexé binaire (BIT) **.

2. Quel genre d'arbre est un arbre phénix?

Jetons un coup d'œil à la structure de l'arbre Phoenix. Par conséquent, considérons le cas où $ N = 7 $ est spécifiquement la longueur de la séquence $ a $.

2.1. Faire un arbre pour le moment

Puisqu'il doit s'agir d'une structure arborescente car on l'appelle "arbre" phénix, nous allons créer un arbre à partir de la séquence $ a $. Plus précisément, comme le montre la figure ci-dessous, un arbre est créé avec chaque terme de la séquence en tant que feuille et la somme des deux termes en tant que parent.

Maintenant que nous avons un arbre (forêt?), Utilisons cet arbre pour résoudre les problèmes du chapitre précédent. Le premier est l'ajout de requête. Par exemple, pensez à mettre à jour $ a_3 $. Il y a trois endroits où $ a_3 $ est lié, vous pouvez donc les mettre à jour. Plus généralement, il y a autant d'endroits à mettre à jour que la hauteur d'un arbre. La hauteur de cet arbre est d'environ $ \ log N $, donc le montant du calcul est $ O (\ log N) $. Qu'en est-il de la somme de la requête? Par exemple, lors de la recherche de la somme jusqu'au 7e

\sum_{i=1}^{7}{a_i}=(a_1+a_2+a_3+a_4)+(a_5+a_6)+(a_7)

Donc, vous devriez regarder 3 endroits. En général, il suffit de regarder la hauteur de l'arbre, donc le montant du calcul est $ O (\ log N) $.

2.2. Plus intelligent

Il semble donc que $ O (\ log N) $ puisse être utilisé à la fois pour les requêtes d'ajout et de somme. Je voudrais dire que je suis content, mais l'arbre que j'ai fait plus tôt est en fait un gaspillage. En fait, il y a des endroits que je n'ai jamais vus quand je vérifie toutes les sommes jusqu'à la première, la somme jusqu'à la seconde, $ \ cdots $, et la somme jusqu'à la septième. Après les avoir supprimés, cela ressemblera à la figure ci-dessous. Il contient toutes les informations nécessaires pour traiter la somme de la requête. (L'ajout de requête ne met à jour que l'emplacement pertinent, il n'y a donc pas de problème.)

2.3. La véritable apparence de l'arbre Phoenix

Jusqu'à présent, j'ai montré la structure arborescente pour savoir "quel genre d'arbre est un arbre phénix?", Mais si vous regardez le code de l'arbre phénix dans ACL, c'est un arbre unidimensionnel d'une longueur de $ N $ de data. Il n'y a qu'un tableau. Où est l'arbre? En fait, ces «données» sont emballées avec une structure arborescente. Plus précisément, il contient ** des informations sur les "directions à suivre" en utilisant l'index du tableau **. Maintenant, changeons l'arbre que nous avons vu ci-dessus en un tableau unidimensionnel. Comme vous l'avez peut-être remarqué, en supprimant la partie inutile plus tôt, la place restante est juste $ N $. Et la valeur maximale de l'indice qui prend la somme partielle (partie soulignée en rouge dans la figure ci-dessous) est différente à chaque endroit. Vous pouvez créer des «données» en utilisant cette valeur.

Donc, j'ai trouvé que la réalité de l'arbre Phoenix (en termes d'implémentation) est un tableau unidimensionnel ** qui contient une belle somme partielle.

3. Comment marcher dans un arrangement étrange

Notre but est de traiter les requêtes add, sum en utilisant cet étrange tableau data. Dans ce chapitre, nous verrons comment chaque requête vous donne "** les directions à suivre **".

3.1. Ajout de requête

Le premier est l'ajout de requête. La requête add (i, x) peut aller n'importe où contenant $ a_i $. Regardons quelques exemples.

Il est difficile de voir les règles avec juste cela. Cependant, si vous faites attention à la «différence entre l'indice actuel et l'indice suivant», les perspectives s'amélioreront immédiatement.

Les lettres rouges sont les index des «données», les flèches vertes sont les directions et les lettres vertes sont les différences d'index. En regardant ce chiffre, vous pouvez voir que vous pouvez ajouter +1 à partir du bas et +2 à partir du milieu. Les parties supérieure, médiane et inférieure de cette figure sont divisées par "le nombre de termes à additionner", et c'est ce qu'on appelle "** longueur **". Par exemple, "longueur des" données [6] "" vaut 2. Ensuite, pour traiter la requête add (i, x), on peut dire que:

Indice

i^\prime = i + (data[i]Longueur de)

Et ajoutez x à data [i].

3.2. Somme des requêtes

Ensuite, regardons la somme de la requête. La somme de la requête (i) doit être tracée pour couvrir $ a_1, \ cdots, a_i $ et résumée. Comme pour la requête ajoutée précédemment, prêtons attention à la "différence entre l'index actuel et l'index suivant".

Après tout, en utilisant "longueur", vous pouvez trouver l'index suivant. Par conséquent, pour traiter la somme de la requête (i), nous pouvons dire que:

Indice

i^\prime = i - (data[i]Longueur de)

Lors de la mise à jour, prenez la somme de chaque data [i].

3.3. Longueur

Il s'avère que les deux requêtes peuvent être traitées tant que la "longueur de" données [i] "" est obtenue. Alors, comment obtenir la longueur de data [i] de i? Rappelez-vous que l'arbre Phoenix est également connu sous le nom d'arbre indexé binaire. Affiche l'index et son affichage binaire pour chaque longueur.

A partir de ce tableau, la longueur correspond à "** l'index est affiché en binaire et à l'endroit où '1' apparaît pour la première fois vu de la droite ", c'est-à-dire " le bit le moins significatif de '1' **". Tu peux voir ça. Le bit le moins significatif est souvent écrit en anglais sous la forme ** Least Significant Bit (LSB) **. Et "LSB de '1' dans i" (écrit comme = LSB (i)) peut être facilement obtenu par ** opération sur les bits **.

LSB(i) \quad=\quad i\quad\&\quad(-i)

Où & est une opération ET bit par bit. Les opérations sur les bits pour les nombres négatifs sont exprimées en 2 complément Il est traité comme représenté par (Reference). Regardons quelques exemples. Ici, nous allons considérer la représentation du complément à 8 bits 2. Quand $ i = 6 $

\begin{aligned}
LSB(6) &= 6 \quad\&\quad(-6)\\
&= (00000110)_2 \quad\&\quad (11111010)_2\\
&= (00000010)_2\\
&= 2
\end{aligned}

Quand $ i = 7 $

\begin{aligned}
LSB(7) &= 7 \quad\&\quad(-7)\\
&= (00000111)_2 \quad\&\quad (11111001)_2\\
&= (00000001)_2\\
&= 1
\end{aligned}

Quand $ i = 24 $

\begin{aligned}
LSB(24) &= 24 \quad\&\quad(-24)\\
&= (00011000)_2 \quad\&\quad (11101000)_2\\
&= (00001000)_2\\
&= 8
\end{aligned}

Maintenant que vous êtes prêt à implémenter Phoenix Tree, implémentons-le.

4. Mise en œuvre

Mettons-le en œuvre. Implémentez autant que possible les noms de variables, les noms de méthodes, etc. selon ACL.

4.1. Constructeur

Créez la classe Fenwick_Tree pour implémenter le constructeur.

class Fenwick_Tree:
    def __init__(self, n):
        self._n = n  #Nombre d'éléments
        self.data = [0] * n

Conservez le nombre d'éléments dans la variable d'instance _n et créez une liste data de longueur n. Au moment de l'initialisation, tout vaut 0. Cela correspond à la séquence $ a = \ {0, \ cdots, 0 \} $. Si vous voulez initialiser avec une chaîne numérique différente de zéro, exécutez $ add (i, a_i) $ pour chaque i.

Mise en garde Jusqu'au chapitre précédent, data était ** 1-indexed **, mais dans l'implémentation, il est ** 0-indexed **. Veuillez noter que le mécanisme de l'arbre phénix est indexé à 1, vous devrez donc le décaler de 1 lors de l'accès à data.

4.2. add Implémentons d'abord la méthode add. Cette méthode correspond à la requête add (p, x).

def add(self, p, x):
    assert 0 <= p < self._n
    p += 1  # 0-indexed -> 1-indexed
    while p <= self._n:
        self.data[p - 1] += x　 #mettre à jour les données
        p += p & -p  #LSB à p(p)Ajouter

Comme nous l'avons vu au chapitre 3.1, query add trouve le prochain index à regarder en ajoutant LSB. Répétez cette mise à jour d'index et la mise à jour de data jusqu'à ce que le tableau ne soit plus référencé.

4.3. sum Vient ensuite la méthode sum: dans ACL, celle correspondant à la requête sum (i) est implémentée comme une fonction interne (privée), et la fonction externe (publique) réellement utilisée est une fonction plus générale. Il est mis en œuvre. Plus précisément, en spécifiant deux valeurs l et r, la somme partielle des sections semi-ouvertes gauche-fermée et droite-ouverte [l, r)

\sum_{i = l}^{r - 1}{a_i}

Retour. (a est indexé à 0) Tout d'abord, implémentez à partir de la fonction interne correspondant à la somme de la requête. Ceci renvoie la somme partielle $ a_0 + \ cdots + a_ {r --1} $ de l'intervalle semi-ouvert [0, r) pour r. Cependant, il renvoie 0 lorsque $ r = 0 $. J'ai également ajouté un trait de soulignement (_) au début pour indiquer qu'il s'agit d'une fonction interne.

def _sum(self, r):
    s = 0  #Variable pour mettre la somme
    while r > 0:
        s += self.data[r - 1]
        r -= r & -r  #r à LSB(r)Soustraire
    return s

Comme nous l'avons vu au chapitre 3.2, la somme des requêtes sait quel index regarder ensuite en soustrayant le LSB. Lors de la mise à jour, prenez la somme de chaque data [r]. Utilisez cette fonction interne pour implémenter la fonction externe générique mentionnée ci-dessus.

def sum(self, l, r):
    assert 0 <= l <= r <= self._n
    return self._sum(r) - self._sum(l)

([l, r)Somme partielle de) = (r -Somme partielle jusqu'à 1) - (l -Somme partielle jusqu'à 1)

est.

4.4. Résumé

fenwicktree.py

class Fenwick_Tree:
    def __init__(self, n):
        self._n = n
        self.data = [0] * n
    
    def add(self, p, x):
        assert 0 <= p < self._n
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p
    
    def sum(self, l, r):
        assert 0 <= l <= r <= self._n
        return self._sum(r) - self._sum(l)
    
    def _sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s

5. Exemple d'utilisation

Ce n'est pas nécessaire à l'origine, mais nous ajoutons directement à a pour voir la séquence a elle-même.

    n = 8 
    a = [0, 1, 2, 3, 4, 5, 6, 7]
    fw = Fenwick_Tree(n)
    for i, a_i in enumerate(a): fw.add(i, a_i)  #Initialiser avec la colonne numérique a
    print(fw.sum(2, 4))  # 5
    print(fw.sum(6, 7))  # 6 sum(i, i + 1)Dans un[i]Peut être obtenu
    fw.add(2, 6)  # a[2] += 6
    a[2] += 6
    fw.add(5, -1)  # a[5] += -1
    a[5] += -1
    print(a)  # [0, 1, 8, 3, 4, 4, 6, 7]
    print(fw.sum(0, 3))  # 9
    print(fw.sum(3, 7))  # 17

6. Exemple de problème

AtCoder Library Practice Contest B "Fenwick Tree"

7. Conclusion

De l'élucidation du mécanisme de l'arbre phénix à sa mise en œuvre en Python. L'arbre de Phoenix semble avoir diverses applications, alors j'aimerais l'étudier un jour.

Veuillez nous faire savoir si vous avez des erreurs, des bogues ou des conseils.