There are many other articles about segment trees, so please choose the one that is easy for you to use! (If you like the segment tree in this article, please use it for competitive programming etc. It is welcome.)
https://algo-logic.info/segment-tree/ https://qiita.com/takayg1/items/c811bd07c21923d7ec69 https://qiita.com/mosamosa/items/d17ab5af6e19f67202cb
Introducing today is a mode that allows you to select a segment tree function. Code below (Received comments on 2021/1/13 and revised if enumeration → dictionary)
segki_simple.py
import sys
import math
sys.setrecursionlimit(10**7)
class segki():
DEFAULT = {
'min': 1 << 60,
'max': -(1 << 60),
'sum': 0,
'prd': 1,
'gcd': 0,
'lmc': 1,
'^': 0,
'&': (1 << 60) - 1,
'|': 0,
}
FUNC = {
'min': min,
'max': max,
'sum': (lambda x, y: x + y),
'prd': (lambda x, y: x * y),
'gcd': math.gcd,
'lmc': (lambda x, y: (x * y) // math.gcd(x, y)),
'^': (lambda x, y: x ^ y),
'&': (lambda x, y: x & y),
'|': (lambda x, y: x | y),
}
def __init__(self, N, ls, mode='min'):
"""
Number of leaves N,Element ls,Function mode(min,max,sum,prd(product),gcd,lmc,^,&,|)
"""
self.default = self.DEFAULT[mode]
self.func = self.FUNC[mode]
self.N = N
self.K = (N - 1).bit_length()
self.N2 = 1 << self.K
self.dat = [self.default] * (2**(self.K + 1))
for i in range(self.N): #Leaf construction
self.dat[self.N2 + i] = ls[i]
self.build()
def build(self):
for j in range(self.N2 - 1, -1, -1):
self.dat[j] = self.func(self.dat[j << 1], self.dat[j << 1 | 1]) #Conditions that parents have
def leafvalue(self, x): #The xth value in the list
return self.dat[x + self.N2]
def update(self, x, y): # index(x)To y
i = x + self.N2
self.dat[i] = y
while i > 0: #Change parent value
i >>= 1
self.dat[i] = self.func(self.dat[i << 1], self.dat[i << 1 | 1])
return
def query(self, L, R): # [L,R)Section acquisition
L += self.N2
R += self.N2
vL = self.default
vR = self.default
while L < R:
if L & 1:
vL = self.func(vL, self.dat[L])
L += 1
if R & 1:
R -= 1
vR = self.func(self.dat[R], vR)
L >>= 1
R >>= 1
return self.func(vL, vR)
I think that the monoids that can be placed on the segment tree are mostly covered (min, max, sum, product, gcd, lmc, ^, &, |). Please point out any mistakes.
There are three arguments required to build a tree: number of elements N, initial element (list), and function (mode). The identity element is defined in DEFAULT (change if necessary). Computational complexity O (N)
Specify the index to be changed by update and the changed value. Computational complexity O (log (N))
You can get the value of any index with leafvalue. Computational complexity O (1). (For example, it is possible to add x to the kth value in combination with updating the value.)
You can get the value of the interval with query. query (L, R) The value that can be obtained is the value of the interval [L, R). Computational complexity O (log (N))
1, atcoder ABC185F https://atcoder.jp/contests/abc185/tasks/abc185_f https://atcoder.jp/contests/abc185/submissions/19042056 It's an xor guy. About 900ms. There seems to be more room for improvement ...
2, atcoder Chokudai SpeedRun 001J https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_j https://atcoder.jp/contests/chokudai_S001/submissions/19404893 It is a problem to find the number of inversions. You can use sum.
3, atcoder Chokudai SpeedRun 001H https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_h https://atcoder.jp/contests/chokudai_S001/submissions/19404925 It's a LIS problem. You can use max.
Thank you for reading. I myself am a beginner in competitive programming, so please point out any mistakes. Let's enjoy the competitive professional life together! !!
Recommended Posts