LeetCode 0307
About 5 min
0307. Range Sum Query - Mutable
- Nhãn: Thiết kế, Cây Fenwick, Cây phân đoạn, Mảng
- Độ khó: Trung bình
Tóm tắt đề bài
Mô tả: Cho một mảng nums
.
Yêu cầu:
- Thực hiện hai loại truy vấn:
- Yêu cầu cập nhật giá trị của phần tử
nums[index]
thànhval
. - Yêu cầu trả về tổng các phần tử trong mảng
nums
trong khoảng[left, right]
(bao gồmleft
vàright
). Trong đó .
- Yêu cầu cập nhật giá trị của phần tử
- Triển khai lớp
NumArray
:NumArray(int[] nums)
: Khởi tạo đối tượng với mảng số nguyênnums
.void update(int index, int val)
: Cập nhật giá trị củanums[index]
thànhval
.int sumRange(int left, int right)
: Trả về tổng các phần tử trong mảngnums
từ chỉ sốleft
đến chỉ sốright
(bao gồm cảleft
vàright
) (tức lànums[left] + nums[left + 1] + … + nums[right]
).
Giải thích:
- .
- .
- .
- .
- Số lần gọi phương thức
update
vàsumRange
không vượt quá .
Ví dụ:
- Ví dụ 1:
Cho nums = [1, 3, 5]
Tổng sumRange(0, 2) -> 9
Cập nhật update(1, 2)
Tổng sumRange(0, 2) -> 8
Ý tưởng giải quyết
Ý tưởng 1: Cây phân đoạn
- Dựa trên mảng
nums
, xây dựng một cây phân đoạn. Mỗi nút của cây phân đoạn lưu trữ ranh giới trái và phải của khoảng hiện tại và tổng của khoảng đó. - Để cập nhật giá trị của một phần tử, ta cập nhật giá trị tại nút tương ứng trong cây phân đoạn.
- Để tính tổng của một khoảng, ta tìm kiếm trong cây phân đoạn các nút tương ứng với khoảng và tính tổng các giá trị của các nút đó.
- Thời gian xây dựng cây phân đoạn là , thời gian cập nhật một phần tử là , thời gian tính tổng của một khoảng là .
Ý tưởng 1: Code
# Lớp nút cây phân đoạn
class SegTreeNode:
def __init__(self, val=0):
self.left = -1 # Ranh giới trái của khoảng
self.right = -1 # Ranh giới phải của khoảng
self.val = val # Giá trị của nút (tổng của khoảng)
# Lớp cây phân đoạn
class SegmentTree:
# Phương thức khởi tạo cây phân đoạn
def __init__(self, nums, function):
self.size = len(nums)
self.tree = [SegTreeNode() for _ in range(4 * self.size)] # Mảng lưu trữ SegTreeNode
self.nums = nums # Dữ liệu gốc
self.function = function # function là một hàm, phương thức tổng hợp của khoảng trái và phải
if self.size > 0:
self.__build(0, 0, self.size - 1)
# Phương thức cập nhật điểm: thay đổi nums[i] thành val
def update_point(self, i, val):
self.nums[i] = val
self.__update_point(i, val, 0)
# Phương thức truy vấn khoảng: truy vấn giá trị của khoảng [q_left, q_right]
def query_interval(self, q_left, q_right):
return self.__query_interval(q_left, q_right, 0)
# Phương thức lấy mảng nums: trả về mảng nums
def get_nums(self):
for i in range(self.size):
self.nums[i] = self.query_interval(i, i)
return self.nums
# Các phương thức triển khai bên trong
# Triển khai phương thức xây dựng cây phân đoạn: chỉ số lưu trữ của nút là index, khoảng của nút là [left, right]
def __build(self, index, left, right):
self.tree[index].left = left
self.tree[index].right = right
if left == right: # Nút lá, giá trị của nút là giá trị phần tử tại vị trí tương ứng
self.tree[index].val = self.nums[left]
return
mid = left + (right - left) // 2 # Điểm chia nút trái và phải
left_index = index * 2 + 1 # Chỉ số lưu trữ của nút con trái
right_index = index * 2 + 2 # Chỉ số lưu trữ của nút con phải
self.__build(left_index, left, mid) # Đệ quy tạo cây con trái
self.__build(right_index, mid + 1, right) # Đệ quy tạo cây con phải
self.__pushup(index) # Cập nhật giá trị khoảng của nút lên trên
# Triển khai phương thức cập nhật điểm: thay đổi nums[i] thành val. Chỉ số lưu trữ của nút là index, khoảng của nút là [left, right]
def __update_point(self, i, val, index):
left = self.tree[index].left
right = self.tree[index].right
if left == right:
self.tree[index].val = val # Nút lá, cập nhật giá trị của nút thành val
return
mid = left + (right - left) // 2 # Điểm chia nút trái và phải
left_index = index * 2 + 1 # Chỉ số lưu trữ của nút con trái
right_index = index * 2 + 2 # Chỉ số lưu trữ của nút con phải
if i <= mid: # Cập nhật giá trị của nút trong cây con trái
self.__update_point(i, val, left_index)
else: # Cập nhật giá trị của nút trong cây con phải
self.__update_point(i, val, right_index)
self.__pushup(index) # Cập nhật giá trị khoảng của nút lên trên
# Triển khai phương thức truy vấn khoảng: tìm kiếm giá trị của khoảng [q_left, q_right] trong khoảng [left, right] của cây
def __query_interval(self, q_left, q_right, index):
left = self.tree[index].left
right = self.tree[index].right
if left >= q_left and right <= q_right: # Khoảng của nút nằm trong khoảng [q_left, q_right]
return self.tree[index].val # Trả về giá trị của nút
if right < q_left or left > q_right: # Khoảng của nút không liên quan đến [q_left, q_right]
return 0
mid = left + (right - left) // 2 # Điểm chia nút trái và phải
left_index = index * 2 + 1 # Chỉ số lưu trữ của nút con trái
right_index = index * 2 + 2 # Chỉ số lưu trữ của nút con phải
res_left = 0 # Kết quả truy vấn cây con trái
res_right = 0 # Kết quả truy vấn cây con phải
if q_left <= mid: # Truy vấn trong cây con trái
res_left = self.__query_interval(q_left, q_right, left_index)
if q_right > mid: # Truy vấn trong cây con phải
res_right = self.__query_interval(q_left, q_right, right_index)
return self.function(res_left, res_right) # Trả về kết quả tính toán tổng của giá trị các nút con trái và phải
# Triển khai phương thức cập nhật lên trên: giá trị khoảng của nút có chỉ số index bằng tổng giá trị của nút con trái và phải
def __pushup(self, index):
left_index = index * 2 + 1 # Chỉ số lưu trữ của nút con trái
right_index = index * 2 + 2 # Chỉ số lưu trữ của nút con phải
self.tree[index].val = self.function(self.tree[left_index].val, self.tree[right_index].val)
class NumArray:
def __init__(self, nums: List[int]):
self.STree = SegmentTree(nums, lambda x, y: x + y)
def update(self, index: int, val: int) -> None:
self.STree.update_point(index, val)
def sumRange(self, left: int, right: int) -> int:
return self.STree.query_interval(left, right)