Tổng tiền tố

def xay_prefix_sum(arr):
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix

def tong_doan(prefix, l, r):
    """Tổng arr[l..r] (l và r đều tính, 0-indexed)."""
    return prefix[r + 1] - prefix[l]

arr = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = xay_prefix_sum(arr)
print(prefix)                     # [0, 3, 4, 8, 9, 14, 23, 25, 31]
print(tong_doan(prefix, 1, 4))    # 11  (1+4+1+5)
print(tong_doan(prefix, 0, 7))    # 31  (toàn mảng)
print(tong_doan(prefix, 3, 5))    # 15  (1+5+9)

def xay_prefix_2d(mat):
    rows, cols = len(mat), len(mat[0])
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r in range(rows):
        for c in range(cols):
            prefix[r+1][c+1] = (mat[r][c]
                + prefix[r][c+1]
                + prefix[r+1][c]
                - prefix[r][c])
    return prefix

def tong_hinh_chu_nhat(prefix, r1, c1, r2, c2):
    """Tổng hình chữ nhật từ (r1,c1) đến (r2,c2) (0-indexed, cả hai bên)."""
    return (prefix[r2+1][c2+1]
            - prefix[r1][c2+1]
            - prefix[r2+1][c1]
            + prefix[r1][c1])

mat = [
    [3, 0, 1, 4],
    [5, 6, 3, 2],
    [1, 2, 0, 1],
    [4, 1, 0, 3],
]
prefix = xay_prefix_2d(mat)
print(tong_hinh_chu_nhat(prefix, 0, 0, 1, 1))   # 14  (3+0+5+6)
print(tong_hinh_chu_nhat(prefix, 1, 1, 3, 3))   # 18  (6+3+2+2+0+1+1+0+3)

def dem_day_con_tong_k(arr, k):
    """
    Đếm số dãy con liên tiếp có tổng bằng k.
    Dùng prefix sum + hashmap đạt O(n).
    """
    from collections import defaultdict
    dem_prefix = defaultdict(int)
    dem_prefix[0] = 1   # prefix[0] = 0 xuất hiện 1 lần

    prefix = 0
    ket_qua = 0
    for x in arr:
        prefix += x
        # Nếu prefix - k tồn tại, có (prefix-k) → prefix là dãy có tổng k
        ket_qua += dem_prefix[prefix - k]
        dem_prefix[prefix] += 1

    return ket_qua

print(dem_day_con_tong_k([1, 1, 1], 2))           # 2
print(dem_day_con_tong_k([1, 2, 3], 3))            # 2  ([1,2] và [3])
print(dem_day_con_tong_k([1, -1, 0], 0))           # 3

def range_update(arr, queries):
    """
    queries: [(l, r, x)] — cộng x vào arr[l..r]
    Dùng difference array: diff[l] += x, diff[r+1] -= x
    Sau đó xây prefix sum của diff để lấy kết quả.
    """
    n = len(arr)
    diff = [0] * (n + 1)

    for l, r, x in queries:
        diff[l] += x
        diff[r + 1] -= x

    # Xây prefix sum của diff rồi cộng vào arr gốc
    tich_luy = 0
    result = arr[:]
    for i in range(n):
        tich_luy += diff[i]
        result[i] += tich_luy

    return result

arr = [1, 2, 3, 4, 5]
queries = [(1, 3, 2), (0, 2, -1), (2, 4, 3)]
print(range_update(arr, queries))
# arr sau (1,3,+2): [1,4,5,6,5]
# sau (0,2,-1):     [0,3,4,6,5]
# sau (2,4,+3):     [0,3,7,9,8]

def tim_chi_so_can_bang(arr):
    """
    Tìm tất cả vị trí i sao cho sum(arr[:i]) == sum(arr[i+1:]).
    Dùng prefix sum tính nhanh.
    """
    tong = sum(arr)
    prefix = 0
    can_bang = []

    for i, x in enumerate(arr):
        # Tổng bên trái = prefix (chưa tính arr[i])
        # Tổng bên phải = tong - prefix - arr[i]
        if prefix == tong - prefix - x:
            can_bang.append(i)
        prefix += x

    return can_bang

print(tim_chi_so_can_bang([1, 7, 3, 6, 5, 6]))    # [3] (6: trái=11, phải=11)
print(tim_chi_so_can_bang([1, 2, 3]))               # []
print(tim_chi_so_can_bang([0, 0, 0, 0]))            # [0, 1, 2, 3]