Einführung

Normalerweise habe ich nur gegoogelt und einen Seg-Baum geklebt, aber da ich aufgrund des Einflusses des Corona-Virus Zeit hatte, habe ich versucht, ihn zu implementieren, während ich das Prinzip verstanden habe. Ich habe es gebaut, während ich mich auf die Artikel verschiedener Leute hauptsächlich im Internet bezog. Ich werde den Link in die letzte Referenz einfügen, aber ich verwende normalerweise den Code während des Wettbewerbs [Juppys Artikel](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 ), Ich war besonders hilfreich für HP von Ikatako Takotsubo-san, daher werde ich es am Anfang auflisten.

Zweck

Ich werde die Prinzipien in einem anderen Artikel zusammenfassen. In diesem Artikel wird erläutert, wie Sie Ihren eigenen Seg-Baum verwenden. Als grobe Funktion beziehe ich mich auf Mr. Juppy, setze das Einheitenelement und die Operation, die Sie selbst ausführen möchten, und es wird in der Klasse geschrieben. Der Knoten des Seg-Baums wurde mit 1-Index geschrieben.

Code

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

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

class SegTree:
    """
    init(init_val, ide_ele):Array init_Initialisieren Sie mit Wert O.(N)
    update(k, x):Aktualisieren Sie den k-ten Wert auf x O.(logN)
    query(l, r):Sektion[l, r)Gibt den Segfunc von O zurück(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val:Anfangswert des Arrays
        segfunc:Operation, für die Sie einen Abschnitt erstellen möchten
        ide_ele:Einheitselement
        n:Elementanzahl
        num:Mindestleistung von 2 größer oder gleich n
        tree:Segmentbaum(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
        #Setzen Sie den Wert des Arrays auf das Blatt
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        #Bauen
        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):
        """
Aktualisieren Sie den k-ten Wert auf 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)Holen Sie sich die 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

Wie benutzt man

1. Bereiten Sie eine Liste für die Initialisierung vor

Alles wird gut. Zum Beispiel ↓

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

2. Entscheiden Sie, was in diesem Abschnitt zu tun ist

Ich möchte die minimalen und maximalen Werte des Intervalls finden, ich möchte die Summe der Intervalle finden usw. Angenommen, Sie möchten diesmal den Mindestwert ermitteln. Schreiben Sie die Funktion in segfunc.

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

3. Bestimmen Sie das Einheitselement

Wird zur Initialisierung verwendet. Dies hat keinen Einfluss auf die Berechnung. Wenn Sie den Mindestwert ermitteln möchten, ist dies unendlich.

ide_ele = float('inf')

4. Erstellen Sie ein Objekt mit den obigen drei Argumenten

seg = SegTree(a, segfunc, ide_ele)

5. Jede Operation kann ausgeführt werden

Behandle die Liste als 0-Index. (Wie immer.) Sie können zwei Vorgänge ausführen.

1. Aktualisieren Sie ein Element

** update (k, x) **: Aktualisiere das k-te Element auf x.

2. Holen Sie sich das Ergebnis der Operation eines bestimmten Abschnitts

Ermitteln Sie den Wert aus ** query (l, r) **: ** [l, r) ** (Intervall zwischen l und kleiner als r).

# [0, 8)Zeigen Sie den Mindestwert von
print(seg.query(0, 8)) # 1

#Ändern Sie 5. auf 0
seg.update(5, 0)

# [0, 8)Zeigen Sie den Mindestwert von
print(seg.query(0, 8)) # 0

Zusammenfassung

Es ist lang, also habe ich es gefaltet.

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

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

class SegTree:
    """
    init(init_val, ide_ele):Array init_Initialisieren Sie mit Wert O.(N)
    update(k, x):Aktualisieren Sie den k-ten Wert auf x O.(N)
    query(l, r):Sektion[l, r)Gibt den Segfunc von O zurück(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val:Anfangswert des Arrays
        segfunc:Operation, für die Sie einen Abschnitt erstellen möchten
        ide_ele:Einheitselement
        n:Elementanzahl
        num:Mindestleistung von 2 größer oder gleich n
        tree:Segmentbaum(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
        #Setzen Sie den Wert des Arrays auf das Blatt
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        #Bauen
        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):
        """
Aktualisieren Sie den k-ten Wert auf 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)Holen Sie sich die 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))

Andere Operationen (außer dem Mindestwert)

Operation	segfunc	Einheitselement
Mindestwert	min(x, y)	float('inf')
Maximalwert	max(x, y)	-float('inf')
Abschnittssumme	x + y	0
Abschnitt Produkt	x * y	1
Maximales Engagement	math.gcd(x, y)	0

abschließend

Bitte lassen Sie mich wissen, wenn Sie Fehler oder Ratschläge haben. Bitte testen Sie es gründlich, bevor Sie es für den Wettbewerb verwenden !!

Verweise

Dies sind die beiden am Anfang genannten Personen. ↓ ・ [Juppys Blog](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) ・ Takotsubos HP Es hat mir geholfen, das Prinzip im Allgemeinen zu verstehen. ↓ ・ Schritt für Schritt Segmentbäume implementieren und verstehen (Python) Es wurde eine Referenz für den nicht rekursiven Segmentbaumteil. ↓ ・ Ich möchte den Segmentbaum etwas beschleunigen ・ Segmentbaum nicht rekursiv schreiben

Algorithmus (Segmentbaum) in Python (Übung)