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

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 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

And 1 is the identity element.

Examples of monoids

• 1 In short, if a value equal to or greater than the value that can appear is taken, it becomes the identity element. For example, if the constraint of the problem is $ A_i <= 10 ^ 4 $, if the identity element is $ 10 ^ 4 + 1 $, then $ min (A_i, 10 ^ 4 + 1) = min (10 ^ 4 + 1,) A_i) = A_i $, which is the identity element. There is no identity element for all natural numbers.

• 2 In a discussion similar to the case of the minimum value, if the value less than the value that can appear is taken, it becomes the identity element.

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.

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,

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.

Given that

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],

Like this

• Look at the child if your area of responsibility is outside the query.
• If the query range includes your area of responsibility, return the value.
• Returns the identity element if the position is unrelated to the query.

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

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

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.)