Truy Vấn Tổng Đoạn & Cập Nhật Điểm (Fenwick / BIT)
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề 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ịvvào phần tửA[i].2 L R: Tính tổng các phần tử từA[L]đếnA[R].
Dữ liệu vào (Input)
- Dòng 1: Hai số nguyên dương
NvàQ(1 ≤ N, Q ≤ 2 × 10^5). - Dòng 2:
Nsố nguyên ban đầuA[1..N]. Qdòng tiếp theo: Mỗi dòng mô tả một truy vấn loại1hoặc loại2.
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
Community Discussion