Algorithm (segment tree) in Python (practice)

Introduction

Normally, I just googled and stuck a seg tree, but since I had time due to the influence of the coronavirus, I tried to implement it while understanding the principle. I built it while referring to the articles of various people mainly on the net. I will put the link in the last reference, but I usually use the code during the contest [Juppy's article](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 ), I've been particularly helpful to Ikatako Takotsubo-san's HP, so I'll list it at the beginning.

Purpose

I will summarize the principle etc. in another article. The purpose of this article is to explain ** how to use your own seg tree **. The general features are that you can set the identity element and the operation you want to perform by yourself, referring to Mr. Juppy, and that it is written in the class. The node of the seg tree was written with 1-index.

code

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

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

class SegTree:
    """
    init(init_val, ide_ele):Array init_Initialize with val O(N)
    update(k, x):Update kth value to x O(logN)
    query(l, r):section[l, r)Returns the segfunc of O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val:Initial value of array
        segfunc:Operation you want to make a section
        ide_ele:Identity element
        n:Element count
        num:The smallest power of 2 greater than or equal to n
        tree:Segment tree(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
        #Set the values of the array to the leaves
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        #Build
        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):
        """
Update kth value to 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)Get the 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

How to use

1. Prepare a list for initialization

Anything will be fine. For example ↓

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

2. Decide what to do in the section

I want to find the minimum and maximum values of an interval, I want to find the sum of intervals, etc. This time, suppose you want to find the minimum value. Write the function in segfunc.

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

3. Determine the identity element

Used for initialization. It does not affect the calculation. Infinity is the case for finding the minimum value.

ide_ele = float('inf')

4. Create an object, the above three arguments

seg = SegTree(a, segfunc, ide_ele)

5. Each operation can be performed

Treat the list as 0-index. (As always.) There are two operations you can perform.

1. Update of one element

** update (k, x) **: Update the kth element to x.

2. Get the result of the operation of a certain section

Get the value from ** query (l, r) **: ** [l, r) ** (interval between l and r).

# [0, 8)Show the minimum value of
print(seg.query(0, 8)) # 1

#Change 5th to 0
seg.update(5, 0)

# [0, 8)Show the minimum value of
print(seg.query(0, 8)) # 0

Summary

It's long, so I folded it.
#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################

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

class SegTree:
    """
    init(init_val, ide_ele):Array init_Initialize with val O(N)
    update(k, x):Update kth value to x O(N)
    query(l, r):section[l, r)Returns the segfunc of O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val:Initial value of array
        segfunc:Operation you want to make a section
        ide_ele:Identity element
        n:Element count
        num:The smallest power of 2 greater than or equal to n
        tree:Segment tree(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
        #Set the values of the array to the leaves
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        #Build
        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):
        """
Update kth value to 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)Get the 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))

Other operations (other than the minimum value)

operation segfunc Identity element
minimum value min(x, y) float('inf')
Maximum value max(x, y) -float('inf')
Interval sum x + y 0
Interval product x * y 1
Greatest common divisor math.gcd(x, y) 0

in conclusion

Please let me know if you have any mistakes or advice. Please test it thoroughly before using it for the contest !!

References

These are the two people mentioned at the beginning. ↓ ・ [Juppy's 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) ・ HP of Takotsubo-san It helped me to understand the principle in general. ↓ ・ Implementing and understanding segment trees step by step (python) It became a reference for the non-recursive seg tree part. ↓ ・ I want to speed up the Segment Tree a little -Write Segment Tree non-recursively

Recommended Posts

Algorithm (segment tree) in Python (practice)
Delayed segment tree in Python (debug request)
Genetic algorithm in python
Algorithm in Python (Dijkstra's algorithm)
Algorithm in Python (primality test)
Reproduce Euclidean algorithm in Python
Algorithm in Python (binary search)
Introducing Python in Practice (PiP)
Implement Dijkstra's Algorithm in python
Algorithm in Python (breadth-first search, bfs)
Python algorithm
Develop an investment algorithm in Python 2
Compiler in Python: PL / 0 syntax tree
Python implementation of non-recursive Segment Tree
Implementing a simple algorithm in Python 2
Run a simple algorithm in Python
Output tree structure of files in Python
Ant book in python: Sec.2-5 Dijkstra's algorithm
Algorithm in Python (ABC 146 C Binary Search
Write a simple greedy algorithm in Python
Draw a tree in Python 3 using graphviz
Manipulate namespaced XML in Python (Element Tree)
Alignment algorithm by insertion method in Python
Algorithm learned with Python 11th: Tree structure
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Python memorandum (algorithm)
Unittest in python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
quicksort in python
N-Gram in Python
Programming in python
Plink in Python
Constant in python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
LINE-Bot [0] in Python
Csv in python
Disassemble in Python
Reflection in Python
Constant in python
Beginners practice Python
nCr in Python.
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Quad-tree in Python
Reflection in Python