Pattern · Prefix Sum (Tổng tiền tố)Dễ ~15 phút đọc + làm

Truy Vấn Tổng Đoạn — Mảng Bất BiếnRange Sum Query - Immutable

Hiểu bài

Cho mảng số nguyên nums không thay đổi sau khi khởi tạo. Cài đặt class NumArray hỗ trợ nhiều truy vấn sumRange(left, right) — trả về tổng các phần tử từ chỉ số left đến right (bao gồm cả hai đầu).

Ví dụ:

const arr = new NumArray([-2, 0, 3, -5, 2, -1])
arr.sumRange(0, 2)  // 1   (−2 + 0 + 3)
arr.sumRange(2, 5)  // -1  (3 − 5 + 2 − 1)
arr.sumRange(0, 5)  // -3

Điểm mấu chốt: mảng bất biến nhưng số lượng truy vấn có thể rất lớn — chi phí mỗi truy vấn mới là thứ cần tối ưu.

Xem cách cơ bản (chậm hơn)

Cách cơ bảnKhởi tạo O(1) · mỗi truy vấn O(n) time · O(1) space thêm

class NumArrayNaive {
  private nums: number[]

  constructor(nums: number[]) {
    this.nums = nums
  }

  sumRange(left: number, right: number): number {
    // cộng trực tiếp từng phần tử trong đoạn
    let sum = 0
    for (let i = left; i <= right; i++) sum += this.nums[i]
    return sum
  }
}

Vì sao cách này chậm:

Mỗi truy vấn quét lại cả đoạn.
Với q truy vấn trên mảng n phần tử → O(q·n).
Khi q và n cùng cỡ 10⁴ thì tổng phép cộng lên tới 10⁸ — quá chậm cho giới hạn thời gian.

Lời giải tối ưu

Tối ưuTiền xử lý O(n) · mỗi truy vấn O(1) time · O(n) space cho mảng tiền tố

class NumArray {
  private prefix: number[]

  constructor(nums: number[]) {
    // prefix[i] = tổng của i phần tử đầu; prefix[0] = 0
    this.prefix = new Array(nums.length + 1)
    this.prefix[0] = 0
    for (let i = 0; i < nums.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + nums[i]
    }
  }

  sumRange(left: number, right: number): number {
    return this.prefix[right + 1] - this.prefix[left]
  }
}

Mấu chốt:

Trả trước chi phí một lần: xây mảng tiền tố prefix dài n+1 với prefix[i] = tổng i phần tử đầu.

Tổng đoạn [left, right] = prefix[right + 1] − prefix[left] — phần tổng trước left có mặt trong cả hai giá trị nên triệt tiêu khi trừ, mỗi truy vấn chỉ còn một phép trừ.
Quy ước prefix[0] = 0 giúp truy vấn từ chỉ số 0 không cần xử lý riêng.
Đây là dạng tối ưu kinh điển khi dữ liệu bất biến còn truy vấn thì nhiều.

Chạy thử từng bước

Chạy thử qua từng bước — bấm vào một bước để xem dòng code tương ứng

1class NumArray {
2  private prefix: number[]
3 
4  constructor(nums: number[]) {
5    // prefix[i] = tổng của i phần tử đầu; prefix[0] = 0
6    this.prefix = new Array(nums.length + 1)
7    this.prefix[0] = 0
8    for (let i = 0; i < nums.length; i++) {
9      this.prefix[i + 1] = this.prefix[i] + nums[i]
10    }
11  }
12 
13  sumRange(left: number, right: number): number {
14    return this.prefix[right + 1] - this.prefix[left]
15  }
16}

Trường hợp biên phải nhớ

Truy vấn 1 phần tử (left === right): prefix[left+1] − prefix[left] = nums[left] — công thức vẫn đúng, không cần nhánh riêng.
Truy vấn toàn mảng (0, n−1): prefix[n] − prefix[0] = tổng cả mảng, nhờ mốc prefix[0] = 0.
Mảng chứa số âm (như ví dụ trên): phép cộng dồn và phép trừ hoạt động bình thường, kết quả có thể âm.
Mảng 1 phần tử [5]: prefix = [0, 5], sumRange(0, 0) = 5.

Tham khảo thêm

Hiểu bài

Ví dụ:

const arr = new NumArray([-2, 0, 3, -5, 2, -1])
arr.sumRange(0, 2)  // 1   (−2 + 0 + 3)
arr.sumRange(2, 5)  // -1  (3 − 5 + 2 − 1)
arr.sumRange(0, 5)  // -3

Điểm mấu chốt: mảng bất biến nhưng số lượng truy vấn có thể rất lớn — chi phí mỗi truy vấn mới là thứ cần tối ưu.

class NumArrayNaive { private nums: number[] constructor(nums: number[]) { this.nums = nums } sumRange(left: number, right: number): number { // cộng trực tiếp từng phần tử trong đoạn let sum = 0 for (let i = left; i <= right; i++) sum += this.nums[i] return sum } }

Lời giải tối ưu

Tối ưuTiền xử lý O(n) · mỗi truy vấn O(1) time · O(n) space cho mảng tiền tố

class NumArray {
  private prefix: number[]

  constructor(nums: number[]) {
    // prefix[i] = tổng của i phần tử đầu; prefix[0] = 0
    this.prefix = new Array(nums.length + 1)
    this.prefix[0] = 0
    for (let i = 0; i < nums.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + nums[i]
    }
  }

  sumRange(left: number, right: number): number {
    return this.prefix[right + 1] - this.prefix[left]
  }
}

Mấu chốt:

Trả trước chi phí một lần: xây mảng tiền tố prefix dài n+1 với prefix[i] = tổng i phần tử đầu.

Tổng đoạn [left, right] = prefix[right + 1] − prefix[left] — phần tổng trước left có mặt trong cả hai giá trị nên triệt tiêu khi trừ, mỗi truy vấn chỉ còn một phép trừ.
Quy ước prefix[0] = 0 giúp truy vấn từ chỉ số 0 không cần xử lý riêng.
Đây là dạng tối ưu kinh điển khi dữ liệu bất biến còn truy vấn thì nhiều.

Chạy thử từng bước

Chạy thử qua từng bước — bấm vào một bước để xem dòng code tương ứng

1class NumArray {
2  private prefix: number[]
3 
4  constructor(nums: number[]) {
5    // prefix[i] = tổng của i phần tử đầu; prefix[0] = 0
6    this.prefix = new Array(nums.length + 1)
7    this.prefix[0] = 0
8    for (let i = 0; i < nums.length; i++) {
9      this.prefix[i + 1] = this.prefix[i] + nums[i]
10    }
11  }
12 
13  sumRange(left: number, right: number): number {
14    return this.prefix[right + 1] - this.prefix[left]
15  }
16}

Trường hợp biên phải nhớ

Truy vấn 1 phần tử (left === right): prefix[left+1] − prefix[left] = nums[left] — công thức vẫn đúng, không cần nhánh riêng.

Truy vấn toàn mảng (0, n−1): prefix[n] − prefix[0] = tổng cả mảng, nhờ mốc prefix[0] = 0.

Mảng chứa số âm (như ví dụ trên): phép cộng dồn và phép trừ hoạt động bình thường, kết quả có thể âm.

Mảng 1 phần tử [5]: prefix = [0, 5], sumRange(0, 0) = 5.

Hiểu bài

Lời giải tối ưu

Chạy thử từng bước

Trường hợp biên phải nhớ

Bài cùng chủ đề

Tích Mảng Ngoại Trừ Chính Nó

Đoạn Con Có Tổng Bằng K

Đoạn Con Tổng Lớn Nhất

Hiểu bài

Lời giải tối ưu

Chạy thử từng bước

Trường hợp biên phải nhớ

Bài cùng chủ đề

Tích Mảng Ngoại Trừ Chính Nó

Đoạn Con Có Tổng Bằng K

Đoạn Con Tổng Lớn Nhất