linkjobai / Segment Trees for Interviews: Range Queries with Updates
0 Lajky
0 Forky
1 Soubory
Naposledy aktivní 5 days ago
Interview prep notes
Segment Trees for Interviews: Range Queries with Updates
Prefix sums answer range-sum queries in O(1), but a single update costs O(n). When a problem mixes point updates and range queries (LeetCode 307, Range Sum Query - Mutable), a segment tree gives O(log n) for both.
Iterative segment tree (compact version)
class SegTree:
def __init__(self, nums):
self.n = len(nums)
Novější
Starší