Cây chỉ số nhị phân Fenwick Tree cập nhật điểm và tính tổng đoạn

Mục tiêu kiến thức

• Cài đặt cấu trúc dữ liệu Cây chỉ số nhị phân (Binary Indexed Tree - BIT / Fenwick Tree).
• Áp dụng thao tác bitwise i += (i & -i) và i -= (i & -i) để cập nhật và tính tiền tố trong O(log N).
• Hỗ trợ thao tác cập nhật điểm (Point Update) và truy vấn tổng đoạn con (Range Sum Query) với N, Q ≤ 10⁵.
• Quản lý tổng lớn bằng kiểu 64-bit long long.

Mô tả bài toán

Hệ thống Gateway của AI Empire Academy phân bổ tài nguyên cho N tài khoản người dùng được đánh số từ 1 đến N (1 ≤ N ≤ 10⁵). Ban đầu, mỗi tài khoản i đã sử dụng một lượng token là A_i (0 ≤ A_i ≤ 10⁹).

Hệ thống cần xử lý Q yêu cầu thời gian thực (1 ≤ Q ≤ 10⁵) thuộc 2 loại:

• 1 i v: Tài khoản i vừa sử dụng thêm v token (1 ≤ i ≤ N, 0 ≤ v ≤ 10⁹). Giá trị token của tài khoản i được tăng thêm v: A_i = A_i + v.
• 2 L R: Thống kê tổng số lượng token đã sử dụng của tất cả các tài khoản từ L đến R: ∑_k=L^R A_k (1 ≤ L ≤ R ≤ N).

Hãy xử lý và in ra kết quả cho tất cả các truy vấn loại 2.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ N, Q ≤ 10⁵.
• 0 ≤ A_i, v ≤ 10⁹.
• 1 ≤ i ≤ N.
• 1 ≤ L ≤ R ≤ N.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.