linkjobai 已修改 5 days ago. 還原成這個修訂版本
1 file changed, 44 insertions
segtree.md(檔案已創建)
| @@ -0,0 +1,44 @@ | |||
| 1 | + | # Segment Trees for Interviews: Range Queries with Updates | |
| 2 | + | ||
| 3 | + | 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. | |
| 4 | + | ||
| 5 | + | ## Iterative segment tree (compact version) | |
| 6 | + | ||
| 7 | + | ```python | |
| 8 | + | class SegTree: | |
| 9 | + | def __init__(self, nums): | |
| 10 | + | self.n = len(nums) | |
| 11 | + | self.t = [0] * (2 * self.n) | |
| 12 | + | self.t[self.n:] = nums | |
| 13 | + | for i in range(self.n - 1, 0, -1): | |
| 14 | + | self.t[i] = self.t[2 * i] + self.t[2 * i + 1] | |
| 15 | + | ||
| 16 | + | def update(self, i, val): | |
| 17 | + | i += self.n | |
| 18 | + | self.t[i] = val | |
| 19 | + | while i > 1: | |
| 20 | + | i //= 2 | |
| 21 | + | self.t[i] = self.t[2 * i] + self.t[2 * i + 1] | |
| 22 | + | ||
| 23 | + | def query(self, l, r): # inclusive l..r | |
| 24 | + | res, l, r = 0, l + self.n, r + self.n + 1 | |
| 25 | + | while l < r: | |
| 26 | + | if l & 1: res += self.t[l]; l += 1 | |
| 27 | + | if r & 1: r -= 1; res += self.t[r] | |
| 28 | + | l //= 2; r //= 2 | |
| 29 | + | return res | |
| 30 | + | ``` | |
| 31 | + | ||
| 32 | + | Swap `+` for `min`, `max` or `gcd` to support other associative operations. | |
| 33 | + | ||
| 34 | + | ## When an interviewer expects it | |
| 35 | + | ||
| 36 | + | - Range updates *and* range queries: mention **lazy propagation**. | |
| 37 | + | - Counting inversions or "count of smaller numbers after self" (315): a segment tree or Fenwick tree over value ranks. | |
| 38 | + | ||
| 39 | + | ## Fenwick tree comparison | |
| 40 | + | ||
| 41 | + | A Fenwick (binary indexed) tree is shorter to write and enough for prefix sums, but a segment tree handles min/max and lazy range updates more naturally. Saying which you'd pick and why is often worth more than the code. | |
| 42 | + | ||
| 43 | + | --- | |
| 44 | + | *Disclosure: I work on [Linkjob.ai](https://www.linkjob.ai/), which offers real-time interview help.* | |
上一頁
下一頁