Try to implement and understand the segment tree step by step (python)

Introduction

When I'm doing AtCoder, I often see strong people tweeting on Twitter, such as pasting a seg tree, but since I did not have it myself, it is an article that I will implement it at this time and connect it to understanding and application. ..

If you happen to be in the contest and want to implement it right away, there is a code in the implementation summary. Operation cannot be guaranteed.

I'm sorry to say what number the decoction is. I'm thinking of differentiating myself by not omitting the implementation of Narutake.

Make it the most basic structure of one-point update and section acquisition. I will write lazy evaluation in the sequel if I feel like it (or if I need it).

Referenced sites

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

What is a segment tree?

What can i do?

Interval queries related to operations and operations that satisfy certain properties can be obtained with ** O (logN) **. (For example, a query to find the minimum value of the first or fifth element) However, note that it takes ** O (N) ** to build.

Then what kind of calculation can be used?

Anything called a ** monoid ** can be embedded.

What is a monoid

I think it's a bit less rigorous,

It suffices if the associative law holds and the identity element exists.

What is an associative law?

For example, if you think about addition

(a+b)+c = a+(b+c)

By doing so, ** it is good if the result does not change no matter where you calculate when calculating between three or more things ** Since this holds, the segment tree can divide the interval more and more by acquiring the value. ([0,6) → (like [0,4) + [4,6))

What is the identity element?

It's difficult to say the original, but in terms of application, if you think in terms of addition,

a + 0 = 0+ a = a

** A number that is the same as the original number when calculated with it is called the identity element ** Besides, for example, if you think about multiplication

a \cdot 1 = 1 \cdot a = a

And 1 is the identity element.

Examples of monoids

Calculation Identity element
addition 0
multiplication 1
minimum value INF ※1
Maximum value -INF ※2
Least common multiple 1

I think that more special operations can be treated as monoids depending on other restrictions, but I don't think people who come up with such ideas need to read this article, so I'll leave it.

[reference] http://beet-aizu.hatenablog.com/entry/2017/09/10/132258

What kind of structure is it?

A binary tree with the results of a query on the interval to cover. Implement as an array.

セグ木.png

Like this. The lower you go, the smaller the section becomes.

Please pay attention to the index of the array. ** You can get the index of the child by the index of the parent x2 and the index of the parent x2 + 1. ** It's basic in BIT (Binary index tree) or binary tree system, but I was impressed when I saw it for the first time. By the way, this is because I think with 1-index, and when it is 0-index, it becomes × 2 + 1, × 2 + 2. It doesn't matter which one you use, but I personally use 1-index because the operation of seeing the parent from the child only needs to be cut off by 2.

Here, the bottom leaf will contain the original data of the array you want to query. (This time it is a size 4 array)

What if the number of elements in the array is not 2 ^ k?

Determine the depth of the tree so that the number of leaves at the bottom can be prepared for the array to which the interval query is originally calculated. The surplus part should be filled with the identity element.

Let's change it a little and consider an example of array size = 3. If you fill in the surplus part with the identity element that appeared above,

segtree2.png

In this way, it can be processed without any particular influence.

Implementation

Initialization

Determine the array size to store the tree so that the number of leaves at the end is 2 ^ k and you can secure more than the size of the array you want to query.

1+2+4+8+\cdots+2^n = 2^{n+1} -1

Given that

2 ^ k> = (data array size)

For k, prepare an array for storing trees with a size of $ 2 ^ {k + 1} $. The implementation looks like this.

class segtree:

    def __init__(self, n,operator,identity):
        """
        n:Data array size
        operator:operator(Monoid).. Function object
        identity:Identity element corresponding to the operator
        """
        nb = bin(n)[2:] #Convert to binary and remove 0b in battle
        bc = sum([int(digit) for digit in nb]) #The number of bits where 1 stands. When this is 1, it's just 2^nb.If not, 2^nb<n<2^(nb+1)
        if bc == 1: #2^with nb
            self.num_end_leaves = 2**(len(nb)-1) #The bottom leaf is 2^nb pieces
        else:#If not 2^(nb+1)Secure
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)] #Initialize with identity element

        self.identity = identity 
        self.operator =operator
        #Have the identity element and operator for later use

Update value

I wrote it briefly at the beginning, but if it is 1-index, if you divide your index by 2 and truncate it, you will become your parent. (Like 3 → 1, 5 → 2)

The value is updated by tracing this to the origin and applying the operators in order. The implementation of only this part looks like this.

    def update(self,x,val):
        """
        x:Substitution location
        val:Value to substitute
        """
        actual_x = x+self.num_leaves #1-Add the minute where the index of the leaf at the end of the index starts(For example, when the data array size is 4, the tree array size is 8, and the latter half starts from index 4.
        self.array[actual_x] = val #Update value
        while actual_x > 0 :
            actual_x = actual_x//2#See parents
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])#Update parents with a new child

Get value

For a certain range, it is sufficient if the range can be expressed by a combination of leaves covering the largest possible range. For example, if your data array is 4 in size and you want a range of [0,2],

q1.png q2.png q3.png

Like this

If you repeat this time, [0,1], [2], the identity element will be obtained as a value, and these subregions will be merged.

operator ([0,1], [2], identity element) = operator ([0,1], [2]) = operator ([0,2])

You can get an interval query. The implementation looks like this.

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        """
        q_left: Left of query interval
        q_right:Right of the query interval
        arr_ind:Tree array index. Since the first is a parent, 1
        leaf_left:To the left of the tree array index, the range covered by the leaves it represents
        depth:Depth in a tree array. Used to calculate the size of the coverage
        """
        width_of_floor = self.num_end_leaves//(2**depth) #Now leaf cover width
        leaf_right = leaf_left+width_of_floor-1 #Find the right side of the current leaf coverage from the left edge and cover width.

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity #Returns the identity element if the query area and leaves are unrelated

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind] #Returns the leaf value if the query area is completely filled with leaves

        else: #If not, look at the child
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)#Child's left
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)#Child's right
            return self.operator(val_l,val_r)#Performs an operation to merge children.

Implementation summary

Folding because I just stuck the previous ones
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)

Trial

Make an array of appropriate range and ask for the minimum value. In addition, plan the execution time appropriately.

s_tree = segtree(10**5,min,10**9) #10**Since it is an array of up to 5, the identity element is 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

After all construction is the heaviest. The operation seems to be normal. (It seems that the bug will be filled if you do not move it with a more complicated problem.)

Recommended Posts

Try to implement and understand the segment tree step by step (python)
Try to understand Python self
[Introduction] I tried to implement it by myself while explaining to understand the binary tree
[CleanArchitecture with Python] Apply CleanArchitecture step by step to a simple API and try to understand "what kind of change is strong" in the code base.
Try to face the integration by parts
Understand the Decision Tree and classify documents
[Python Kivy] How to get the file path by dragging and dropping
Put Cabocha 0.68 on Windows and try to analyze the dependency with Python
Try to build python and anaconda environment on Mac (by pyenv, conda)
I tried to verify and analyze the acceleration of Python by Cython
Try to implement Oni Maitsuji Miserable in python
Try to solve the man-machine chart with Python
How to erase the characters output by Python
Knowledge notes needed to understand the Python framework
Try porting the "FORTRAN77 Numerical Computing Programming" program to C and Python (Part 1)
Try porting the "FORTRAN77 Numerical Computing Programming" program to C and Python (Part 3)
Try porting the "FORTRAN77 Numerical Computing Programming" program to C and Python (Part 2)
[Introduction] I tried to implement it by myself while explaining the binary search tree.
Try to solve the programming challenge book with python3
How to put Takoyaki Oishikunaru on the segment tree
Try refactoring step by step
[Python] Try to read the cool answer to the FizzBuzz problem
The first step of machine learning ~ For those who want to implement with python ~
Try to solve the internship assignment problem with Python
Carefully understand the exponential distribution and draw in Python
Try to operate DB with Python and visualize with d3
Plot and understand the multivariate normal distribution in Python
Read the xml file by referring to the Python tutorial
Carefully understand the Poisson distribution and draw in Python
The first step to getting Blender available from Python
The VIF calculated by Python and the VIF calculated by Excel are different .. ??
Artificial intelligence, machine learning, deep learning to implement and understand
A super introduction to Django by Python beginners! Part 6 I tried to implement the login function
Try to import to the database by manipulating ShapeFile of national land numerical information with Python
A story about porting the code of "Try and understand how Linux works" to Rust
Try to make it using GUI and PyQt in Python
Try hitting the Twitter API quickly and easily with Python
Try to get the function list of Python> os package
Understand the Strategy pattern by comparing JavaScript and Java code
How to switch the configuration file to be read by Python
Make the display of Python module exceptions easier to understand
Understand the difference between cumulative assignment to variables and cumulative assignment to objects
Neural network to understand and implement in high school mathematics
Understand the Decorator pattern by comparing JavaScript and Java code
[Python] Try to classify ramen shops by natural language processing
Understand the State pattern by comparing JavaScript and Java code
Build a Python environment and transfer data to the server
"Deep copy" and "Shallow copy" to understand with the smallest example
Debug by attaching to the Python process of the SSH destination
I tried to implement the mail sending function in Python
Understand the Composite pattern by comparing JavaScript and Java code
I want to know the features of Python and pip
I tried to enumerate the differences between java and python
[Python] The first step to making a game with Pyxel
[Introduction to Tensorflow] Understand Tensorflow properly and try to make a model
Just try to receive a webhook in ngrok and python
Try to decipher the garbled attachment file name with Python
Wagtail Recommendations (3) Understand and use the tree structure of pages
[Python] Visualize Arashi's lyrics with WordCloud and try to understand what I wanted to convey to fans in the 20th year of formation.
Understand Python packages and modules
Read the old Gakushin DC application Word file (.doc) from Python and try to operate it.