Segment Trees
- Segment Trees are a data structure where each node is responsible for a range of values.
- Can do point updates in $O(\log n)$ and range queries in $O(\log n)$.
- Requires $2\cdot n+1$ storage.
- Implemented as a collection of complete binary tree.
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β 1: β
β ----- β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β 2: β 3: β
β [3,11) β ----- β
βββββββββββββββββ¬ββββββββββββββββ«ββββββββββββββββββββββββββββββββ
β 4: β 5: β 6: β 7: β
β [3,7) β [7,11) β ----- β [1,3) β
βββββββββ¬ββββββββΌββββββββ¬ββββββββ ββββββββ¦ββββββββ£ββββββββ¬ββββββββ’
β 8: β 9: β 10: β 11: β 12: β 13: β 14: β 15: β
β [3,5) β [5,7) β [7,9) β [9,11)β[11,13)β 0 β 1 β 2 β
βββββ¬ββββΌββββ¬ββββΌββββ¬ββββΌββββ¬ββββ«ββββ¬ββββ ββββ€ββββ©ββββ€ββββͺββββ€ββββ
β16:β17:β18:β19:β20:β21:β22:β23:β24:β25:β β β β β β |
β 3 β 4 β 5 β 6 β 7 β 8 β 9 β10 β11 β12 β β β β β β β
βββββ§ββββ§ββββ§ββββ§ββββ§ββββ§ββββ§ββββ©ββββ§ββββββββ΄ββββ΄ββββ΄ββββ΄ββββ΄ββββ
βββββββββββ
βTree idx:β
β range β
βββββββββββ
References
OP = lambda a, b: min(a, b)
E = lambda : math.inf
class SegTree:
def __init__(self, A: List[int]) -> None:
n = len(A)
self.T: List[int] = [E()] * (2 * n)
for i in range(n):
self.T[n + i] = A[i]
for i in range(n - 1, 0, -1):
self.T[i] = OP(self.T[2 * i] , self.T[2 * i + 1])
self.n: int = n
def __getitem__(self, i: int) -> int:
return self.T[self.n + i]
def point_update(self, i: int, value: int) -> None:
i += self.n
self.T[i] = value
while i > 1:
i //= 2
self.T[i] = OP(self.T[2 * i] , self.T[2 * i + 1])
def range_query(self, l: int, r: int) -> int: # [l, r)
res_l, res_r = E(), E()
l += self.n
r += self.n
while l < r:
if l % 2 == 1:
res_l = OP(res_l, self.T[l])
l += 1
if r % 2 == 1:
r -= 1
res_r = OP(self.T[r], res_r)
l //= 2
r //= 2
return OP(res_l, res_r)