introduction

Normalement, je viens de googler et de coller un arbre seg, mais comme j'avais le temps en raison de l'influence du virus corona, j'ai essayé de le mettre en œuvre tout en comprenant le principe. Je l'ai construit en me référant aux articles de diverses personnes principalement sur le net. Je mettrai le lien dans la dernière référence, mais j'utilise généralement le code lors du concours [article de Juppy](https://juppy.hatenablog.com/entry/2019/05/02/%E8 % 9F% BB% E6% 9C% AC_python_% E3% 82% BB% E3% 82% B0% E3% 83% A1% E3% 83% B3% E3% 83% 88% E6% 9C% A8_% E7% AB % B6% E6% 8A% 80% E3% 83% 97% E3% 83% AD% E3% 82% B0% E3% 83% A9% E3% 83% 9F% E3% 83% B3% E3% 82% B0_Atcoder ), J'ai été particulièrement utile pour HP d'Ikatako Takotsubo-san, donc je vais le lister au début.

Objectif

Je vais résumer les principes dans un autre article. Le but de cet article est d'expliquer ** comment utiliser votre propre arbre seg **. À titre indicatif, je ferai référence à M. Juppy, je définirai l'élément unité et l'opération que vous souhaitez effectuer vous-même, et cela est écrit dans la classe. Le nœud de l'arbre seg a été écrit avec 1-index.

code

#####segfunc#####
def segfunc(x, y):
    return
#################

#####ide_ele#####
ide_ele =
#################

class SegTree:
    """
    init(init_val, ide_ele):Array init_Initialiser avec val O(N)
    update(k, x):Mettre à jour la kème valeur à x O(logN)
    query(l, r):section[l, r)Renvoie le segfunc de O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val:Valeur initiale du tableau
        segfunc:Opération que vous souhaitez créer une section
        ide_ele:Élément d'unité
        n:Nombre d'éléments
        num:Puissance minimale de 2 supérieure ou égale à n
        tree:Arborescence des segments(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        #Définissez la valeur du tableau sur la feuille
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        #Construire
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
    
    def update(self, k, x):
        """
Mettre à jour la valeur kth à x
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)Obtenez le segfunc
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

Comment utiliser

1. Préparez une liste pour l'initialisation

Tout ira bien. Par exemple ↓

a = [14, 5, 9, 13, 7, 12, 11, 1, 7, 8]

2. Décidez quoi faire dans la section

Je veux trouver les valeurs minimales et maximales de l'intervalle, je veux trouver la somme des intervalles, etc. Cette fois, supposons que vous souhaitiez trouver la valeur minimale. Écrivez la fonction en segfunc.

def segfunc(x, y):
    return min(x, y)

3. Déterminez l'élément unitaire

Utilisé pour l'initialisation. Cela n'affecte pas le calcul. Si vous voulez trouver la valeur minimale, c'est l'infini.

ide_ele = float('inf')

4. Créez un objet, les trois arguments ci-dessus

seg = SegTree(a, segfunc, ide_ele)

5. Chaque opération peut être effectuée

Traitez la liste comme un index 0. (Comme toujours.) Vous pouvez effectuer deux opérations.

1. Mettre à jour un élément

** update (k, x) **: met à jour le kème élément en x.

2. Obtenez le résultat de l'opération d'une certaine section

Obtenez la valeur de ** query (l, r) **: ** [l, r) ** (intervalle entre l et r).

# [0, 8)Afficher la valeur minimale de
print(seg.query(0, 8)) # 1

#Remplacez le 5 par 0
seg.update(5, 0)

# [0, 8)Afficher la valeur minimale de
print(seg.query(0, 8)) # 0

Résumé

C'est long, alors je l'ai plié.

#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################

#####ide_ele#####
ide_ele = float('inf')
#################

class SegTree:
    """
    init(init_val, ide_ele):Array init_Initialiser avec val O(N)
    update(k, x):Mettre à jour la kème valeur à x O(N)
    query(l, r):section[l, r)Renvoie le segfunc de O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val:Valeur initiale du tableau
        segfunc:Opération que vous souhaitez créer une section
        ide_ele:Élément d'unité
        n:Nombre d'éléments
        num:Puissance minimale de 2 supérieure ou égale à n
        tree:Arborescence des segments(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        #Définissez la valeur du tableau sur la feuille
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        #Construire
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
    
    def update(self, k, x):
        """
Mettre à jour la valeur kth à x
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)Obtenez le segfunc
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

a = [14, 5, 9, 13, 7, 12, 11, 1, 7, 8]

seg = SegTree(a, segfunc, ide_ele)

print(seg.query(0, 8))
seg.update(5, 0)
print(seg.query(0, 8))

Autres opérations (autres que la valeur minimale)

opération	segfunc	Élément d'unité
valeur minimum	min(x, y)	float('inf')
Valeur maximum	max(x, y)	-float('inf')
Somme de section	x + y	0
Produit de la section	x * y	1
Engagement maximum	math.gcd(x, y)	0

en conclusion

Veuillez me faire savoir si vous avez des erreurs ou des conseils. Veuillez le tester soigneusement avant de l'utiliser pour le concours !!

Les références

Ce sont les deux personnes mentionnées au début. ↓ ・ [Le blog de Juppy](https://juppy.hatenablog.com/entry/2019/05/02/%E8%9F%BB%E6%9C%AC_python_%E3%82%BB%E3%82%B0% E3% 83% A1% E3% 83% B3% E3% 83% 88% E6% 9C% A8_% E7% AB% B6% E6% 8A% 80% E3% 83% 97% E3% 83% AD% E3% 82% B0% E3% 83% A9% E3% 83% 9F% E3% 83% B3% E3% 82% B0_Atcoder) ・ Les PV de Takotsubo Cela m'a aidé à comprendre le principe en général. ↓ ・ Implémentation et compréhension des arborescences de segments étape par étape (python) Il est devenu une référence pour la partie non récursive de l'arborescence de segments. ↓ ・ Je veux accélérer un peu l'arbre des segments ・ Écriture non récursive de l'arborescence des segments

Algorithme (arborescence de segments) en Python (s'entraîner)