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).
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
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.
Anything called a ** monoid ** can be embedded.
I think it's a bit less rigorous,
It suffices if the associative law holds and the identity element exists.
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))
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.
Calculation | Identity element |
---|---|
addition | 0 |
multiplication | 1 |
minimum value | INF ※1 |
Maximum value | -INF ※2 |
Least common multiple | 1 |
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
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)
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.
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
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
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
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.
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)
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