Sổ biến động chỉ số

Bối cảnh và bài toán

Một hệ thống theo dõi n chỉ số. Mỗi thao tác hoặc cộng thêm một lượng vào đúng một vị trí, hoặc yêu cầu tổng trên một đoạn nửa mở [l,r). Khối lượng thao tác lớn khiến việc cộng trực tiếp từng phần tử trong mỗi truy vấn không còn phù hợp.

Yêu cầu

Xử lý toàn bộ cập nhật và truy vấn theo thứ tự.

Input

• Dòng 1 chứa n q.
• Dòng 2 chứa n giá trị ban đầu, đánh số từ 0.
• q dòng tiếp theo:
  • 0 p x: cộng x vào vị trí p.
  • 1 l r: hỏi tổng trên [l,r).

Output

Với mỗi truy vấn loại 1, in tổng tương ứng.

Ràng buộc

• 1 <= n, q <= 5 * 10^5
• 0 <= a[i], x <= 10^9
• 0 <= p < n
• 0 <= l < r <= n

Chấm điểm

Ví dụ 1

Input

5 5
1 2 3 4 5
1 0 5
1 2 4
0 3 10
1 0 5
1 0 3

Output

15
7
25
6

Giải thích. Cập nhật làm vị trí 3 (đánh số từ 0) tăng thêm 10 trước hai truy vấn cuối.

Ví dụ 2

Input

3 4
0 0 0
0 1 5
1 0 2
0 0 2
1 0 3

Output

5
7

Giải thích. Sau hai lần cộng, mảng là [2,5,0].

Thông tin bài tập

Nguồn: Phỏng theo AtCoder Library Practice Contest – Fenwick Tree.