Yêu cầu cập nhật giá trị của phần tử nums[index] thành val.
Yêu cầu trả về tổng các phần tử trong mảng nums trong khoảng [left, right] (bao gồm left và right). Trong đó left≤right.
Triển khai lớp NumArray:
NumArray(int[] nums): Khởi tạo đối tượng với mảng số nguyên nums.
void update(int index, int val): Cập nhật giá trị của nums[index] thành val.
int sumRange(int left, int right): Trả về tổng các phần tử trong mảng nums 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:
1≤nums.length≤3∗104.
−100≤nums[i]≤100.
0<=index<num.length.
0≤left≤right<nums.length.
Số lần gọi phương thức update và sumRange không vượt quá 3∗104.
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à O(n), thời gian cập nhật một phần tử là O(logn), thời gian tính tổng của một khoảng là O(logn).