Thay đổi giá trị một phần tử & xuất tổng của đoạn

TONGDOAN Tổng đoạn 1
Cho một dãy số có độ dài N gồm các số nguyên. Người ta có M yêu cầu gồm 2 loại sau:
+ C i j : Thay phần tử thứ i bằng giá trị j.
+ Q i j : xuất ra tổng các phần tử trong dãy số, từ vị trí i đến vị trí j.

Yêu cầu : Cho trước dãy số và các yêu cầu. Hãy làm phép biến đổi trên dãy và viết các kết quả.
Input :
·   Dòng đầu tiên chứa 2 số nguyên N và M. (1≤ N ≤ 10^4; M ≤ 10^5)
·   Dòng thứ 2 chứa các phần tử của dãy. (|ai| ≤ 1000)
·   M dòng cuối chứa các yêu cầu.
Output : Gồm một số dòng tương ứng là kết quả của các yêu cầu Q trong file input.

Input :
5 3
1 4 3 4 5
Q 2 3
C 3 7
Q 1 4
Output
7
16
- Kiến thức : Interval tree
- Giải : sử dụng một cây tính tổng từ [i,j]. Với mỗi truy vấn C x y ta update lại tất cả các tổng chứa phần tử x tăng thêm một khoảng a[x]-y.

CODE