Chương 22 - Advanced Tree (BST, Segment Tree, Fenwick Tree)

Chương cây nâng cao gồm 3 cấu trúc chính: BST (Binary Search Tree), Segment Tree, và Fenwick Tree (Binary Indexed Tree). Cả 3 đều giải bài “range query với update” trong O(log n) per operation. Trong phỏng vấn Big Tech, BST hỏi rất nhiều; Segment/Fenwick xuất hiện ở vòng on-site Hard.

Mục tiêu chương

Sau chương này, bạn sẽ:

  • BST: dùng bound (low, high) truyền xuống, không chỉ check local.
  • Fenwick Tree: prefix sum + point update O(log n), code ngắn nhất.
  • Segment Tree: range query phức tạp (min/max/GCD/lazy update).
  • Coordinate compression khi giá trị lớn nhưng số phần tử nhỏ.

Khi nào dùng pattern này?

  • BST - bất kỳ bài “tree với property left < node < right”.
  • Segment Tree - range query + point update / range update O(log n).
  • Fenwick (BIT) - prefix sum + point update O(log n), code ngắn hơn segment tree.

Lựa chọn nhanh: - Cần sum / prefix only → Fenwick (đơn giản hơn). - Cần min / max / GCD / complex merge → Segment Tree. - Range update lazy → Segment Tree with lazy propagation.

Template code 

# 1) BST validate / search - xem Chương 11.4

# 2) Fenwick Tree (1-indexed)
class Fenwick:
    def __init__(self, n: int):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i: int, delta: int) -> None:    # 1-indexed
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def query(self, i: int) -> int:                  # prefix sum [1..i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def range_query(self, l: int, r: int) -> int:
        return self.query(r) - self.query(l - 1)


# 3) Segment Tree - sum, iterative version
class SegTree:
    def __init__(self, n: int):
        self.n = n
        self.tree = [0] * (2 * n)

    def update(self, i: int, val: int) -> None:
        i += self.n
        self.tree[i] = val
        while i > 1:
            i //= 2
            self.tree[i] = self.tree[2*i] + self.tree[2*i+1]

    def query(self, l: int, r: int) -> int:          # [l, r)
        res = 0
        l += self.n; r += self.n
        while l < r:
            if l & 1: res += self.tree[l]; l += 1
            if r & 1: r -= 1; res += self.tree[r]
            l //= 2; r //= 2
        return res

Bài tự luyện cuối chương

  • LC 1109 - Corporate Flight Bookings
  • LC 1395 - Count Number of Teams
  • LC 2179 - Count Good Triplets in an Array

22.1 Validate BST (LC 98) - recap

Đã giải đầy đủ ở Chương 11.4. Pattern: DFS với bound (low, high) hoặc inorder check strictly increasing.

Liên hệ với chương này

  • BST property là global - phải truyền bound từ root xuống, không chỉ check local.
  • Inorder của BST là sequence sorted strictly increasing - đây là gateway cho các bài Advanced Tree khác như Recover BST (22.2), Kth Smallest in BST (LC 230).

Code Python 3 (recap) 

import math

class Solution:
    def isValidBST(self, root) -> bool:
        def dfs(node, low: float, high: float) -> bool:
            if not node:
                return True
            if not (low < node.val < high):
                return False
            return dfs(node.left, low, node.val) and \
                   dfs(node.right, node.val, high)
        return dfs(root, -math.inf, math.inf)

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(h) stack.

Bài tự luyện liên quan

  • LC 99 - Recover BST (bài 22.2).
  • LC 230 - Kth Smallest Element in BST.

22.2 Recover Binary Search Tree (LC 99)

Đề bài

Input: root của 1 BST (LC level-order serialize). Đúng 2 node của BST bị swap giá trị nhầm. Khôi phục BST (sửa giá trị) mà không thay đổi cấu trúc cây. Yêu cầu O(1) extra space (follow-up).

Ví dụ 

Input:  root = [1, 3, null, null, 2]
        (LC level-order serialize)

        Cây ban đầu (KHÔNG phải BST hợp lệ):
              1
             / \
            3   *
             \
              2

Output: root sau khi recover = [3, 1, null, null, 2]
        Cây sau khi sửa (BST hợp lệ):
              3
             / \
            1   *
             \
              2

Giải thích: hàm mutate cây in-place; 2 node bị swap value là 1 và 3 →
            chỉ cần swap value của 2 node đó.

Ràng buộc

  • 2 <= số node <= 1000
  • -2^31 <= node.val <= 2^31-1

Clarifying questions

  • Có khả năng > 2 node bị swap? → Theo đề: đúng 2.
  • Tree rỗng? → Không, có swap nghĩa là có node.

Hướng tiếp cận

Inorder traversal của BST đúng = sequence tăng strictly. Khi có 2 node swap, inorder sẽ có 2 vị trí vi phạm (a > b với a đứng trước b).

  • Case 1: 2 vi phạm liền kề → 2 node cần swap là a và b trong vi phạm này.
  • Case 2: 2 vi phạm cách xa → first = a của vi phạm 1, second = b của vi phạm 2.

Sau khi tìm first, second → swap giá trị chúng.

Code Python 3 

class Solution:
    def recoverTree(self, root) -> None:
        first = second = prev = None

        def inorder(node) -> None:
            nonlocal first, second, prev
            if not node:
                return
            inorder(node.left)
            if prev and prev.val > node.val:
                if not first:
                    first = prev
                second = node
            prev = node
            inorder(node.right)

        inorder(root)
        first.val, second.val = second.val, first.val

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(h) stack.

Bình luận

  • Morris Traversal đạt O(1) extra space thực sự (không stack) - phức tạp hơn, thường không cần trong phỏng vấn.

Bài tự luyện liên quan

  • LC 98 - Validate BST.
  • LC 530 - Minimum Absolute Difference in BST.

22.3 Serialize and Deserialize Binary Tree (LC 297)

Đề bài

Thiết kế 2 hàm: serialize(root) -> str và deserialize(str) -> root.

Ví dụ 

Input:  root = [1, 2, 3, null, null, 4, 5]
        (LC level-order serialize)

        Cây thực tế:
              1
             / \
            2   3
               / \
              4   5

Output (serialize): "1,2,#,#,3,4,#,#,5,#,#"
        (preorder DFS; `#` đại diện cho node None)

Yêu cầu round-trip: deserialize(serialize(root)) tạo lại cây tương đương
(cùng cấu trúc + cùng giá trị) với root ban đầu.

Ràng buộc

  • 0 <= số node <= 10^4
  • -1000 <= node.val <= 1000

Clarifying questions

  • Định dạng output không cố định? → Tuỳ chọn, miễn round-trip qua deserialize.

Hướng tiếp cận

Preorder DFS với # cho None.

  • Serialize: preorder, mỗi node ghi val,; mỗi None ghi #,.
  • Deserialize: split, dùng iterator. Mỗi lần đọc 1 token:
    • # → None.
    • Khác → tạo node, đệ quy build trái rồi phải.

Code Python 3 

class Codec:
    def serialize(self, root) -> str:
        parts: list[str] = []

        def go(node):
            if not node:
                parts.append('#')
                return
            parts.append(str(node.val))
            go(node.left)
            go(node.right)

        go(root)
        return ','.join(parts)

    def deserialize(self, data: str):
        tokens = iter(data.split(','))

        def build():
            tk = next(tokens)
            if tk == '#':
                return None
            node = TreeNode(int(tk))
            node.left = build()
            node.right = build()
            return node

        return build()

Phân tích độ phức tạp

  • Thời gian: O(n) cho cả 2. Bộ nhớ: O(n).

Bình luận

  • Phiên bản BFS cũng ổn, dễ quan sát bằng mắt khi gỡ lỗi.
  • Bẫy: dùng iterator (next(tokens)) thay vì index - tránh bug khi duy trì trạng thái index thủ công.

Bài tự luyện liên quan

  • LC 449 - Serialize and Deserialize BST.
  • LC 428 - Serialize and Deserialize N-ary Tree.

22.4 Binary Tree Maximum Path Sum (LC 124)

Đề bài

Cho root của binary tree. Path là dãy node nối nhau qua edge (không nhất thiết qua root). Tìm path có sum max.

Ví dụ 

Input:  root = [1, 2, 3]
        Cây thực tế:
              1
             / \
            2   3
Output: 6
        (path 2 → 1 → 3, tổng = 6)

Input:  root = [-10, 9, 20, null, null, 15, 7]
        Cây thực tế:
              -10
              /  \
             9    20
                 /  \
                15   7
Output: 42
        (path 15 → 20 → 7, tổng = 42, bỏ qua root -10 vì không có lợi)

Ràng buộc

  • 1 <= số node <= 3·10^4
  • -1000 <= node.val <= 1000

Clarifying questions

  • Tree 1 node? → Path sum = node.val.
  • Tất cả negative? → Trả node âm lớn nhất.

Hướng tiếp cận

DFS bottom-up: mỗi node trả về “đường đi từ node xuống một lá” tối đa (= node.val + max(left_path, right_path, 0)). Đồng thời cập nhật best với “đường đi qua chính node” = node.val + left_path + right_path.

max(..., 0) để có thể bỏ subtree có sum âm.

Code Python 3 

class Solution:
    def maxPathSum(self, root) -> int:
        self.best = -float('inf')

        def dfs(node) -> int:
            if not node:
                return 0
            left = max(dfs(node.left), 0)
            right = max(dfs(node.right), 0)
            self.best = max(self.best, node.val + left + right)
            return node.val + max(left, right)

        dfs(root)
        return self.best

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(h) stack.

Bình luận

  • Tinh thần “trả 1 chiều, cập nhật 2 chiều” - pattern Tree DP cốt lõi (Chương 42).

Bài tự luyện liên quan

  • LC 543 - Diameter of Binary Tree.
  • LC 687 - Longest Univalue Path.

22.5 Count of Smaller Numbers After Self (LC 315)

Đề bài

Cho mảng nums. Trả về counts[i] = số phần tử nhỏ hơn nums[i] ở phía sau trong mảng.

Ví dụ 

Input:  nums = [5, 2, 6, 1]
Output: [2, 1, 1, 0]
Giải thích:
  5 có {2, 1} nhỏ hơn sau → 2.
  2 có {1} → 1.
  6 có {1} → 1.
  1 có 0.

Ràng buộc

  • 1 <= len(nums) <= 10^5
  • -10^4 <= nums[i] <= 10^4

Clarifying questions

  • Duplicate trong nums? → Có (mỗi xuất hiện tính riêng).

Hướng tiếp cận

Brute force - O(n²). TLE.

Cách 1 - Merge sort + đếm inversion (Chương 17.2).

Khi merge 2 nửa đã sort, khi lấy phần tử từ nửa trái L[i], mọi phần tử đã được lấy ra trước từ nửa phải đều nhỏ hơn L[i] → đếm vào counts[i].

Cách 2 - Fenwick Tree, O(n log n).

Duyệt từ phải sang trái. Với mỗi nums[i]: - counts[i] = fenwick.query(rank(nums[i]) - 1) - số phần tử nhỏ hơn đã thấy. - fenwick.update(rank(nums[i]), +1).

rank = vị trí của nums[i] trong sorted unique → coordinate compression.

Code Python 3 (Fenwick) 

from typing import List
from bisect import bisect_left

class Fenwick:
    def __init__(self, n): self.n = n; self.tree = [0] * (n + 1)
    def update(self, i, d=1):
        while i <= self.n:
            self.tree[i] += d
            i += i & -i
    def query(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s


class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        sorted_vals = sorted(set(nums))
        rank = {v: i + 1 for i, v in enumerate(sorted_vals)}  # 1-indexed
        f = Fenwick(len(sorted_vals))
        counts = [0] * len(nums)
        for i in range(len(nums) - 1, -1, -1):
            r = rank[nums[i]]
            counts[i] = f.query(r - 1)
            f.update(r, 1)
        return counts

Phân tích độ phức tạp

  • Thời gian: O(n log n). Bộ nhớ: O(n).

Bình luận

  • Coordinate compression = thu hẹp range giá trị vào [1, k] với k ≤ n.
  • Pattern Fenwick “đếm số nhỏ hơn / lớn hơn đã thấy” mạnh - áp dụng cho LC 327, 493.

Bài tự luyện liên quan

  • LC 327 - Count of Range Sum.
  • LC 493 - Reverse Pairs.

22.6 Range Sum Query - Mutable (LC 307)

Đề bài

Thiết kế class: - NumArray(nums): khởi tạo. - update(index, val): set nums[index] = val. - sumRange(left, right): tổng nums[left..right].

Cả update và sumRange phải O(log n).

Ví dụ 

Input (LC-style operation arrays):
  ops  = ["NumArray", "sumRange", "update", "sumRange"]
  args = [[[1, 3, 5]], [0, 2],    [1, 2],   [0, 2]]

Output: [null, 9, null, 8]

Giải thích:
  NumArray([1, 3, 5])  → khởi tạo, return null
  sumRange(0, 2)       → 1 + 3 + 5 = 9
  update(1, 2)         → đặt nums[1] = 2; mảng giờ là [1, 2, 5]
  sumRange(0, 2)       → 1 + 2 + 5 = 8

Ràng buộc

  • 1 <= len(nums) <= 3·10^4
  • -100 <= nums[i] <= 100
  • Tối đa 3·10^4 op

Clarifying questions

  • Query với i không hợp lệ? → Theo đề: 0 ≤ i < len.

Hướng tiếp cận

Fenwick Tree là lựa chọn lý tưởng - code ngắn nhất cho bài này. Segment Tree cũng làm được nhưng dài hơn.

Code Python 3 (Fenwick) 

from typing import List

class NumArray:
    def __init__(self, nums: List[int]):
        self.n = len(nums)
        self.nums = nums[:]
        self.tree = [0] * (self.n + 1)
        for i, x in enumerate(nums):
            self._add(i + 1, x)

    def _add(self, i: int, delta: int) -> None:
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def _prefix(self, i: int) -> int:
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def update(self, index: int, val: int) -> None:
        delta = val - self.nums[index]
        self.nums[index] = val
        self._add(index + 1, delta)

    def sumRange(self, left: int, right: int) -> int:
        return self._prefix(right + 1) - self._prefix(left)

Phân tích độ phức tạp

  • Init: O(n log n). Update / Query: O(log n).

Bình luận

  • Cấu trúc Fenwick: ý tưởng “mỗi index i lưu sum của 1 đoạn dài lowbit(i)”. Trick i & -i lấy bit thấp nhất → vị trí kế tiếp.
  • Lúc nào segment tree? Khi cần merge phức tạp hơn (min/max/GCD/lazy).

Bài tự luyện liên quan

  • LC 304 - Range Sum Query 2D Mutable.
  • LC 308 - Range Sum 2D Mutable.

Tóm tắt chương & Quyết định

Tree family map

Cấu trúc Hỗ trợ Khi nào dùng
Binary Tree (cây thường) Duyệt, đường đi LC 124, 543
BST (sorted invariant) Search, kth, range count LC 230, 938
Fenwick / BIT Prefix sum / count, point update LC 307, 315
Segment Tree Range query/update tổng quát LC 732, 218
Trie Prefix strings Chương 23, 41

Fenwick vs Segment Tree

  Fenwick Segment Tree
Op cơ bản Prefix sum, point update Range sum, range min/max/gcd…
Code ~10 dòng ~40-60 dòng
Bộ nhớ n 4n
Lazy propagation Khó Dễ
Khi đủ dùng Khi chỉ cần prefix/sum Khi cần range query + update phức tạp

Count Smaller After Self (LC 315) - coordinate compression

  • Giá trị có thể đến ±10⁴ → array size lớn? Nhưng số phần tử ≤ 5 × 10⁴.
  • Compress: sort unique → map mỗi value về rank [0, m-1]. Fenwick size m đủ.

Serialize / Deserialize (LC 297) - chọn traversal

  • Preorder + null marker ("1,2,#,#,3,#,#"): tự nhiên với đệ quy, deserialize bằng queue.
  • Level-order (BFS): dễ quan sát bằng mắt, dùng cho format gần với LC.
  • Cả hai đều O(n) time/space. Preorder thường ngắn hơn vài byte.