Tổng đoạn

Hướng tiếp cận

Tính trước mảng tổng tiền tố $p_0=0$ và $p_i=a_1+a_2+\cdots +a_i$ với $i=1,2,\dots ,n$. Khi đó với mỗi truy vấn $(l,r)$:

$$a_l+a_{l+1}+\cdots +a_r=p_r-p_{l-1}.$$

Nhận xét quan trọng

1. Tiền xử lý mảng $p$ tốn $O(n)$ thời gian.
2. Mỗi truy vấn trả lời trong $O(1)$.
3. Vì $|a_i|\le {10}^9$ và $n\le 2·{10}^5$, tổng tối đa có giá trị tuyệt đối khoảng $2·{10}^{14}$ — vẫn nằm gọn trong kiểu long long.

Thuật toán

1. Đọc $n,q$ và dãy $a$.
2. Khởi tạo $p_0=0$; với $i$ từ $1$ tới $n$: $p_i=p_{i-1}+a_i$.
3. Với mỗi truy vấn $(l,r)$: in ra $p_r-p_{l-1}$.

Độ phức tạp

• Thời gian: $O(n+q)$.
• Bộ nhớ: $O(n)$.