Truy Vấn Tổng Đoạn & Cập Nhật Điểm (Fenwick / BIT)

Buổi 15 — Prefix Sum & Difference Array Buổi 26 — Fenwick Tree Data-structures prefix-sum
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho mảng A gồm N số nguyên (đánh số từ 1 đến N) và Q truy vấn thuộc một trong hai loại:

  • 1 i v: Cộng thêm giá trị v vào phần tử A[i].
  • 2 L R: Tính tổng các phần tử từ A[L] đến A[R].
Dữ liệu vào (Input)
  • Dòng 1: Hai số nguyên dương N và Q (1 ≤ N, Q ≤ 2 × 10^5).
  • Dòng 2: N số nguyên ban đầu A[1..N].
  • Q dòng tiếp theo: Mỗi dòng mô tả một truy vấn loại 1 hoặc loại 2.
Dữ liệu ra (Output)
  • Với mỗi truy vấn loại 2, in ra tổng đoạn [L, R] trên một dòng.
Ví dụ mẫu
Sample Input 13500000000000
Gợi ý thuật toán

Khai báo

5 4
1 2 3 4 5
2 1 3
1 2 5
2 1 3
2 2 5
Sample Output 1
6
11
19
Draft saved