Array — trực quan các thao tác

1. Truy cập theo chỉ số: O(1)

2. Chèn / xóa giữa: O(n) — phải dịch chuyển

3. Binary search: O(log n)

function binarySearch(arr, target):
    lo, hi = 0, len(arr)-1
    while lo <= hi:
        mid = (lo + hi) / 2
        if arr[mid] == target: return mid
        if arr[mid] < target:  lo = mid + 1
        else:                  hi = mid - 1
    return -1

4. Đảo ngược mảng tại chỗ — two pointer: O(n)

function reverse(arr):
    left, right = 0, len(arr)-1
    while left < right:
        swap(arr[left], arr[right])
        left += 1
        right -= 1

5. Dynamic array — resize doubling (vì sao amortized O(1)?)

Khi size == capacity, cấp mảng mới gấp đôi và copy toàn bộ → lần đó tốn O(n). Nhưng tổng cost của n lần push = O(n), nên trung bình mỗi lần = O(1).

Thử: append liên tục — copy chỉ xảy ra tại các mốc 2^k; chia tổng công cho n phép append: trung bình O(1).

size=0 · capacity=1

6. Sliding window: tổng lớn nhất cửa sổ k (README §8.3)

Trượt cửa sổ size k: mỗi bước thêm phần tử phải, bỏ phần tử trái → cập nhật tổng O(1) thay vì cộng lại cả cửa sổ. Tím = cửa sổ hiện tại, viền vàng = cửa sổ tổng lớn nhất tới giờ.