Cho mảng a[] có n phần tử. Có q truy vấn, mỗi truy vấn là 2 số L, R. Với mỗi truy vấn, in ra tổng các phần tử từ a[L] đến a[R].

Input Format

Dòng 1 là n và q

Dòng 2 là n số nguyên

q dòng tiếp theo mỗi dòng là 1 truy vấn

Output Format

In ra kết quả của mỗi truy vấn trên 1 dòng

Ràng buộc:

1 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5

1 ≤ a[i] ≤ 10^9

1 ≤ L ≤ R ≤ n

C++

Question

Cho mảng a[] có n phần tử. Có q truy vấn, mỗi truy vấn là 2 số L, R. Với mỗi truy vấn, in ra tổng các phần tử từ a[L] đến a[R].

Input Format

Dòng 1 là n và q

Dòng 2 là n số nguyên

q dòng tiếp theo mỗi dòng là 1 truy vấn

Output Format

In ra kết quả của mỗi truy vấn trên 1 dòng

Ràng buộc:

1 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5

1 ≤ a[i] ≤ 10^9

1 ≤ L ≤ R ≤ n

C++

Accepted Answer

Dưới đây là đoạn code C++ giải bài toán tổng đoạn (range sum) với n phần tử và q truy vấn, sử dụng prefix sum để trả lời truy vấn trong O(1) thời gian: ```cpp #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector a(n + 1, 0); for (int i = 1; i <= n; i++) { cin >> a[i]; } // Tính prefix sum for (int i = 1; i <= n; i++) { a[i] += a[i - 1]; } while (q--) { int L, R; cin >> L >> R; // Tổng từ L đến R = prefix[R] - prefix[L-1] cout << a[R] - a[L - 1] << " "; } return 0; } ``` **Giải thích:** - Đọc vào mảng a từ 1 đến n. - Tạo mảng prefix sum, prefix[i] = tổng a[1] đến a[i]. - Với mỗi truy vấn (L, R), kết quả là prefix[R] - prefix[L-1]. - Cách này giúp trả lời mỗi truy vấn trong O(1), phù hợp với ràng buộc lớn (n, q ≤ 10^5).

Cho mảng a[] có n phần tử. Có q truy vấn, mỗi truy vấn là 2 số L, R. Với mỗi truy vấn, in ra tổng các phần tử từ a[L] đến a[R]. Input Format Dòng 1 là n và q Dòng 2 là n số nguyên q dòng ti...