Range Sum Query
Bạn có một mảng số nguyên nums không bao giờ thay đổi và một danh sách queries. Mỗi truy vấn là một cặp [left, right] gồm các chỉ số bắt đầu từ 0, yêu cầu tính nums[left] + nums[left+1] + ... + nums[right], bao gồm cả hai đầu mút. Hãy trả về các đáp án theo cùng thứ tự với các truy vấn.
Hàm
- numsinteger-array
- mảng số nguyên, giống nhau cho mọi truy vấn
- queriesinteger-2d-array
- các khoảng cần cộng lại, mỗi khoảng là một cặp [left, right] với left ≤ right
- Trả vềinteger-array
- Tổng của mỗi khoảng, mỗi truy vấn một khoảng, theo thứ tự truy vấn
Ràng buộc
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ left ≤ right < nums.lengthcho mọi truy vấn[left, right]
Ví dụ
- Đầu vào
- nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
- Đầu ra
- [6, 0, 1]
- Giải thích
- Các chỉ số từ 0 đến 2 chứa
3 + (-2) + 5 = 6. Các chỉ số từ 1 đến 4 chứa-2 + 5 + 1 + (-4) = 0. Phạm vi[3, 3]chỉ chứa giá trị1.
- Đầu vào
- nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
- Đầu ra
- [18, 9, 2, 8]
- Giải thích
- Tổng của cả mảng là
18, hai giá trị cuối cùng là1 + 8 = 9, riêng chỉ số 0 là2, còn các chỉ số từ 1 đến 2 là7 + 1 = 8.
Câu hỏi mở rộng
Nếu các số tạo thành một lưới và mỗi truy vấn yêu cầu tính tổng của một hình chữ nhật, bạn sẽ mở rộng tổng tiền tố như thế nào để trả lời mỗi truy vấn trong thời gian hằng số?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Nhiều truy vấn có các giá trị gần như giống nhau. Bạn có thể làm việc gì một lần trước khi đọc bất kỳ truy vấn nào?
Nếu biết tổng của
igiá trị đầu tiên với mọii, bạn có thể tính tổng trong một đoạn bằng hiệu của hai tổng đó.Tạo
prefixvớiprefix[0] = 0vàprefix[i+1] = prefix[i] + nums[i]. Sau đó, mỗi truy vấn[left, right]được tính bằngprefix[right+1] - prefix[left].
Lời giải
Một phạm vi đơn lẻ là một vòng lặp, nhưng mỗi truy vấn có thể bao phủ phần lớn mảng, nên tính tổng từng phạm vi riêng lẻ sẽ lặp lại các phép cộng giống nhau. Cộng dồn mảng một lần thành các tổng tiền tố, rồi mỗi phạm vi chỉ cần một phép trừ.
Cộng từng khoảng
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Với mỗi truy vấn, hãy cộng lần lượt các giá trị từ nums[left] đến nums[right] vào tổng. Cách này đúng vì nó đọc mọi giá trị trong phạm vi, và với một truy vấn thì đó là cách tốt nhất bạn có thể làm. Một truy vấn có thể bao gồm tối đa n giá trị, nên q truy vấn cần tối đa n × q phép cộng: 1.5 × 10^7 khi n = 10^4 và q = 1500, gần như tất cả đều bị lặp lại.
Thuật toán
- Tạo một danh sách kết quả trống.
- Với mỗi truy vấn
[left, right], đặttotal = 0. - Cộng
nums[i]vàototalvới mọiitừleftđếnright, bao gồm cả hai đầu. - Thêm
totalvào danh sách kết quả và trả về danh sách đó sau truy vấn cuối cùng.
def sumRange(nums, queries):
answers = []
for left, right in queries:
total = 0
for i in range(left, right + 1):
total += nums[i]
answers.append(total)
return answersTổng tiền tố
Ý tưởng
Gọi prefix[i] là tổng của i giá trị đầu tiên, với prefix[0] = 0. Với [3, -2, 5, 1, -4, 6], ta có [0, 3, 1, 6, 7, 3, 9].
Khoảng [left, right] là tổng mọi giá trị đến chỉ số right trừ đi tổng mọi giá trị trước chỉ số left: prefix[right+1] - prefix[left]. Với [1, 4], ta có prefix[5] - prefix[1] = 3 - 3 = 0. Số 0 ở đầu giúp ta dùng cùng một công thức cho khoảng bắt đầu tại chỉ số 0. Chỉ cần một lượt cộng n lần để tạo mảng, sau đó mỗi truy vấn chỉ cần một phép trừ.
Thuật toán
- Tạo
prefixcó độ dàin+1vớiprefix[0] = 0. - Với mỗi
itừ0đếnn-1, đặtprefix[i+1] = prefix[i] + nums[i]. - Với mỗi truy vấn
[left, right], thêmprefix[right+1] - prefix[left]vào danh sách kết quả. - Trả về danh sách kết quả.
def sumRange(nums, queries):
# prefix[i] is the sum of the first i values, so prefix[0] = 0.
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
# nums[left..right] is the first right+1 values minus the first left values.
return [prefix[right + 1] - prefix[left] for left, right in queries]
Lỗi thường gặp và trường hợp biên
- Viết
prefix[right] - prefix[left]. Vớiprefix[0] = 0, cách này bỏ quanums[right], nên đoạn[3, 3]cho kết quả0thay vì1. - Tạo
prefixcó độ dài bằngnums, đểprefix[i]bao gồmnums[i]. Khi đó, đoạn bắt đầu từ 0 cầnprefix[-1], nhưng chỉ số này nằm ngoài phạm vi, và Python âm thầm đọc phần tử cuối cùng. - Dừng vòng lặp vét cạn tại
i < right. Cả hai đầu mút đều được tính, nên[3, 3]sẽ không tính tổng phần tử nào. - Trong Lua và R, vốn đếm từ 1, truy vấn bắt đầu từ 0
[left, right]bao gồm từnums[left+1]đếnnums[right+1], và các chỉ số của mảng tổng tích lũy cũng dịch chuyển tương tự.
Câu hỏi thường gặp3
Mảng tổng tiền tố là gì?
Một mảng mà mỗi phần tử là tổng của tất cả giá trị trước một vị trí: prefix[i] = nums[0] + ... + nums[i-1], với prefix[0] = 0. Bạn tạo mảng này chỉ trong một lượt, sau đó tính tổng của bất kỳ đoạn nào [left, right] bằng prefix[right+1] - prefix[left].
Độ phức tạp thời gian của truy vấn tổng trên một đoạn bằng tổng tiền tố là bao nhiêu?
O(n) để tạo mảng tiền tố một lần, sau đó O(1) cho mỗi truy vấn, nên tổng cộng là O(n + q) cho q truy vấn. Cộng trực tiếp từng phạm vi sẽ tốn đến O(n) cho mỗi truy vấn, tổng cộng là O(n·q).
Điều gì sẽ xảy ra nếu mảng có thể thay đổi giữa các truy vấn?
Vậy mảng tổng tiền tố không phù hợp, vì mỗi lần cập nhật sẽ làm thay đổi mọi tổng phía sau và cần O(n) để tính lại. Cây Fenwick hoặc cây phân đoạn xử lý cả thao tác cập nhật lẫn tính tổng một khoảng trong O(log n).
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def sumRange(nums, queries):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Đối số
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
Đầu ra mong đợi
[6, 0, 1]