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.
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.
#####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
Anything will be fine. For example ↓
a = [14, 5, 9, 13, 7, 12, 11, 1, 7, 8]
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)
Used for initialization. It does not affect the calculation. Infinity is the case for finding the minimum value.
ide_ele = float('inf')
seg = SegTree(a, segfunc, ide_ele)
Treat the list as 0-index. (As always.) There are two operations you can perform.
** update (k, x) **: Update the kth element to x.
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
#####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))
| 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 |
Please let me know if you have any mistakes or advice. Please test it thoroughly before using it for the contest !!
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